Baeza-Yates-Gonnet-Algorithmus

Der Baeza-Yates-Gonnet-Algorithmus bzw. Shift-or-Algorithmus, der auch unter dem Namen Shift-and 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.

Inhaltsverzeichnis

Grundlage

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


R_{j+1}[i] = \begin{cases} 1, & \mbox{falls }i=0\\1, & \mbox{falls }R_j[i-1]=1 \mbox{ und } \mathit{Musterzeichen}_i=\mathit{Eingabezeichen}_{j+1}\\0, & \mbox{sonst}\end{cases}

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

Ein Treffer für ein Suchmuster mit Länge m ist demnach gefunden, falls Rj[m] = 1.

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


s_a[i] = \begin{cases} 1, & \mbox{falls im Suchmuster an Stelle } i \mbox{ das Zeichen } a \mbox{ steht}\\0, & \mbox{sonst} \end{cases}

Beispiel:

Suchmuster abcac, Länge m = 5

Charakteristische Vektoren:


\begin{matrix}
  & s_a & s_b & s_c & s_d & ...\\
a & 1 & 0 & 0 & 0 & ...\\
b & 0 & 1 & 0 & 0 & ...\\
c & 0 & 0 & 1 & 0 & ...\\
a & 1 & 0 & 0 & 0 & ...\\
c & 0 & 0 & 1 & 0 & ...
\end{matrix}

Ablauf (exaktes Matching)

Um den Ablauf zu vereinfachen, wird zunächst eine spezielle Bit-Operation Bitshift bzw. \gg für den Vektor R eingeführt: 
R=
\begin{matrix} 0\\ 0\\ 0\\ 0\\ 0 \end{matrix}
\quad\stackrel{\mathit{Bitshift}}{\longrightarrow}\quad
\begin{matrix} 1\\ 0\\ 0\\ 0\\ 0 \end{matrix}
\quad\stackrel{\mathit{Bitshift}}{\longrightarrow}\quad
\begin{matrix} 1\\ 1\\ 0\\ 0\\ 0 \end{matrix}
\quad\stackrel{\mathit{Bitshift}}{\longrightarrow}\quad
\begin{matrix} 1\\ 1\\ 1\\ 0\\ 0 \end{matrix}

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

  1. Initialisiere den R-Vektor mit 0 (für alle Positionen) und beginne mit dem ersten Zeichen des zu durchsuchenden Textes
  2. Verschiebe alle Bits in R mittels Bitshift um eine Position nach rechts.
  3. Führe eine UND-Verknüpfung von R 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 R aus: Durch das Shiften wird aus dem "alten" R das Zeichen an Stelle i an die Stelle i + 1 angelegt (entspricht in Kombination mit UND der Bedingung Rj[i] = 1). Der charakteristische Vektor des aktuellen Textzeichens enthält an der Stelle i + 1 genau dann eine 1, falls Muster und Text hier übereinstimmen. Durch das UND werden beide Bedingungen verknüpft.

Beispiel (exaktes Matching)

Muster: abcac, m = 5

Text: abcabcac


\begin{vmatrix}
i \setminus & R_0 & \gg & s_a & R_1\\
1 & 0 & 1 & 1 & 1 \\
2 & 0 & 0 & 0 & 0 \\
3 & 0 & 0 & 0 & 0 \\
4 & 0 & 0 & 1 & 0 \\
5 & 0 & 0 & 0 & 0 
\end{vmatrix}
\begin{vmatrix}
\gg & s_b & R_2\\
1 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & 0 
\end{vmatrix}
\begin{vmatrix}
\gg & s_c & R_3 \\
1 & 0 & 0 \\
0 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 0 \\
0 & 1 & 0 
\end{vmatrix}
\begin{vmatrix}
\gg & s_a & R_4 \\
1 & 1 & 1 \\
0 & 0 & 0 \\
0 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 0 
\end{vmatrix}
\begin{vmatrix}
\gg & s_b & R_5 \\
1 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 0 \\
0 & 0 & 0 \\
1 & 0 & 0 
\end{vmatrix}
\begin{vmatrix}
\gg & s_c & R_6 \\
1 & 0 & 0 \\
0 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 0 \\
0 & 1 & 0 
\end{vmatrix}
\begin{vmatrix}
\gg & s_a & R_7 \\
1 & 1 & 1 \\
0 & 0 & 0 \\
0 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 0 
\end{vmatrix}
\begin{vmatrix}
\gg & s_c & R_8 \\
1 & 0 & 0 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 0 \\
1 & 1 & 1 
\end{vmatrix}

Da R8[5] = 1 liegt ein Treffer bei 8 − 5 + 1 (Position − Musterlänge + Korrektur für erstes Zeichen) vor.

Erweiterung (approximatives Matching)

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

  1. R_j^0[i]: entspricht dem vorherigen Rj[i]; Der Index 0 steht für die Anzahl der aufgetretenen Fehler.
  2. R_j^1[i]: Bezeichnet einen R-Vektor, der auf Treffer mit maximal einem Fehler ausgerichtet ist.
  3. ...
  4. R_j^k[i]: Bezeichnet einen R-Vektor, der auf Treffer mit maximal k 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 R_j^0[i] bleibt unverändert. Für Fehlervektoren R_{j+1}^kwird nach der verursachenden Aktion unterschieden:

Einfügen eines Zeichens in das Suchmuster


R_{j+1}^k = (\mathit{Bitshift}(R_j^k)\ \wedge\ s_x) \quad \vee \ R_j^{k-1}

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

Interpretation: R_j^k[i]=1, falls nach j Zeichen der Eingabe von den letzten i + k Zeichen mindestens i 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


R_{j+1}^k = (\mathit{Bitshift}(R_j^k)\ \wedge\ s_x) \quad \vee \ \mathit{Bitshift}(R_{j+1}^{k-1})

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

Ersetzen eines Zeichens im Muster


R_{j+1}^k = (\mathit{Bitshift}(R_j^k)\ \wedge\ s_x) \quad \vee \ \mathit{Bitshift}(R_j^{k-1})

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

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

Weblinks

  • StringSearch – high-performance pattern matching algorithms in Java (Implementierungen des Shift-Or-Algorithmus in Java; englisch)
  • BNDM-Algorithmus

Literatur

  • Ricardo A. Baeza-Yates, Gaston H. Gonnet: A New Approach to Text Searching. In: Communications of the ACM. 35, Nr. 10, Oktober 1992, ISSN 0001-0782, S. 74-82 (PS).

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • String-Matching-Algorithmus — Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf… …   Deutsch Wikipedia

  • Shift-And-Algorithmus — Der Baeza Yates Gonnet Algorithmus bzw. Shift or Algorithmus, der auch unter dem Namen Shift and bekannt ist, löst das String Matching Problem indem er einen nichtdeterministischen Automaten simuliert. Unter anderem wird eine Abwandlung dieses… …   Deutsch Wikipedia

  • Shift-Or-Algorithmus — Der Baeza Yates Gonnet Algorithmus bzw. Shift or Algorithmus, der auch unter dem Namen Shift and bekannt ist, löst das String Matching Problem indem er einen nichtdeterministischen Automaten simuliert. Unter anderem wird eine Abwandlung dieses… …   Deutsch Wikipedia

  • Shift-And — Der Baeza Yates Gonnet Algorithmus bzw. Shift or Algorithmus, der auch unter dem Namen Shift and bekannt ist, löst das String Matching Problem indem er einen nichtdeterministischen Automaten simuliert. Unter anderem wird eine Abwandlung dieses… …   Deutsch Wikipedia

  • Shift-Or — Der Baeza Yates Gonnet Algorithmus bzw. Shift or Algorithmus, der auch unter dem Namen Shift and bekannt ist, löst das String Matching Problem indem er einen nichtdeterministischen Automaten simuliert. Unter anderem wird eine Abwandlung dieses… …   Deutsch Wikipedia

  • String-Matching-Algorithmen — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. String Matching Algorithmen, etwa Zeichenketten Übereinstimmungs… …   Deutsch Wikipedia

  • String Matching — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. String Matching Algorithmen, etwa Zeichenketten Übereinstimmungs… …   Deutsch Wikipedia

  • Suchmaske — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. String Matching Algorithmen, etwa Zeichenketten Übereinstimmungs… …   Deutsch Wikipedia

  • Textsuche — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. String Matching Algorithmen, etwa Zeichenketten Übereinstimmungs… …   Deutsch Wikipedia

  • Shellsort — ist ein von Donald L. Shell im Jahre 1959 entwickeltes Sortierverfahren, das auf dem Sortierverfahren des direkten Einfügens (Insertionsort) basiert. Inhaltsverzeichnis 1 Prinzip 2 Beispiel 3 Implementierung …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”