Von Rabin Karp Rolling Hash erzeugte Hashes, die den Text nicht reflektieren

Question

Hinweis: Viele mögliche Duplikate, aber nichts scheint mein Problem zu lösen.

Ich arbeite an einer Plagiatserkennung basierend auf MOSS .

Nach erfolgreicher Implementierung eines Filters, der alle erforderlichen Details (Kommentare, Interpunktionen usw.) entfernt, habe ich den Inhalt mithilfe einer Rolling Hash-Implementierung (Rabin Karp) gehasht

Die Hashes, die in zwei Textdateien des Quellcodes übereinstimmen, haben jedoch einen sehr unterschiedlichen zugrunde liegenden Text (kein Plagiat und dennoch dieselben Hashes)

Der von mir implementierte Algorithmus (Ruby) -> (Teilausschnitt)

 #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    

Gibt es ein Problem mit meiner Implementierung? Oder können die von mir angegebenen Parameter fehlerhaft sein?

Ich nehme radix= 34 (Ich bin nicht sicher, ob es der richtige Wert ist. Ich gehe davon aus, dass der gestrippte Text nur Alphabete + einige Sonderzeichen wie '+', '-', '*', '/' enthält, also eine grobe Schätzung von insgesamt 34 Zeichen)

Ich nehme q (prime) als 101

Ist dies ein Kollisionsproblem, mit dem ich mich befasse? Gibt es Hinweise, wie das Problem gelöst werden kann?

Answer 1

Ich stelle fest, dass es mit q= 101 nur 101 mögliche Hashwerte gibt - 0, 1, 2 ... 100.Haben Sie versucht, q zu erhöhen?Ein anderer Ansatz wäre zu sehen, ob die Hash-Werte so aussehen, als wären sie zufällig ausgewählte Werte innerhalb der möglichen Werte von 0,1..q-1.

Sie sollten Ihr Programm natürlich auch in Fällen testen, in denen wiederholte Zeichenfolgen gefunden werden müssen - ein Fehler könnte ein weiteres Symptom für ein Problem sein, das ebenfalls Kollisionen verursacht, und es wäre einfacher zu finden und zu debuggen.