Robert Sedgewick: Algorithmen

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


19. Suchen in Zeichenfolgen



Der Algorithmus von Boyer-Moore

Wenn das Rücksetzen nicht kompliziert ist, kann eine bedeutend schnellere Suchmethode entwickelt werden, indem das Muster von rechts nach links durchsucht wird, wenn versucht wird, es mit dem Text in Übereinstimmung zu bringen. Wenn wir nach unserem Beispiel-Muster 10100111 suchen, so können wir, wenn wir Übereinstimmungen beim achten, siebenten und sechsten Zeichen, nicht aber beim fünften feststellen, das Muster sofort um sieben Positionen nach rechts verschieben und das fünfzehnte Zeichen als nächstes überprüfen, da bei unserer teilweisen Übereinstimmung 111 gefunden wurde, was anderswo im Muster nicht auftritt. Natürlich kommt das Endstück im allgemeinen Fall anderswo wieder vor, so daß wir wie oben eine Tabelle next benötigen.

Abbildung 19.6 zeigt eine »Von-rechts-nach-links«-Variante der Tabelle next für das Muster 10110101: In diesem Fall ist next[j] die Anzahl der Zeichenpositionen, um die das Muster nach rechts verschoben werden kann, wenn bei einem Durchsuchen von hinten eine Nichtübereinstimmung beim j-ten Zeichen von rechts im Muster auftrat. Ähnlich wie zuvor bestimmen wir diesen Wert, indem wir zwei Kopien des Musters übereinander legen, wobei anfangs das vorletzte Zeichen unter dem letzten Zeichen liegt. Dann verschieben wir die untere Kopie solange nach rechts, bis die letzten j - 1 Zeichen der oberen Kopie mit den sie überlappenden Zeichen der unteren Kopie übereinstimmen und das j-letzte Zeichen, das ja die Nicht-Übereinstimmung verursachte, nicht mit dem es überlappenden Zeichen übereinstimmt. Zum Beispiel ist next[3]=7, weil, wenn bei einem Durchsuchen von rechts nach links eine Übereinstimmung der letzten zwei Zeichen und dann eine Nichtübereinstimmung vorlag, im Text 001 vorgefunden worden sein muß; dies tritt im Muster nicht auf, außer möglicherweise dann, wenn die 1 auf einer Höhe mit dem ersten Zeichen im Muster liegt, so daß wir um 7 Positionen nach rechts verschieben können.

Abbildung 19.6
Abbildung 19.6 Wiederaufsetzpositionen für die Suche nach Boyer-Moore.

Dies führt unmittelbar zu einem Programm, welches der obigen Implementation der Methode von Knuth-Morris-Pratt sehr ähnlich ist. Wir gehen hierauf nicht ausführlicher ein, da es einen völlig anderen Weg gibt, beim Durchsuchen von Mustern von rechts nach links Zeichen zu überspringen, der in vielen Fällen weit besser ist.

Die Idee besteht darin, die Entscheidung über den nächsten Schritt sowohl auf der Basis des die Nicht-Übereinstimmung verursachenden Zeichens im Text als auch auf der Basis des Musters zu treffen. Der der Verarbeitung vorausgehende Schritt besteht darin, für jedes mögliche Zeichen, das im Text auftreten könnte, zu bestimmen, was wir tun würden, wenn dieses Zeichen die Nichtübereinstimmung verursachen würde. Die einfachste Realisierung dieses Gedankens führt unmittelbar zu einem sehr nützlichen Programm.

Abbildung 19.7 zeigt diese Methode für unseren ersten Beispiel-Text. Indem wir bei der Prüfung auf Übereinstimmung mit dem Muster von rechts nach links vorgehen, vergleichen wir zuerst das G im Muster mit dem R (dem fünften Zeichen) im Text. Sie stimmen nicht nur nicht überein, sondern wir können sogar feststellen, daß R nirgends im Muster auftritt, so daß wir das Muster sofort ganz an dem R vorbeischieben können. Der nächste Vergleich wird zwischen dem G im Muster und dem fünften Zeichen nach dem R (dem S in SEARCHING) vorgenommen. Diesmal können wir das Muster soweit nach rechts schieben, daß das S im Muster mit dem S im Text übereinstimmt. Danach wird das G im Muster mit dem C in SEARCHING verglichen, welches im Muster nicht auftritt, so daß das Muster um weitere fünf Positionen nach rechts verschoben werden kann. Nach drei weiteren jeweils fünf Zeichen umfassenden Sprüngen gelangen wir zum T in CONSISTING, wo wir das Muster so ausrichten, daß das T in ihm mit dem T im Text übereinstimmt, und die vollständige Übereinstimmung feststellen. Diese Methode führt uns unmittelbar zur Position der Übereinstimmung, wobei nur sieben Zeichen im Text untersucht werden müssen (und fünf weitere, um die Übereinstimmung zu prüfen)!

Abbildung 19.7
Abbildung 19.7 Suche nach Boyer-Moore unter Verwendung
der heuristischen Methode der nicht übereinstimmenden Zeichen.

Dieser Algorithmus l&auuml;ßt sich sehr leicht implementieren. Dazu wird ein grobes Durchsuchen des Musters von rechts nach links einfach dadurch verbessert, daß ein Feld skip initialisiert wird, welches für jedes Zeichen im Alphabet angibt, wie weit zu springen ist, wenn dieses Zeichen im Text auftritt und eine Nichtübereinstimmung während der Suche verursacht. Für jedes Zeichen, das möglicherweise im Text erscheinen könnte, muß ein Eintrag in skip vorhanden sein. Der Einfachheit halber nehmen wir an, daß wir eine Funktion function index(c: char): integer; haben, die 0 für Leerzeichen und i für den i-ten Buchstaben des Alphabets zurückgibt; wir nehmen weiterhin an, daß eine Prozedur procedure initskip vorliegt, die das Feld skip für alle Zeichen mit M initialisiert und dann für j von 1 bis M skip[index(p[j])] auf M - j setzt. Dann ist die Implementation sehr einfach:

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

Die Anweisung i:=i + M - j + 1 setzt i auf die nächste Position in der Text-Zeichenfolge zurück (da sich das Muster von links durch diese bewegt); danach setzt j:=M den Zeiger des Musters als Vorbereitung für den zeichenweisen Vergleich von rechts nach links zurück. Die nächste Anweisung verschiebt das Muster sogar noch weiter im Text vorwärts, wenn dies gerechtfertigt ist. Für das Muster STING lautet die Eintragung für G in skip 0, die Eintragung für N lautet 1, die für I 2, die für T 3, die für S 4. Die Eintragungen für alle anderen Buchstaben lauten 5. Somit wird zum Beispiel, wenn im Verlauf einer Suche ein S vorgefunden wird, der Zeiger i um 4 inkrementiert, so daß das Ende des Musters sich vier Positionen rechts von dem S befindet (und demzufolge das S im Muster und das S im Text übereinanderliegen). Wenn mehr als ein S im Muster vorhanden wäre, würden wir für diese Berechnung das am weitesten rechts befindliche verwenden wollen; demzufolge wird das Feld skip erzeugt, indem von links nach rechts gesucht wird.

Boyer und Moore schlugen vor, die beiden von uns skizzierten Methoden für das Durchsuchen des Musters von rechts nach links zu kombinieren und dann den größeren der zwei erforderlichen Sprünge zu wählen.

Eigenschaft 19.3 Bei der Suche gemäß dem Algorithmus von Boyer-Moore sind niemals mehr als M + N Zeichenvergleiche erforderlich, und es werden ungefähr N/M Schritte benötigt, wenn das Alphabet nicht klein und das Muster nicht lang ist.

In der gleichen Weise wie bei der Methode von Knuth-Morris-Pratt ist der Algorithmus im ungünstigsten Fall linear (die oben angegebene Implementation, die nur eine der beiden heuristischen Methoden von Boyer-Moore realisiert, ist nicht linear). Das Ergebnis W/M für den »durchschnittlichen Fall« kann für verschiedene Modelle zufälliger Zeichenfolgen bewiesen werden, doch sind diese meist unrealistisch, so daß wir auf die Einzelheiten verzichten. In vielen praktischen Situationen gilt, daß alle Zeichen des Alphabets mit Ausnahme einiger weniger nirgends im Muster erscheinen, so daß jeder Vergleich dazu führt, daß M Zeichen übersprungen werden, wodurch sich die Behauptung ergibt. w.z.b.w.

Der Algorithmus der nicht übereinstimmenden Zeichen nützt offenbar für binäre Zeichenfolgen nicht viel, da es hier nur zwei Möglichkeiten für Zeichen gibt, die die Nichtübereinstimmung verursachen (und diese treten beide wahrscheinlich im Muster auf). Die Bits können jedoch zu Gruppen zusammengefaßt werden, um »Zeichen« zu bilden, die genau wie oben benutzt werden können. Wenn wir jeweils b Bits nehmen, benötigen wir eine Tabelle skip mit 2b Einträgen. Der Wert von b sollte genügend klein gewählt werden, so daß diese Tabelle nicht zu groß ist, aber groß genug dafür, daß die meisten der aus b Bits bestehenden Abschnitte des Textes wahrscheinlich nicht im Muster auftreten. Insbesondere gibt es M - b + 1 verschiedene, aus b Bits bestehende Abschnitte im Muster (bei jeder Bitposition von 1 bis M - b + 1 beginnt jeweils einer), so daß es wünschenswert ist, daß M - b + 1 wesentlich kleiner als 2b ist. Wenn wir zum Beispiel b ungefähr lg(4M) wählen, so wird die Tabelle skip zu mehr als drei Vierteln mit M gefüllt. Ebenso muß b kleiner als M/2 sein, da wir andernfalls das Muster ganz verpassen könnten, wenn es zwischen zwei b Bits umfassenden Textabschnitten aufgeteilt wäre.


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