Quelltext der Seite Boyer-Moore-Algorithmus

Der '''Boyer-Moore-Algorithmus''' ist ein  [[String-Matching-Algorithmus]]. Der Algorithmus wird dazu genutzt, um in einem Text ''T'' einen bestimmten Teiltext (Muster ''M'') zu finden und wurde [[1977]] von [[Robert S. Boyer]] und [[J Strother Moore]] entwickelt.

__TOC__
== Algorithmus ==
Das Muster wird am Anfang linksbündig unter den Text geschrieben und dann von rechts nach links Zeichen für Zeichen mit dem Text verglichen. Sobald ein [[Mismatch]] auftritt, berechnen zwei [[Heuristik#Informatik|Heuristiken]], wie weit das Suchmuster nach rechts verschoben werden kann.

; Bad-Character-Heuristik:Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein Zeichen des Musters nicht mit dem Zeichen des Textes überein (''Bad-Character''), wird im Muster nach dem letzten Vorkommen dieses ''Bad-Characters'' gesucht und das Muster so weit verschoben, bis beide Buchstaben übereinander liegen. Existiert dieser ''Bad-Character'' nicht im Muster, wird das Muster soweit verschoben, dass sein erstes Zeichen unter dem Nachfolger des ''Bad-Character'' liegt. Es kann vorkommen, dass die Bad-Character-Heuristik eine Verschiebung des Musters nach links vorschlägt. In diesem Fall wird um eine Position nach rechts geschoben.
; Good-Suffix-Heuristik:Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein [[Suffix]] des Musters mit dem Text überein und tritt danach aber ein Mismatch auf, wird das Muster so weit nach rechts geschoben, bis ein Teilwort des Musters wieder auf das Suffix passt. Existiert das Suffix kein zweites Mal im Muster, wird das Muster um seine volle Länge nach rechts verschoben.

Es kommt vor, dass die beiden Heuristiken unterschiedliche Verschiebungen berechnen. Der Algorithmus wählt immer das [[Größtes und kleinstes Element|Maximum]] der beiden Vorschläge, um das Muster nach rechts zu verschieben.

Um das Vorgehen effizient zu gestalten, wird für beide Heuristiken in einem Vorverarbeitungsschritt jeweils eine Sprungtabelle errechnet. Die Sprungtabelle für die Bad-Character-Heuristik enthält für jedes im Suchmuster vorkommende Zeichen den Abstand von der Position des letzten Vorkommens im Suchmuster bis zum Ende des Suchmusters. Die Tabelle für die Good-Suffix-Heuristik enthält für jedes Teilmuster (von hinten aus gesehen) den Abstand vom Ende des Musters, ab dem es wieder im Muster vorkommt.

== Beispiele ==
=== Bad-Character-Heuristik ===

'''String:''' Hoola-Hoola girls like Hooligans

'''Suchmuster:''' Hooligan

 Hoola-H<span style="color:#00ff00">o</span>ola girls like Hooligans
 Hooliga<u><span style="color:#ff0000">n</span></u>

Das letzte Zeichen stimmt nicht mit dem letzten des Suchmusters überein, also kann man das Suchmuster bis zum ersten „o“ (des Suchmusters, von hinten gelesen) verschieben:

 Hoola-H<span style="color:#00ff00">o</span>ola <span style="color:#0000ff">g</span>irls like Hooligans
 Hooliga<u><span style="color:#ff0000">n</span></u>
      Ho<span style="color:#00ff00">o</span>liga<u><span style="color:#ff0000">n</span></u>

Das letzte Zeichen des Suchmusters stimmt nicht mit dem Text überein. An der betreffenden Stelle steht ein „g“, das sich wiederum im Muster an der dritten Position von rechts findet. Wird das Muster um zwei Zeichen nach rechts verschoben, dann „matchen“ die blauen „g“:

 Hoola-H<span style="color:#00ff00">o</span>ola <span style="color:#0000ff">g</span>irls like Hooligans
      Ho<span style="color:#00ff00">o</span>liga<u><span style="color:#ff0000">n</span></u>
        Hooli<span style="color:#0000ff">g</span>a<u><span style="color:#ff0000">n</span></u>

Das „r“ im String kommt im Muster überhaupt nicht vor. Das ermöglicht – weil bereits der erste verglichene Buchstabe (von hinten) nicht passt – das Verschieben um die komplette Länge des Suchstrings, da hier ausgeschlossen ist, dass das Muster an einer Stelle matcht. Das Gleiche passiert gleich im nächsten Schritt erneut, nur ist es jetzt das Leerzeichen (statt dem „r“), das nicht im Muster vorkommt.

 Hoola-Hoola <span style="color:#0000ff">g</span>irls like Hooligans
        Hooli<span style="color:#0000ff">g</span>a<u><span style="color:#ff0000">n</span></u>
                Hooliga<u><span style="color:#ff0000">n</span></u>
                        <u>Hooligan</u>
Danach wurde das Muster gefunden.

Ein weiteres Beispiel, bei dem es nicht das letzte Zeichen des Suchstrings betrifft. Deshalb kann der gesamte Suchstring nur bis eine Stelle nach dem gefundenen Mismatch verschoben werden.
{| class="wikitable"
|A
|B
|R
|A
|'''G'''
|A
|D
|A
|B
|R
|A
|K
|A
|D
|A
|'''B'''
|R
|A
|-
|A
|B
|R
|A
|'''K'''
|A
|D
|A
|B
|R
|A
|&nbsp;
|&nbsp;
|&nbsp;
|&nbsp;
|&nbsp;
|&nbsp;
|&nbsp;
|-
|&nbsp;
|&nbsp;
|&nbsp;
|&nbsp;
|&nbsp;
|A
|B
|R
|A
|K
|A
|D
|A
|B
|R
|'''A'''
|&nbsp;
|&nbsp;
|-
|&nbsp;
|&nbsp;
|&nbsp;
|&nbsp;
|&nbsp;
|&nbsp;
|&nbsp;
|A
|B
|R
|A
|K
|A
|D
|A
|B
|R
|A
|}
Skip-Tabelle für das oben aufgeführte Beispiel:
{| class="wikitable"
|A
|B
|R
|K
|D
|-
|0
|2
|1
|6
|4
|}

Der Boyer-Moore-Algorithmus arbeitet am effizientesten, wenn er ein Zeichen vorfindet, das im Suchmuster nicht vorkommt. Die Bad-Character-Regel kommt dann zum Tragen. Dies ist sehr wahrscheinlich bei einem relativ kleinen Muster und einem großen Alphabet, was ihn für einen solchen Fall besonders geeignet macht. In diesem Fall arbeitet der Algorithmus mit einer Effizienz von <math>O\left(\frac{n}{m}\right)</math> Vergleichen.

=== Good-Suffix-Heuristik ===

'''String:''' reinesupersauersupesupersupe

'''Suchmuster:''' supersupe

 reine<u>supe</u>rsauersupesupersupe
 super<u>supe</u>

Nur die letzten 4 Buchstaben stimmen überein („supe“). Dieses Suffix kommt im Muster ganz am Anfang vor, also kann man das Muster bis dorthin verschieben:

 reinesupersau<u>e</u>rsupesupersupe
      supersup<u>e</u>

Nur der letzte Buchstabe „e“ stimmt überein. Wir können das Muster bis zum nächsten Auftreten von „e“ in supersupe verschieben:

 reinesupersau<u>ersupe</u>supersupe
           sup<u>ersupe</u>

Nur die letzten Buchstaben „ersupe“ stimmen überein, welche an keiner anderen Stelle im Muster mehr auftreten. Allerdings tritt das Suffix „supe“ sowohl am Ende von „ersupe“ als auch am Anfang des Musters auf.

 reinesupersauersupesupersupe
                supersupe

„e“ und „r“ stimmen nicht überein, wir verschieben um eine Position. Dieser Fall tritt mehrmals hintereinander auf:

 reinesupersauersupesupersupe
                 supersupe

 reinesupersauersupesupersupe
                  supersupe

 reinesupersauersupesupersupe
                   supersupe

 reinesupersauersupe<u>supersupe</u>
                    <u>supersupe</u>

Muster wurde gefunden.
Zusammen mit der „Bad-Character-Heuristik“ könnten die letzten 3 Iterationen übersprungen werden, da wir bis zum nächsten „r“ im Muster verschieben können.

== Laufzeit ==
Im Folgenden wird die [[Landau-Notation]] verwendet, um das asymptotische Verhalten der Laufzeit anzugeben.
Sucht der Boyer-Moore-Algorithmus nur das erste Auftreten des Musters, hat er eine Worst-Case-Komplexität von <math>\Theta\left(n + m\right)</math>.
Wird er jedoch benutzt, um alle Matches des Musters zu finden, ist die
Worst-Case-Komplexität <math>\Theta\left(n \cdot m\right)</math>. Diese Komplexität kann jedoch durch eine zusätzliche Regel für den Fall, dass im letzten Schritt das Muster gefunden wurde, wieder auf <math>\Theta\left(n + m\right)</math> reduziert werden.
Verwendet man den Algorithmus jedoch für ein relativ kleines Muster und ein großes Alphabet, erhält man eine Average-Case-Komplexität von <math>\Theta\left(\frac{n}{m}\right)</math>.

=== Bad-Character-Heuristik ===
Verwendet man nur die Bad-Character-Heuristik, erhält man immer noch eine Average-Case-Komplexität von <math>\Theta\left(\frac{n}{m}\right)</math>, muss aber eine Worst-Case-Komplexität von <math>\Theta\left(n \cdot m\right)</math> in Kauf nehmen. Ein Worst-Case-Beispiel ist der Text <math>T=a^n</math> gemeinsam mit dem Muster <math>M=ba^{m-1}</math>.
Hier wird immer das ganze Muster mit dem Text verglichen, bis an der ersten Stelle ein Mismatch auftritt. Nach einem solchen Mismatch kann das Muster (mittels Bad-Character-Heuristik) aber nur um eine Stelle nach rechts verschoben werden.

== Beispielcode in C++ ==

In der Praxis wendet der Algorithmus beide Regeln an und nutzt immer die Regel, die das Muster am weitesten springen lässt, für die „Guter-Suffix-Regel“ sowie für die „Schlechtes-Zeichen-Regel“ erstellt man zu Beginn der Suche jeweils eine Sprungtabelle (siehe „charTable“ und „offsetTable“ im Code).

Im folgenden Quellcode geschieht das Anlegen der „Guter-Suffix-Regel“-Tabelle (charTable) im (unwahrscheinlichen) schlechtesten Fall in <math>O\left(m^2\right)</math>, was bei nicht zu großen Mustern zu vernachlässigen ist. Die Suche nach dem Suffix für die „Schlechtes-Zeichen-Regel“-Tabelle lässt sich beispielsweise über den [[Knuth-Morris-Pratt-Algorithmus|KMP]]-Algorithmus machen, was hier aber der Übersichtlichkeit wegen vermieden wird. Damit liegt folgender Algorithmus in <math>O\left(n + m^2\right)</math>.

Lässt man sich die Anzahl der benötigten Vergleiche ausgeben, so sind dies bei einem großen Alphabet erstaunlich wenige und der Boyer-Moore-Algorithmus ist beispielsweise dem [[Knuth-Morris-Pratt-Algorithmus]] vorzuziehen.
<!-- angenehmere Farben beim --><syntaxhighlight lang="c++">
#include <algorithm>
#include <iostream>
#include <limits>
#include <string_view>
#include <vector>

using namespace std;

/**
 * Ist needle[position] bis needle[needle.size() - 1] ein Präfix von needle?
 */
bool isPrefix(string_view needle, int position) {
    for (int i = position, j = 0; i < needle.size(); ++i, ++j)
        if (needle[i] != needle[j])
            return false;

    return true;
}

/**
 * Gibt die maximale Länge der Teilzeichenfolge zurück, die bei position endet
 * und ein Suffix ist. (Hilfsfunktion für Guter-Suffix-Regel)
 */
int suffixSize(string_view needle, int position) {
    int size = 0, i = position, j = needle.size() - 1;

    while (i >= 0 and needle[i] == needle[j]) {
        --i;
        --j;
        ++size;
    }

    return size;
}

/**
 * Erstellt die Sprungtabelle basierend auf den nicht übereinstimmenden
 * Zeicheninformationen. (Schlechtes-Zeichen-Regel)
 */
vector<int> makeCharTable(string_view needle) {
    auto table = vector<int>(numeric_limits<char>::max());

    for (int &value: table)
        value = needle.size();

    for (int i = 0; i < needle.size() - 1; ++i)
        table[needle[i]] = needle.size() - 1 - i;

    return table;
}

/**
 * Erstellt die Sprungtabelle basierend auf dem Scanoffset, bei dem eine
 * Nichtübereinstimmung auftritt. (Guter-Suffix-Regel)
 */
vector<int> makeOffsetTable(string_view needle) {
    auto table = vector<int>(needle.size());
    int lastPrefixPosition = needle.size();

    for (int i = needle.size(); i > 0; --i) {
        if (isPrefix(needle, i))
            lastPrefixPosition = i;

        table[needle.size() - i] = lastPrefixPosition - i + needle.size();
    }

    for (int i = 0; i < needle.size() - 1; ++i) {
        int size = suffixSize(needle, i);
        table[size] = needle.size() - 1 - i + size;
    }

    return table;
}

/**
 * Gibt den Index innerhalb der Zeichenfolge des ersten Auftretens vom
 * spezifizierten Teilstring zurück. Wenn es sich nicht um einen Teilstring
 * handelt, wird -1 zurückgegeben.
 */
int indexOf(string_view haystack, string_view needle) {
    if (needle.size() == 0)
        return 0;

    vector<int> charTable = makeCharTable(needle);
    vector<int> offsetTable = makeOffsetTable(needle);

    for (int i = needle.size() - 1, j; i < haystack.size();) {
        for (j = needle.size() - 1; needle[j] == haystack[i]; --i, --j)
            if (j == 0)
                return i;

        i += max(offsetTable[needle.size() - 1 - j], charTable[haystack[i]]);
    }

    return -1;
}

int main() {
    string_view haystack = "ttabarbsxfarbbarb";
    string_view needle = "arbbarb";
    cout << "found at position " << indexOf(haystack, needle) << endl;

    return 0;
}
</syntaxhighlight>

== Literatur ==

* [[Robert S. Boyer]], [[J. Strother Moore]]: ''A fast string searching algorithm''. In: ''Communications of the ACM.'' Bd. 20, Nr. 10, {{ISSN|0001-0782}}, S. 762–772, [https://www.cs.utexas.edu/~moore/publications/fstrpos.pdf Onlineversion (PDF; 1,19 MB)], {{doi|10.1145/359842.359859}}.

* Robert S. Boyer, J. Strother Moore: ''A Lemma Driven Automatic Theorem Prover for Recursive Function Theory.'' In: ''5th International Joint Conference on Artificial Intelligence, 1977, IJCAI-77. Proceedings of the Conference. Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, August 22–25, 1977.'' Band 2. Morgan Kaufmann Publishers Inc., Los Altos CA 1977, ISBN 0-934613-48-6, S. 511–519, [https://www.ijcai.org/Proceedings/77-1/Papers/089.pdf Onlineversion (PDF; 240 kB)].

* Markus E. Nebel: ''Texte durchsuchen – aber schnell! Der Boyer-Moore-Horspool Algorithmus''. In: Taschenbuch der Algorithmen. Hrsg. von [[Berthold Vöcking]], [[Helmut Alt]], [[Martin Dietzfelbinger]], [[Rüdiger Reischuk]], [[Christian Scheideler]], [[Heribert Vollmer]] und [[Dorothea Wagner]]. Berlin, Heidelberg: Springer Verlag 2008, S. 51–60. ISBN 978-3-540-76394-9
== Weblinks ==
* [https://www.inf.hs-flensburg.de/lang/algorithmen/pattern/bm.htm Eine ausführlichere Erklärung bei der Hochschule Flensburg]
* University of British Columbia: [https://cmps-people.ok.ubc.ca/ylucet/DS/BoyerMoore.html Boyer-Moore String Search], Webseite zur Visualisierung des Boyer-Moore-Algorithmus
* [https://www.cs.utexas.edu/users/moore/best-ideas/string-searching/ Ein ausführliches Beispiel von Miterfinder] [[J Strother Moore]]
* [https://users.dcc.uchile.cl/~rbaeza/handbook/algs/7/713b.srch.c.html Boyer-Moore-Horspool-Algorithmus]

[[Kategorie:Algorithmus]]
[[Kategorie:Suchalgorithmus]]