Хэши, созданные Rabin Karp Rolling Hash, не отражаются в тексте
-
28-10-2019 - |
Вопрос
Примечание: много возможных дубликатов, но, похоже, мою проблему ничто не решает.
Я работаю над обнаружением плагиата на основе MOSS .
После успешной реализации фильтра, который удаляет все необходимые детали (комментарии, знаки препинания и т. д.), я хэширую контент с помощью реализации скользящего хеширования (Рабин Карп)
Однако хэши, которые совпадают в двух текстовых файлах исходного кода, имеют очень разный базовый текст (без плагиата и одинаковых хешей)
Реализованный мной алгоритм (Ruby) -> (Частичный фрагмент)
родовое словоЕсть ли проблема с моей реализацией? Или указанные мной параметры могут быть ошибочными?
Я беру radix= 34 (Я не уверен, что это правильное значение, я предполагаю, что вырезанный текст будет содержать только алфавиты + некоторые специальные символы, такие как '+', '-', '*', '/', поэтому приблизительная оценка всего 34 символы)
Я беру q (простое число) равным 101
Я имею дело с проблемой столкновения? Есть указания, как решить эту проблему?
Решение
Замечу, что при q= 101 существует только 101 возможное значение хеш-функции - 0, 1, 2 ... 100.Вы пробовали увеличить q?Другой подход - посмотреть, выглядят ли хеш-значения так, будто они являются случайно выбранными значениями в пределах возможных значений 0,1..q-1.
Вы, конечно, также должны протестировать свою программу в тех случаях, когда есть повторяющиеся строки, которые нужно найти - сбой может быть еще одним признаком любой проблемы, которая также вызывает конфликты, и ее будет легче найти и отладить./ p>