Warum wird die Basis zur Berechnung von Hashes in Rabin-Karp-Primzahlen immer verwendet?

Der Rabin-Karp-String-Matching-Algorithmus erfordert eine Hash-Funktion, die schnell berechnet werden kann. Eine häufige Wahl ist

$$h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i,$$ wo $b$ist prime (alle Berechnungen sind Module$2^w$, wo $w$ist die Breite eines Maschinenwortes). Warum ist es wichtig für$b$ Prime sein?

Eine kurze Zusammenfassung zuerst. Wir suchen ein Muster$P[1\ldots m]$ in einer Zeichenfolge $S[1\ldots n]$. Der Rabin-Karp-Algorithmus definiert dazu eine Hash-Funktion$h$. Wir berechnen$h(P)$ (das heißt, der Hash des Musters) und Vergleich mit $h(S[1\ldots m])$, $h(S[2\ldots m+1])$und so weiter. Wenn wir einen passenden Hash finden, ist dies ein potenzieller passender Teilstring.

Die Effizienz des Algorithmus hängt von der Rechenfähigkeit ab $h(S[r+1\ldots s+1])$ effizient aus $h(S[r\ldots s])$. Dies wird als "rollender Hash" bezeichnet. Beachten Sie, dass jede effiziente Rolling-Hash-Funktion ausreicht und es sich immer noch um Rabin-Karp handelt. Die Frage, die Sie stellen, ist eine bestimmte Auswahl der Hash-Funktion, bei der Sie Folgendes verwenden:

$$h(S[r\ldots s]) = \sum_{i=r}^s S[i]\, p^{s-i} \bmod q$$

wo $p$ ist eine Primzahl mit ungefähr der gleichen Größenordnung wie die Größe des Zeichensatzes und $q$ist eine weitere Primzahl, die die Kardinalität des Bereichs der Hash-Funktion definiert, typischerweise in der gleichen Größenordnung wie ein Maschinenwort geteilt durch die Zeichensatzgröße. Wenn ich es richtig lese, fragst du warum$q$ muss prim sein.

In der Tat ist dies eine allgemeinere Frage. In vielen alten (und aktuellen) Literatur zum Thema Hashing wird empfohlen, die Hash-Funktion modulo als Primzahl zu verwenden (z. B. sollten Hash-Tabellen eine Primzahl haben).

Damit eine Hash-Funktion so nützlich wie möglich ist, muss ihr Bereich relativ gleichmäßig sein, auch wenn ihre Domäne dies nicht ist. Text in natürlicher Sprache (sagen wir) hat keine einheitliche Häufigkeitsverteilung, aber Hash-Werte sollten es sein.

Wenn $q$ ist eine Primzahl, dann sind viele andere Zahlen relativ prim dazu, und insbesondere die Summe (besonders wenn $p$ist auch Prime!). Dies macht die Häufigkeitsverteilung der Hash-Werte gleichmäßiger, obwohl die Hash-Funktion relativ schwach ist.

Es ist wichtig zu verstehen, dass wir dies tun, da die Hash-Funktion schwach ist. Wenn die Hash-Funktion stärker wäre, wäre es nicht notwendig, den Rest zu nehmen, wenn er durch eine Primzahl geteilt wird. Sie könnten zum Beispiel den Rest nehmen, wenn er durch eine Zweierpotenz geteilt wird, was eine viel billigere Bitmaskenoperation wäre. Es ist jedoch schwierig, starke rollende Hash-Funktionen zu entwerfen, die billig genug sind, um für jedes Eingabezeichen im Rabin-Karp-Algorithmus ausgeführt zu werden.

Es ist erwähnenswert, dass diese "Rest einer Prime" -Technik in vielen Hashing-Anwendungen üblich war, aber dieser Rat ist bei moderner Hardware nicht ratsam. Es war einmal sinnvoll, Ratschläge zu erteilen, denn während die Anweisung zur endgültigen Ganzzahldivision immer teuer war, waren es auch die Operationen, mit denen Sie Ihre Hash-Funktion berechnet haben, wie beispielsweise die Ganzzahlmultiplikation. Auf modernen CPUs ist es viel teurer, eine Ganzzahldivision durchzuführen, als eine Ganzzahlmultiplikation.

Moderne Carry-Save-Addierer-Multiplikatoren sind vollständig per Pipeline verbunden, sodass mehrere solcher Anweisungen gleichzeitig ausgeführt werden können. Moderne Teiler verwenden die SPH- oder Goldschmidt-Algorithmen, die mehrzyklisch und unmöglich zu leiten sind. Goldschmidt-Teiler binden auch die Multiplikationseinheit zusammen, wodurch die Leistung noch größer wird.

Ich hatte Programme, bei denen diese Teilungsanweisung der Engpass war, und der ärgerliche Teil war, dass sie in der Standardbibliothek versteckt war.

Auf einer modernen CPU lohnt es sich, eine ausgefeiltere Hash-Funktion zu verwenden, die aus vollständig pipelinisierbaren Operationen (z. B. Multiplikationen oder sogar Tabellensuchen) besteht, und Hash-Tabellen zu verwenden, die Zweierpotenzen sind. Die Modulo-Operation ist also eine Bitmaske. Tun Sie alles, um diese Teilungsoperation zu vermeiden.

Nur nicht für Rabin-Karp.