Hashes gerados por Rabin Karp Rolling Hash não refletem no texto
-
28-10-2019 - |
Pergunta
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?
Solução
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.