Хэши, сгенерированные Рабином Карпом Rolling Hash, не отраженные в тексте

Question

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

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

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

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

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

 #Preprocessing from RobinKarp Algorithm
  for c in 0...k do
    text_hash=(radix*text_hash+text_to_process[c].ord)%q
  end

  #Main loop
  for c in 0...loop do   
        text_hash=((radix*text_hash-(text_to_process[c].ord)*highorder)+(text_hash[c+k].ord))%q    

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

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

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

Это проблема столкновенияЯ имею дело с?Любые указатели относительно того, как решить проблему?

Answer 1

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

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