Хэши, созданные Rabin Karp Rolling Hash, не отражаются в тексте

Question

Примечание: много возможных дубликатов, но, похоже, мою проблему ничто не решает.

Я работаю над обнаружением плагиата на основе MOSS .

После успешной реализации фильтра, который удаляет все необходимые детали (комментарии, знаки препинания и т. д.), я хэширую контент с помощью реализации скользящего хеширования (Рабин Карп)

Однако хэши, которые совпадают в двух текстовых файлах исходного кода, имеют очень разный базовый текст (без плагиата и одинаковых хешей)

Реализованный мной алгоритм (Ruby) -> (Частичный фрагмент)

родовое слово

Есть ли проблема с моей реализацией? Или указанные мной параметры могут быть ошибочными?

Я беру radix= 34 (Я не уверен, что это правильное значение, я предполагаю, что вырезанный текст будет содержать только алфавиты + некоторые специальные символы, такие как '+', '-', '*', '/', поэтому приблизительная оценка всего 34 символы)

Я беру q (простое число) равным 101

Я имею дело с проблемой столкновения? Есть указания, как решить эту проблему?

Answer 1

Замечу, что при q= 101 существует только 101 возможное значение хеш-функции - 0, 1, 2 ... 100.Вы пробовали увеличить q?Другой подход - посмотреть, выглядят ли хеш-значения так, будто они являются случайно выбранными значениями в пределах возможных значений 0,1..q-1.

Вы, конечно, также должны протестировать свою программу в тех случаях, когда есть повторяющиеся строки, которые нужно найти - сбой может быть еще одним признаком любой проблемы, которая также вызывает конфликты, и ее будет легче найти и отладить./ p>