Robert Sedgewick: Algorithmen

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


19. Suchen in Zeichenfolgen



Der Algorithmus von Knuth-Morris-Pratt

Die Idee, die dem von Knuth, Morris und Pratt entdeckten Algorithmus zugrunde liegt, ist folgende: Wenn eine Nichtübereinstimmung festgestellt wird, besteht unser »Fehlstart« aus Zeichen, die wir bereits kennen (da sie sich im Muster befinden). Irgendwie sollte es uns gelingen, aus dieser Information einen Vorteil zu ziehen, anstatt den Zeiger i über alle diese bekannten Zeichen hinweg zurückzusetzen.

Um ein einfaches Beispiel hierfür zu betrachten, werde angenommen, daß das erste Zeichen im Muster nicht noch einmal im Muster erscheint (das Muster sei zum Beispiel 10000000). Nehmen wir weiterhin an, daß an einer gewissen Position im Text ein Fehlstart erfolgt, der sich über j Zeichen erstreckt. Wenn die Nichtübereinstimmung festgestellt wird, wissen wir aufgrund der Tatsache, daß bei j Zeichen Übereinstimmung vorlag, daß wir den Text-Zeiger i nicht »zurückzusetzen« brauchen, da keines der vorangehenden j - 1 Zeichen im Text mit dem ersten Zeichen im Muster übereinstimmen kann. Diese Änderung könnte implementiert werden, indem i:=i - j + 2 im obigen Programm weggelassen wird. Die praktische Auswirkung dieser Änderung ist begrenzt, da das Auftreten eines solchen speziellen Musters nicht besonders wahrscheinlich ist, doch es lohnt sich, über diese Idee nachzudenken. Der Algorithmus von Knuth-Morris-Pratt stellt eine Verallgemeinerung dieses Falles dar. Erstaunlicherweise ist es immer möglich, es so einzurichten, daß der Zeiger i nie dekrementiert wird.

Ein vollständiges Überspringen des Musters bei Feststellung einer Nichtübereinstimmung, wie es im vorigen Absatz beschrieben wurde, führt nicht zum Ziel, wenn das Muster an der Stelle der Nichtübereinstimmung mit sich selbst in Übereinstimmung gebracht werden könnte. Wenn wir zum Beispiel in 1010100111 nach 10100111 suchen, stellen wir die Nichtübereinstimmung zuerst beim fünften Zeichen fest. Wir müssen jedoch beim dritten Zeichen wiederaufsetzen, um die Suche fortzusetzen, da wir andernfalls die Übereinstimmung verpassen würden. Doch wir können im voraus exakt ausrechnen, was zu tun ist, da dies nur vom Muster abhängt, wie Abbildung 19.2 zeigt.

Abbildung 19.2
Abbildung 19.2 Wiederaufsetzposition für die Suche nach Knuth-Morris-Pratt.

Das Feld next[1..M] wird verwendet, um zu bestimmen, wie weit zurückzukehren ist, wenn eine Nichtübereinstimmung festgestellt wird. Stellen wir uns vor, daß wir eine Kopie der ersten j - 1 Zeichen des Musters unter sich selbst legen, wobei das erste Zeichen anfangs unter dem zweiten liegt. Dann verschieben wird die untere Kopie soweit nach rechts, bis alle sich überlappenden Zeichen übereinstimmen oder sich keine Zeichen mehr überlappen (Die schattierten Zeichen gehören nicht zu der Kopie, sondern sind nur zur Veranschaulichung aufgeführt). Diese übereinanderliegenden Zeichen definieren die nächste mögliche Stelle, wo das Muster passen könnte, wenn eine Nichtübereinstimmung an der Stelle p[j] festgestellt wird. Die Entfernung (next[j]), um die im Muster zurückzukehren ist, ist genau gleich eins plus der Anzahl der übereinanderliegenden Zeichen. Insbesondere ist für j>1 der Wert von next[j] gleich dem maximalen k < j, für das die ersten k - 1 Zeichen des Musters mit den letzten k - 1 Zeichen der ersten j - 1 Zeichen des Musters übereinstimmen. Wie wir bald sehen werden, ist es zweckmäßig, next[1] per Definition gleich Null zu setzen.

Dieses Feld next liefert unmittelbar einen Weg zur Begrenzung (in Wirklichkeit, wie wir sehen werden, zur Beseitigung) der oben besprochenen Rücksetzung des Text-Zeigers i. Wenn i und j auf nicht übereinstimmende Zeichen zeigen (bei der Prüfung auf Übereinstimmung mit dem Muster, beginnend bei Position i - j + 1 in der Text-Zeichenfolge), so beginnt die nächste mögliche Position für eine Übereinstimmung mit dem Muster bei Position i - next[j] + 1. Doch laut Definition der Tabelle next stimmen die ersten next[j] - 1 Zeichen in dieser Position mit den ersten next[j] - 1 Zeichen des Musters überein, so daß es nicht notwendig ist, den Zeiger i so weit zurückzusetzen; wir können den Zeiger i einfach unverändert lassen und den Zeiger j auf next[j] setzen:

    function kmpsearch: integer;
      var i,j: integer;
      begin
      i:=1; j:=1; initnext;
      repeat
        if (j=0) or (a[i]=p[j])
          then begin i:=i+1; j:=j+1 end
          else begin j:=next[j] end;
      until (j>M) or (i>N);
      if j>M then kmpsearch:=i-M else kmpsearch:=i;
      end;

Wenn j = 1 ist und a[i] nicht mit dem Muster übereinstimmt, so gibt es keine übereinanderliegenden Zeichen, so daß wir i inkrementieren und j auf den Anfang des Musters zurücksetzen. Dies wird erreicht, indem next[1] per Definition gleich Null gesetzt wird, was zur Folge hat, daß j auf 0 gesetzt wird; danach wird i inkrementiert, und j wird beim nächsten Schleifendurchlauf auf 1 gesetzt. (Damit dieser Trick funktioniert, muß das Feld für das Muster als bei 0 beginnend deklariert werden, da andernfalls Standard-Pascal bei j = 0 eine »Unterschreitung eines Bereichs« signalisieren würde, auch wenn eigentlich nicht auf p[0] zugegriffen werden muß, um den Wahrheitsgehalt der or-Bedingung zu ermitteln.) In funktioneller Hinsicht ist dieses Programm das gleiche wie brutesearch, doch es läuft für Muster, die in hohem Maße »selbstwiederholend« sind, sicherlich schneller ab.

Nun muß noch die Tabelle next berechnet werden. Das Programm hierfür ist elegant: Dem Wesen nach ist es das gleiche Programm wie oben, doch wird das Muster auf Übereinstimmung mit sich selbst geprüft:

    procedure initnext;
      var i,j: integer;
      begin
      i:=1; j:=0; next[1]:=0;
      repeat
        if (j=0) or (p[i]=p[j])
          then begin i:=i+1; j:=j+1; next[i]:=j end
          else begin j:=next[j] end;
      until i>=M;
      end;
Unmittelbar nachdem i und j inkrementiert worden sind steht fest, daß die ersten j - 1 Zeichen des Musters mit den Zeichen in den Positionen p[i - j - 1..i - 1] übereinstimmen, den letzten j - 1 Zeichen der ersten i - 1 Zeichen des Musters. Und dies ist das größte j mit dieser Eigenschaft, da andernfalls eine »mögliche Übereinstimmung« des Musters mit sich selbst verpaßt worden wäre. Folglich ist j genau der Wert, der next[i] zugewiesen werden muß.

Eine interessante Betrachtungsweise dieses Algorithmus besteht darin, das Muster als feststehend zu betrachten, so daß die Tabelle next mit dem Programm »verdrahtet« werden kann. Zum Beispiel entspricht das folgende Programm für das von uns betrachtete Muster genau dem obigen Programm, doch ist es sicherlich wesentlich effizienter.

    i:=0;
 0: i:=i+1;
 1: if a[i]<>'1' then goto 0; i:=i+1;
 2: if a[i]<>'0' then goto 1; i:=i+1;
 3: if a[i]<>'1' then goto 1; i:=i+1;
 4: if a[i]<>'0' then goto 2; i:=i+1;
 5: if a[i]<>'0' then goto 3; i:=i+1;
 6: if a[i]<>'1' then goto 1; i:=i+1;
 7: if a[i]<>'1' then goto 2; i:=i+1;
 8: if a[i]<>'1' then goto 2; i:=i+1;
    search:=i-8;

Die goto-Marken in diesem Programm entsprechen der Tabelle next. Tatsächlich kann das obige Programm initnext, welches die Tabelle next berechnet, leicht so modifiziert werden, daß es dieses Programm erstellt! Um zu vermeiden, daß jedesmal, wenn i inkrementiert wird, geprüft werden muß, ob i<N gilt, nehmen wir an, daß das Muster selbst am Ende des Textes als Marke in a[N + 1..N +M] gespeichert ist. (Diese Optimierung könnte auch bei der standardmäßigen Implementation angewandt werden.) Dies ist ein einfaches Beispiel eines »Compilers für die Suche in Zeichenfolgen«: Zu einem gegebenen Muster können wir ein sehr effizientes Programm zur Suche nach diesem Muster in einer beliebig langen Text-Zeichenfolge erzeugen. In den nächsten beiden Kapiteln betrachten wir Verallgemeinerungen dieses Grundgedankens.

Das obige Programm verwendet nur einige sehr elementare Operationen, um das Problem der Suche in Zeichenfolgen zu lösen. Das bedeutet, daß es leicht mit Hilfe eines sehr einfachen Maschinenmodells beschrieben werden kann, einem endlichen Automaten. Abbildung 19.3 zeigt den endlichen Automaten für das obige Programm.

Abbildung 19.3
Abbildung 19.3 Endlicher Automat für den Algorithmus von Knuth-Morris-Pratt.

Der Automat besteht aus Zuständen (durch Ziffern in Kreisen dargestellt) und Übergängen (durch Linien dargestellt). Jeder Zustand hat zwei Übergänge, auf denen er verlassen werden kann: einen Übereinstimmungs-Übergang (durchgehende Linie, nach rechts führend) und einen Nichtübereinstimmungs-Übergang (punktierte Linie, nach links führend). Die Zustände entsprechen den Programmzeilen, die Übergänge den goto-Anweisungen. Wenn sich der Automat in dem mit der Marke x versehenen Zustand befindet, kann er nur eine Anweisung ausführen: »Falls das aktuelle Zeichen x ist, dann »durchlaufe« es und nehme den Übereinstimmungs-Übergang, andernfalls nehme den Nichtübereinstimmungs-Übergang.« Das »Durchlaufen« eines Zeichens bedeutet, daß das nächste Zeichen in der Zeichenfolge als das »aktuelle Zeichen« genommen wird; der Automat »durchläuft« Zeichen, wenn er Übereinstimmung feststellt. Hierbei gibt es zwei Ausnahmen: Im ersten Zustand wird immer ein Übereinstimmungs-Übergang genommen und zum nächsten Zeichen übergegangen (dem Wesen nach entspricht dies der Suche nach dem ersten Auftreten des ersten Zeichens im Muster), und der letzte Zustand ist ein Endzustand, der anzeigt, daß eine Übereinstimmung gefunden wurde. Im folgenden Kapitel sehen wir, wie ein ähnlicher (aber leistungsfähigerer) Automat verwendet werden kann, um einen wesentlich leistungsfähigeren Algorithmus für das Pattern Matching entwickeln zu helfen.

Der aufmerksame Leser wird bemerkt haben, daß es in diesem Algorithmus immer noch Verbesserungsmöglichkeiten gibt, da er nicht das Zeichen berücksichtigt, welches die Nichtübereinstimmung verursachte. Nehmen wir zum Beispiel an, daß unser Text mit 1011 beginnt und wir unser Beispiel-Muster 10100111 suchen. Nach der Übereinstimmung in 101 stellen wir eine Nichtübereinstimmung beim vierten Zeichen fest; an dieser Stelle besagt die Tabelle next, daß nun das zweite Zeichen des Musters mit dem vierten Zeichen des Textes zu vergleichen ist, da, ausgehend von der Übereinstimmung in 101, das erste Zeichen des Musters zum dritten Zeichen des Textes verschoben werden kann (doch wir brauchen diese Zeichen nicht zu vergleichen, da wir wissen, daß sie beide 1 sind). An dieser Stelle kann jedoch keine Übereinstimmung vorliegen: Aufgrund der Nichtübereinstimmung wissen wir, daß das nächste Zeichen im Text nicht 0 ist, wie es das Muster fordert. Eine andere Betrachtungsweise hierzu besteht darin, die Variante des Programms mit der »verdrahteten« Tabelle next zu untersuchen: Bei Marke 4 gehen wir zu 2, falls a[i] nicht 0 ist, doch bei Marke 2 gehen wir zu 1, falls a[i] nicht 0 ist. Warum geht man nicht einfach direkt zu 1? Abbildung 19.4 zeigt die verbesserte Variante des endlichen Automaten für unser Beispiel.

Abbildung 19.4
Abbildung 19.4 Endlicher Automat für den Algorithmus von Knuth-Morris-Pratt (verbessert).

Zum Glück ist es einfach, diese Änderung im Algorithmus vorzunehmen. Wir müssen nur die Anweisung next[i]:=j im Programm initnext durch

    if p[j]<>p[i] then next[i]:=j else next[i]:=next[j];

ersetzen. Da wir von links nach rechts vorgehen, ist der benötigte Wert von next bereits berechnet worden, so daß wir ihn einfach benutzen.

Eigenschaft 19.2 Bei der Suche in Zeichenfolgen gemäß dem Algorithmus von Knuth-Morris-Pratt sind niemals mehr als M + N Zeichenvergleiche erforderlich.

Diese Eigenschaft wird in Abbildung 19.5 veranschaulicht; sie ist auch vom Programm her offensichtlich: Entweder inkrementieren wir j, oder wir setzen es mittels der Tabelle next zurück, und zwar höchstens einmal für jedes i. w.z.b.w.

Abbildung 19.5
Abbildung 19.5 Suche nach Knuth-Morris-Pratt in einem binären Text.

Abbildung 19.5 zeigt, daß diese Methode sicherlich für unser binäres Beispiel weit weniger Vergleiche verwendet als die grobe Methode. In vielen realen Anwendungen ist der Algorithmus von Knuth-Morris-Pratt jedoch nicht nennenswert schneller als die grobe Methode, da nur wenige Anwendungen das Suchen nach Mustern mit einem hohen Grad an Selbstwiederholung in einem Text mit einem hohen Grad an Selbstwiederholung erfordern. Trotzdem hat das Verfahren einen wichtigen praktischen Vorteil: Es durchläuft die Eingabedaten sequentiell und kehrt niemals innerhalb der Eingabedaten »zurück«. Dadurch ist es für Fälle geeignet, wo eine umfangreiche Datei von irgendeinem externen Gerät eingelesen wird. (Algorithmen, die ein Rücksetzen erfordern, benötigen in dieser Situation eine komplizierte Pufferung.)


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