Robert Sedgewick: Algorithmen

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


19. Suchen in Zeichenfolgen



Der grobe Algorithmus

Die offensichtliche Methode für das Pattern Matching, an die man sofort denkt, besteht darin, für jede mögliche Position im Text, an der das Muster passen könnte, zu prüfen, ob es tatsächlich paßt. Das folgende Programm sucht auf diese Weise nach dem ersten Auftreten eines Musters p[1..M] in einer Text-Zeichenfolge a[1..N]:

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

Das Programm verwendet einen Zeiger i, der in den Text zeigt, und einen weiteren Zeiger j, der in das Muster zeigt. Solange die beiden Zeiger auf übereinstimmende Zeichen zeigen, werden sie inkrementiert. Wenn das Ende des Musters erreicht wird (j>M), ist eine Übereinstimmung gefunden worden. Wenn i und j auf nicht übereinstimmende Zeichen zeigen, wird j so zurückgesetzt, daß es auf den Anfang des Musters zeigt, und i wird so zurückgesetzt, daß es der Verschiebung des Musters um eine Position nach rechts entspricht, um erneut die Übereinstimmung mit dem Text zu prüfen. Wenn das Ende des Textes erreicht wird (i>N), liegt keine Übereinstimmung vor. Wenn das Muster nicht im Text auftritt, wird der Wert N + 1 zurückgegeben.

Bei einer Anwendung beim Editieren von Texten wird die innere Schleife dieses Programms selten durchlaufen, und die Laufzeit ist näherungsweise proportional zur Anzahl der untersuchten Textzeichen. Nehmen wir zum Beispiel an, daß wir das Muster STING in der Text-Zeichenfolge

A STRING SEARCHING EXAMPLE CONSISTING OF ...

suchen. Dann wird die Anweisung j:=j+1 nur viermal ausgeführt (einmal für jedes S, jedoch zweimal für das erste ST), bevor die wirkliche Übereinstimmung gefunden wird.

Andererseits kann die grobe Suche für manche Muster sehr langsam sein, zum Beispiel dann, wenn der Text binär (aus zwei Zeichen gebildet) ist, wie dies für Anwendungen bei der Bildverarbeitung und Systemprogrammierung der Fall sein kann. Abbildung 19.1 zeigt, was geschieht, wenn der Algorithmus verwendet wird, um in einer langen binären Text-Zeichenfolge nach dem Muster 10100111 zu suchen. Jede Zeile (mit Ausnahme der letzten, welche die Übereinstimmung zeigt) besteht aus null oder mehr übereinstimmenden Zeichen, denen eine Nicht-Übereinstimmung folgt. Dies sind die »Fehlstarts«, die bei der Suche nach dem Muster erfolgen; ein offensichtliches Ziel bei der Entwicklung von Algorithmen besteht in dem Versuch, die Anzahl und Länge dieser »Fehlstarts« zu begrenzen. In diesem Beispiel werden im Durchschnitt für jede Textposition ungefähr zwei Zeichen im Muster geprüft, obwohl die Situation wesentlich ungünstiger sein kann.

Abbildung 19.1
Abbildung 19.1 Grobes Suchen in Zeichenfolgen in einem binären Text.

Eigenschaft 19.1 Beim groben Suchen in Zeichenfolgen können ungefähr NM Zeichenvergleiche erforderlich sein.

Der ungünstigste Fall liegt vor, wenn sowohl das Muster als auch der Text ausschließlich aus Nullen und einer 1 in der letzten Stelle bestehen. Dann werden für jede der N - M + 1 Positionen, in denen Übereinstimmung möglich wäre, alle Zeichen im Muster mit dem Text verglichen, mit einem Gesamtaufwand von M(N - M + 1). Normalerweise ist M sehr klein im Vergleich zu N, so daß die Gesamtzahl ungefähr NM beträgt. w.z.b.w.

Derartige entartete Zeichenfolgen sind sicher im normalen Text (oder in Pascal) nicht wahrscheinlich, doch sie können durchaus auftreten, wenn binäre Texte verarbeitet werden, so daß wir nach besseren Algorithmen suchen.


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