Hashs générés par Rabin Karp Rolling Hash Hash ne reflète pas le texte

Question

Remarque: beaucoup de doublons possibles, mais rien ne semble résoudre mon problème.

Je travaille sur une détection de plagiat basée sur MOUSSE.

Après avoir mis en œuvre avec succès un filtre qui supprime tous les détails nécessaires (commentaires, ponctuations, etc.) I Hash Le contenu à l'aide d'une implémentation de hachage roulante (Rabin Karp)

Cependant, les hachages qui correspondent en deux fichiers de texte du code source ont un texte sous-jacent très différent (pas de plagiat et pourtant les mêmes hachages)

L'algorithme que j'ai implémenté (Ruby) -> (extrait partiel)

 #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    

Y a-t-il un problème avec ma mise en œuvre? Ou les paramètres que je spécifie peuvent être en faute?

Je prends Radix = 34 (je ne sais pas si c'est la bonne valeur, je suppose que le texte supprimé ne contiendra que des alphabets + des charctres spéciaux comme '+', '-', '*', '/' SO A Estimation approximative de 34 caractères au total)

Je prends Q (Prime) à 101

Est-ce un problème de collision avec lequel je fais face? Des conseils sur la façon de s'attaquer au problème?

Answer 1

Je note qu'avec Q = 101, il n'y a que 101 valeurs de hachage possibles - 0, 1, 2 ... 100. Avez-vous essayé d'augmenter Q? Une autre approche serait de regarder et de voir si les valeurs de hachage semblent être des valeurs choisies au hasard dans les valeurs possibles de 0,1..q-1.

Vous devez bien sûr tester également votre programme sur les cas où il y a des chaînes répétées à trouver - une défaillance il pourrait y avoir un autre symptôme de tout problème qui provoque également des collisions, et il serait plus facile de trouver et de déboguer.