Baeza-Yates-Gonnet-Algorithmus

(Weitergeleitet von Shift-Or-Algorithmus)

Der Baeza-Yates-Gonnet-Algorithmus bzw. Shift-or-Algorithmus, der auch unter den Namen Shift-and oder Bitap bekannt ist, löst das String-Matching-Problem, indem er einen nichtdeterministischen Automaten simuliert. Unter anderem wird eine Abwandlung dieses Algorithmus bei dem Unix-Tool grep benutzt.

Da die Implementierung auf Bit-Operationen zurückgeführt werden kann, ist der Algorithmus alleine von der Ausführung her bereits sehr effizient. Kombiniert man dies mit dem zu Grunde liegenden System (im Preprocessing einmal Schleife über das Muster, während der Suche einmal Schleife über den Text) ergibt sich ein extrem effizienter Algorithmus.

Grundlage

Bearbeiten

Grundlage des Algorithmus bildet eine Menge von Vektoren   mit folgender Definition:

 

Anschaulich bedeutet dies, dass   genau dann   ist, wenn nach der Verarbeitung von   Zeichen des Textes die letzten   Zeichen mit den ersten   Zeichen des Suchmusters übereinstimmen.

Ein Treffer für ein Suchmuster mit Länge   ist demnach gefunden, falls  .

Weiterhin werden die charakteristischen Vektoren für alle möglicherweise im Text vorkommenden Zeichen benötigt:

 

Beispiel:

Suchmuster  , Länge  

Charakteristische Vektoren:

 

Ablauf (exaktes Matching)

Bearbeiten

Um den Ablauf zu vereinfachen, wird zunächst eine spezielle Bit-Operation Bitshift bzw.   für den Vektor   eingeführt:  

Der Algorithmus für exakte Übereinstimmungen lässt sich nun auf wenige einfache Schritte reduzieren:

  1. Initialisiere den  -Vektor mit 0 (für alle Positionen) und beginne mit dem ersten Zeichen des zu durchsuchenden Textes
  2. Verschiebe alle Bits in   mittels Bitshift um eine Position nach rechts.
  3. Führe eine  -Verknüpfung von   und dem charakteristischen Vektor des aktuellen Textzeichens durch.
  4. Gehe zum nächsten Textzeichen. Falls Ende erreicht, breche ab, sonst gehe zu (2)

Die Schritte (2) und (3) führen bei genauer Betrachtung genau die Berechnungsvorschrift für   aus: Durch das Shiften wird aus dem „alten“   das Zeichen an Stelle   an die Stelle   angelegt (entspricht in Kombination mit   der Bedingung  ). Der charakteristische Vektor des aktuellen Textzeichens enthält an der Stelle   genau dann eine  , falls Muster und Text hier übereinstimmen. Durch das   werden beide Bedingungen verknüpft.

Beispiel (exaktes Matching)

Bearbeiten

Muster:  ,  

Text:  

 

Da   liegt ein Treffer bei   (Position − Musterlänge + Korrektur für erstes Zeichen) vor.

Erweiterung (approximatives Matching)

Bearbeiten

Der Algorithmus kann durch leichte Modifikationen eine fehlertolerante Suche durchführen. Hierfür wird der Vektor   aufgeteilt:

  1.  : entspricht dem vorherigen  ; Der Index   steht für die Anzahl der aufgetretenen Fehler.
  2.  : Bezeichnet einen  -Vektor, der auf Treffer mit maximal einem Fehler ausgerichtet ist.
  3. ...
  4.  : Bezeichnet einen  -Vektor, der auf Treffer mit maximal   Fehlern ausgerichtet ist.

Achtung: Bei den fehlerbehafteten Vektoren ist die obige Interpretation mit „nach j Zeichen stimmen die letzten i mit den ersten i des Musters überein“ schwierig und nicht mehr unbedingt einleuchtend.

Die Berechnungsvorschrift für   bleibt unverändert. Für Fehlervektoren  wird nach der verursachenden Aktion unterschieden:

Einfügen eines Zeichens in das Suchmuster

Bearbeiten

 

Erläuterung: Der erste Teil des Ausdrucks beschreibt den Fall, dass bereits   Fehler vorhanden sind, aber das aktuelle Zeichen von Text und Muster übereinstimmen. Der zweite Teil beschreibt den Fehlerfall: Bisher (in  ) lagen nur   Fehler vor, das aktuelle Zeichen kann also in das Muster eingefügt werden.

Interpretation:  , falls nach   Zeichen der Eingabe von den letzten   Zeichen mindestens   Zeichen mit dem Suchmuster übereinstimmen und der Rest durch Einfügen der fehlenden Zeichen zur Übereinstimmung gebracht werden kann.

Löschen eines Zeichens aus dem Suchmuster

Bearbeiten

 

Erläuterung: Der erste Teil des Ausdrucks beschreibt den Fall, dass bereits   Fehler vorhanden sind, aber das aktuelle Zeichen von Text und Muster übereinstimmen. Der zweite Teil beschreibt den Fehlerfall: Schaut man sich bei   Zeichen des Textes nicht die ersten   Zeichen an, sondern nur die ersten   (im Vektor die Position darüber), so stimmt das Muster bis auf   Fehler überein. Das   Zeichen des Musters wird daraufhin einfach gelöscht.

Ersetzen eines Zeichens im Muster

Bearbeiten

 

Erläuterung: Der erste Teil des Ausdrucks beschreibt den Fall, dass bereits   Fehler vorhanden sind, aber das aktuelle Zeichen von Text und Muster übereinstimmen. Der zweite Teil beschreibt den Fehlerfall: Nach   Zeichen stimmten die letzten   Zeichen überein. Ersetzt man nun also das   Zeichen im Muster durch das   Zeichen des Textes, stimmen auch nach   Zeichen die letzten   Zeichen mit den ersten   Zeichen des „neuen“ Musters überein.

Die Varianten können mittels bitweisem oder beliebig verknüpft werden.

Literatur

Bearbeiten
  • Ricardo A. Baeza-Yates, Gaston H. Gonnet: A New Approach to Text Searching. In: Communications of the ACM. Band 35, Nr. 10, Oktober 1992, ISSN 0001-0782, S. 74–82, doi:10.1145/135239.135243.
Bearbeiten
  • StringSearch – high-performance pattern matching algorithms in Java (Implementierungen des Shift-Or-Algorithmus in Java; englisch)
  • BNDM-Algorithmus (PDF; 289 kB)