Hashes gerados por Rabin Karp Rolling Hash não refletem no texto

Question

Observação: muitas duplicatas possíveis, mas nada parece estar resolvendo meu problema.

Estou trabalhando em uma detecção de plágio baseada em MOSS .

Depois de implementar com sucesso um filtro que remove todos os detalhes necessários (comentários, pontuações, etc.), faço o hash do conteúdo usando uma implementação Rolling Hash (Rabin Karp)

No entanto, os Hashes que correspondem em dois arquivos de texto do código-fonte, têm um texto subjacente muito diferente (sem plágio e ainda assim os mesmos hashes)

O Algoritmo que implementei (Ruby) -> (Snippet parcial)

 #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    

Há um problema com minha implementação? Ou os parâmetros que eu especificar podem ser os culpados?

Eu pego radix= 34 (Não tenho certeza se é o valor correto, estou assumindo que o texto retirado conterá apenas alfabetos + alguns caracteres especiais como '+', '-', '*', '/' então uma estimativa aproximada do total de 34 personagens)

Estou considerando q (primo) como 101

Estou lidando com um problema de colisão? Alguma indicação de como lidar com o problema?

Answer 1

Observo que com q= 101, existem apenas 101 valores de hash possíveis - 0, 1, 2 ... 100.Você já tentou aumentar q?Outra abordagem seria verificar se os valores de hash parecem ser valores escolhidos aleatoriamente dentro dos valores possíveis de 0,1..q-1.

Obviamente, você também deve testar seu programa em casos onde há strings repetidas para ele localizar - uma falha pode ser outro sintoma de qualquer problema que também esteja causando colisões, e seria mais fácil de localizar e depurar.