Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


19. Suchen in Zeichenfolgen



Der Algorithmus von Rabin-Karp

Ein grober Ansatz für die Suche in Zeichenfolgen, den wir oben noch nicht betrachtet haben, wäre, sehr viel Speicher zu benutzen und jeden möglichen, aus M Zeichen bestehenden Abschnitt des Textes als einen Schlüssel in einer standardmäßigen Hash-Tabelle zu behandeln. Es ist jedoch nicht erforderlich, eine ganze Hash-Tabelle abzuspeichern, da das Problem so geartet ist, daß nur ein Schlüssel gesucht wird; alles, was wir zu tun haben, ist, für jeden der möglichen aus M Zeichen bestehenden Abschnitte des Textes die Hash-Funktion zu berechnen und zu prüfen, ob sie gleich der Hash-Funktion des Musters ist. Das Problem bei dieser Methode ist, daß es zunächst ebenso schwierig zu sein scheint, die Hash-Funktion für M Zeichen aus dem Text zu berechnen, wie nur zu prüfen, ob diese Zeichen mit dem Muster übereinstimmen. Rabin und Karp fanden einen einfachen Weg zur Überwindung dieser Schwierigkeit, und zwar für die Hash-Funktion, die wir in Kapitel 16 verwendeten: h(k) = k mod q, wobei q (die Größe der Tabelle) eine große Primzahl ist. In diesem Falle wird nichts in der Hash-Tabelle gespeichert, daher kann q sehr groß gewählt werden.

Die Methode beruht auf der Berechnung der Hash-Funktion für die Position i im Text, wenn ihr Wert für die Position i - 1 gegeben ist, und sie folgt praktisch unmittelbar aus der mathematischen Formulierung. Nehmen wir an, daß wir unsere M Zeichen in Zahlen umwandeln, indem wir sie zu einem Computerwort zusammenfassen, welches wir dann als eine ganze Zahl behandeln. Dies entspricht der Schreibweise der Zeichen als Zahlen in einem Zahlensystem mit der Basis d, wobei d die Anzahl der möglichen Zeichen ist. Die a[i..i + M - 1] entsprechende Zahl ist folglich

x = a[i]dM-1 + a[i+1]dM-2 + ... + a[i+M-1],

und wir können annehmen, daß wir den Wert von h(x) = x mod q kennen. Das Verschieben um eine Position im Text nach rechts entspricht jedoch einfach dem Ersetzen von x durch

(x - a[i]M-1)d + a[i+M].

Eine grundlegende Eigenschaft der Operation mod ist, daß wir sie jederzeit während dieser Operationen ausführen können und stets das gleiche Ergebnis erhalten. Anders gesagt, wenn wir nach jeder arithmetischen Operation den Rest nehmen, der bei der Division durch q bleibt (um die Zahlen, mit denen wir operieren, klein zu halten), so erhalten wir das gleiche Ergebnis, wie wenn wir alle arithmetischen Operationen ausführen und danach den Rest nehmen, der bei der Division durch q bleibt.

Dies führt zu dem sehr einfachen Algorithmus des Pattern Matching, der nachstehend implementiert ist. Für das Programm wird die gleiche Funktion index wie oben angenommen, im Interesse der Effizienz wird jedoch d = 32 verwendet (die Multiplikationen könnten dann als Verschiebungen implementiert werden).

    function rksearch: integer;
      const q=33554393; d=32;
      var h1,h2,dM,i: integer;
      begin
      dM:=1; for i:=1 to M-1 do dM:=(d*dM) mod q;
      h1:=0; for i:=1 to M do h1:=(h1*d+index(p[i])) mod q;
      h2:=0; for i:=1 to M do h2:=(h2*d+index(a[i])) mod q;
      i:=1;
      while (h1<>h2) and (i<=N-M) do
        begin
        h2:=(h2+d*q-index(a[i])*dM) mod q;
        h2:=(h2*d+index(a[i+M])) mod q;
        i:=i+1;
        end;
      rksearch:=i;
      end;

Das Programm berechnet zuerst einen Hash-Wert h1 für das Muster, danach einen Hash-Wert h2 für die ersten M Zeichen des Textes. (Es berechnet auch den Wert von dM-1 mod q in der Variablen dM.) Dann durchläuft es die Text-Zeichenfolge, wobei es die obige Methode zur Berechnung der Hash-Funktion für die M Zeichen benutzt, beginnend bei der Position i (für jedes i), und wobei es jeden neuen Hash-Wert mit h1 vergleicht. Die Primzahl q wird so gewählt, daß sie möglichst groß ist, jedoch nicht so groß, daß (d - 1) * q einen Überlauf hervorruft; dies erfordert weniger Operationen mod, als wenn wir die größte darstellbare Primzahl verwenden würden. (Während der Berechnung von h2 wird ein zusätzliches d * q addiert, um zu gewährleisten, daß alles positiv bleibt, so daß die Operation mod wie gewünscht ausgeführt wird.)

Eigenschaft 19.4 Das Pattern Matching nach Rabin-Karp ist in den allermeisten Fällen linear.

Dieser Algorithmus benötigt offensichtlich eine Zeit, die proportional zu N + M ist, doch es muß angemerkt werden, daß er in Wirklichkeit nur eine Position im Text findet, welche den gleichen Hash-Wert wie das Muster hat. Um sicherzugehen, sollten wir unbedingt noch einen direkten Vergleich des betreffenden Textes mit dem Muster vornehmen. Jedoch bewirkt die Verwendung eines sehr großen Wertes von q - die durch die Berechnungen mit mod und die Tatsache, daß wir die eigentliche Hash-Tabelle nicht führen müssen - ermöglicht wird, daß es äußerst unwahrscheinlich ist, daß eine Kollision auftritt. Theoretisch könnte dieser Algorithmus in dem (unwahrscheinlichen) ungünstigsten Fall dennoch O(NM) Schritte benötigen, doch in der Praxis kann man sich darauf verlassen, daß ungefähr N + M Schritte erforderlich sind. w.z.b.w.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]