Gibt es funktionierende Implementierungen der Rolling-Hash-Funktion, die im Rabin-Karp-String-Suchalgorithmus verwendet wird?

Question

Ich bin auf der Suche nach einer rollenden Hash-Funktion, so dass ich Hashes von N-Grammen einer sehr großen Zeichenfolge nehmen kann.

Zum Beispiel:

"Stackoverflow", in 5 Gramm aufgebrochen wäre:

"stack", "Tacko", "ackov", "ckove" "kover", „overf“, „verfl“, „erflo“, „rflow“

Dies ist ideal für eine roll Hashfunktion denn nachdem ich die ersten N-Gramm-Hash-Berechnung, die folgenden sind relativ billig, weil ich zu berechnen einfach den ersten Buchstaben des ersten Hashes löschen und den neuer letzter Buchstabe des zweiten Hashs.

Ich weiß, dass diese Hash-Funktion wird im allgemeinen erzeugt, wie:

H = c a ^{k - 1} + c a ^{k - 2} + c a ^{k - 3} + ... + c _k ein wo a ist eine Konstante und c1, ..., ck sind die Eingabezeichen.

Wenn Sie diesem Link auf der Rabin-Karp string search algorithm folgen, besagt es, dass "a" normalerweise einige große Primzahl ist.

Ich möchte meine Hashes in 32-Bit-Ganzzahlen gespeichert werden, also wie groß von einer Primzahl sollte "a" sein, so dass ich meine ganze Zahl nicht überlaufen?

Gibt es eine vorhandene Implementierung dieser Hash-Funktion irgendwo, die ich bereits verwenden könnte? Hier

---

ist eine Implementierung ich erstellt:

public class hash2 
{ 

    public int prime = 101; 

    public int hash(String text) 
    { 
     int hash = 0; 

     for(int i = 0; i < text.length(); i++) 
     { 
      char c = text.charAt(i); 
      hash += c * (int) (Math.pow(prime, text.length() - 1 - i)); 
     } 

     return hash; 
    } 

    public int rollHash(int previousHash, String previousText, String currentText) 
    { 

     char firstChar = previousText.charAt(0); 
     char lastChar = currentText.charAt(currentText.length() - 1); 

     int firstCharHash = firstChar * (int) (Math.pow(prime, previousText.length() - 1)); 
     int hash = (previousHash - firstCharHash) * prime + lastChar; 

     return hash; 
    } 

    public static void main(String[] args) 
    { 
     hash2 hashify = new hash2(); 

     int firstHash = hashify.hash("mydog"); 
     System.out.println(firstHash); 
     System.out.println(hashify.hash("ydogr")); 
     System.out.println(hashify.rollHash(firstHash, "mydog", "ydogr")); 
    } 

} 

Ich bin 101 als mein bester verwenden. Ist es wichtig, ob meine Hashes überlaufen werden? Ich denke, das ist wünschenswert, aber ich bin mir nicht sicher.

Scheint dies der richtige Weg zu sein?

Answer 1

wie ich sie verstehe, es ist eine Funktion Minimierung für:

2^31 - sum (maxchar) * A^kx 

wo maxchar = 62 (für A-Za-z0-9). Ich habe es gerade mit Excel (OO Calc, genau) berechnet :) und ein Maximum A, das es gefunden hat, ist 76, oder 73, für eine Primzahl.

Answer 2

Ich erinnere mich an eine etwas andere Implementierung, die von einem der Sedgewick Algorithmenbücher zu sein scheint (es enthält auch Beispielcode - versuchen Sie es nachzuschlagen). Hier ist eine Zusammenfassung, die auf 32-Bit-Ganzzahlen eingestellt ist:

Sie verwenden Modulo-Arithmetik, um zu verhindern, dass Ihre Ganzzahl nach jeder Operation überläuft.

anfänglich:

• c = Text ("Stackoverflow")
• M = Länge des "n-Gramm"
• d = Größe des Alphabets (256)
• q = a große Primzahl, so daß (d + 1) * q nicht überläuft (8.355.967 wäre eine gute Wahl sein)
• dM = d ^{M-1 mod q}

zuerst den Hash-Wert des ersten n-Gramm berechnen:

h = 0 
for i from 1 to M: 
    h = (h*d + c[i]) mod q 

und für jedes folgende n-gram:

for i from 1 to lenght(c)-M: 
    // first subtract the oldest character 
    h = (h + d*q - c[i]*dM) mod q 

    // then add the next character 
    h = (h*d + c[i+M]) mod q 

der Grund, warum Sie haben d * q hinzuzufügen, bevor die Subtraktion Das älteste Zeichen besteht darin, dass Sie aufgrund kleiner Werte, die durch die vorherige Modulo-Operation verursacht wurden, möglicherweise negative Werte erhalten.

Fehler enthalten, aber ich denke, Sie sollten die Idee bekommen. Versuchen Sie eines der Sedgewick Algorithmen Bücher für Details, weniger Fehler und eine bessere Beschreibung zu finden. :)

Answer 3

Nicht sicher, was Ihr Ziel hier ist, aber wenn Sie versuchen, die Leistung zu verbessern, kostet die Verwendung von math.pow Sie weit mehr als Sie sparen, indem Sie einen rollenden Hash-Wert berechnen.

Ich schlage vor, Sie beginnen, indem Sie einfach und effizient halten und Sie sind sehr wahrscheinlich finden, dass es schnell genug ist.