Muss ich mich beim Rabin-Karp wirklich darum kümmern, eine Mod-Q-Operation auf die rollenden Hashes anzuwenden?

Ich habe über den Rabin Karp-Algorithmus gelesen und mich immer wieder gefragt, was die große Sache ist, wenn unsere rollenden Hashes durch einen Wert Q begrenzt werden.

Ich hatte gedacht, dass unsere Ganzzahlendarstellung auf dem typischen Computer 2-Komplement ist, was genau der Begrenzung aller unserer Operationen über die rollenden Hashes durch 2 ^ 31 entspricht, sodass es mich mit anderen Worten einfach nicht interessieren sollte. Je kleiner wir binden oder haschen, desto mehr Kollisionen hätten wir. Ein größeres Q sollte also gleichbedeutend mit einer verbesserten Leistung sein!

Ich habe versucht, eine einfache (Java) Implementierung zu codieren:

public static int rabinKarp(String text, String pattern) {
    if (text.length() < pattern.length()) {
        return -1;
    } else {
        int patternHash = 0;
        int textHash = 0;
        int pow = 1;

        // preprocessing the pattern and the first characters of the text string
        for (int i = pattern.length()-1; i >= 0; --i) {
            patternHash += pattern.charAt(i) * pow;
            textHash += text.charAt(i) * pow;
            pow *= 10;
        }
        pow /= 10;

        // actual search
        if (patternHash == textHash && areEqual(text, 0, pattern)) {
            return 0;
        } else {
            for (int i = 1; i < text.length()-pattern.length()+1; ++i) {
                textHash -= text.charAt(i-1)*pow;
                textHash *= 10;
                textHash += text.charAt(i+pattern.length()-1);
                if (textHash == patternHash && areEqual(text, i, pattern)) {
                    return i;
                }
            }
            return -1;
        }
    }
}

Nach einigen vorläufigen Tests scheint meine Hypothese empirisch korrekt zu sein, aber ich habe sie nirgendwo geschrieben gesehen, also wundere ich mich.

Vermisse ich etwas

Ja, in der Praxis kommt man gut zurecht, wenn man nur die Berechnungen überlaufen lässt. Sie arbeiten effektiv Modulo$2^{32}$. Es hat auch den Vorteil, dass keine (teure) Modulo-Berechnung erforderlich ist. Es fehlen jedoch einige der theoretischen Leistungsgarantien. Sie müssen bei der Auswahl der Basis sehr vorsichtig sein (in diesem Fall:$10$) in Bezug auf den Modul.

Insbesondere Ihre Wahl von $10$ist sehr arm. Beachten Sie, dass$10^{32}=2^{32}\cdot 5^{32}$, damit $10^{32} \textrm{ mod } 2^{32} = 0$. Dies bedeutet, dass nur die letzten$32$ Zeichen der Zeichenfolge werden im Hash berücksichtigt, sodass eine Eingabe erstellt werden kann, für die Ihr Algorithmus eine sehr schlechte Leistung erbringt.

Lassen Sie den Heuhaufen eine Kette von sein $m$ $1$'s, dh $1111111\ldots$ und die Nadel eine Schnur bestehend aus $n$ $1$eins $0$, und dann $32$ $1$'s. Weil die Zeichenfolge mit endet$32$ $1$Jede Position führt zu einem falschen Treffer, und der Algorithmus muss eine Schleife durchlaufen $n$ $1$Bevor Sie auf eine Null stoßen, erhalten Sie eine $\Omega(nm)$ Laufzeit.

Ich habe Ihren Algorithmus an einer Eingabe getestet, an der $n=3000,m=n^2=9\cdot 10^6$. Es dauerte$18$ Sekunden, um auf einem Eingang zu laufen, der mit endete $32$ Einsen, aber nur $200ms$ für eine Zeichenfolge, die auf endet $31$ $1$'s.

Das Problem ist, dass $10$ist nicht relativ prim zum Modul. Zum Beispiel nehmen$9$ da die Basis Ihr Programm viel besser macht, nur nehmen $200ms$ für den Fall mit $32$ $1$'s. Natürlich löst die Verwendung eines Primmoduls dieses Problem teilweise, da die Basis automatisch relativ prim ist. Dies ist jedoch nicht der einzige Grund, einen Primzahlmodul zu bevorzugen.

Nun, auch wenn der Modul $n$ und Basis $b$sind relativ erstklassig, unerwünschte Dinge können immer noch passieren. Zum Beispiel gibt es eine$k$ für welche $b^k=1\textrm{ mod } n$. Es ist unerwünscht für$k$ klein sein, da die Hash-Funktion nicht jeden unterscheiden kann $i^\textrm{th}$ Charakter von jedem $i+k^\textrm{th}$Charakter. In mathematischen Begriffen möchten Sie die Reihenfolge von$b$ mod $n$ so groß wie möglich sein.

Die Reihenfolge von $b$ mod $n$ ist immer höchstens die Euler-Phi-Funktion $\phi(n)$. Für eine Primzahl$p$, $\phi(p)=p-1$ während für Nicht-Primzahlen $n$es wird kleiner sein. Also nehmen$n$ eine Primzahl zu sein, erlaubt mehr von den Werten von $b^k$um nützlich zu sein". Idealerweise sollte man nehmen$b$ ein primitives Wurzelmodulo sein $n$, das zu machen $b^k=1 \textrm{ mod } n$ gilt nicht für einen Wert von $0<k<\phi(n)$.

Beachten Sie, dass Sie immer Instanzen erstellen können, für die die Leistung schlecht ist. Um sich vor "Angriffen" durch einen Gegner zu schützen, müssen Sie die Basis und den Modul als zufällige Werte verwenden.