Textsuche: Boyer-Moore-Algorithmus

Warum eigentlich bei der Textsuche das Muster immer von links nach rechts mit dem Text vergleichen?

Wenn du im Text auf ein Zeichen triffst, das im Muster überhaupt nicht vorkommt, dann kannst du das Muster hinter dieses Textzeichen verschieben!

Beim Boyer-Moore-Algorithmus vergleichst du das Muster von rechts nach links mit dem Text. Dadurch erhältst du größere Verschiebungen, wenn du früh auf ein solches, im Muster nicht vorhandenes, Zeichen triffst.

Zum Schluss lernst du noch eine einfachere Variante des Boyer-Moore-Algorithmus kennen, den Sunday-Algorithmus.

Idee

Bei der Textsuche geht es darum, ein Wort oder einen kurzen Text, das Muster, in einem langen Text zu finden – so wie du es von dem Befehl "Suchen" in Textverarbeitungsprogrammen kennst.

Im einfachsten Ansatz vergleichst du das Muster zeichenweise an jeder möglichen Position mit dem Text. Mit diesem naiven Algorithmus benötigst du im schlechtesten Fall $n \cdot m$ Schritte, wobei $n$ die Länge des Textes und $m$ die Länge des Musters ist.

Mit dem Knuth-Morris-Pratt-Algorithmus benötigst du für den Suchvorgang nur höchstens $2n$ Schritte und zusätzlich für den notwendigen Vorlauf noch einmal höchstens $2m$ Schritte.

Beim Boyer-Moore-Algorithmus vergleichst du zuerst das letzte Zeichen des Musters mit dem entsprechenden Zeichen des Textes. Wenn dies ein Zeichen ist, das im Muster überhaupt nicht vorkommt, dann kannst du das Muster sofort hinter dieses Zeichen verschieben!

Beispielsweise hast du den Text ababacaababba und das Muster ababaa. Gleich der erste Vergleich der Zeichen c und a liefert eine Nicht-Übereinstimmung, einen sogenannten Mismatch. Das Zeichen c kommt im Muster nicht vor. Damit kannst du das Muster hinter dieses c verschieben und dort weitervergleichen!

a b a b a c a a b a b b a

a b a b a a

______ a b a b a a

Dies ist der Extremfall – wenn er immer eintritt, benötigt der Boyer-Moore-Algorithmus nur $n/m$ Schritte!

Schlechtes-Zeichen-Strategie

Im allgemeinen Fall tritt ein Mismatch vielleicht erst auf, wenn du schon zwei oder drei Zeichen verglichen hast. Aber auch dann gehst du entsprechend vor, nämlich nach der sogenannten Schlechtes-Zeichen-Strategie (bad character heuristics):

Wenn das Textzeichen, das den Mismatch verursacht hat, im Muster gar nicht vorkommt, verschiebst du das Muster hinter dieses Textzeichen.
Wenn das Zeichen dagegen im Muster vorkommt, verschiebst du das Muster so, dass sein letztes Vorkommen im Muster auf das Textzeichen ausgerichtet ist – außer wenn dabei eine negative Verschiebung zustande kommt, dann verschiebst du das Muster um 1.

Die folgenden drei Situationen veranschaulichen diese unterschiedlichen Fälle.

Das c tritt überhaupt nicht im Muster auf. Du verschiebst das Muster hinter das c.

a b a c a a a a b a b b a

a b a b a a

____ a b a b a a

Das Zeichen b im Text hat einen Mismatch verursacht. Du richtest das letzte b im Muster auf dieses b des Textes aus.

a b a b a b a a b a b b a

a b a b a a

__ a b a b a a

Wenn du in folgender Situation das letzte b des Musters auf das b des Textes ausrichtest, das den Mismatch verursacht hat, erhältst du eine negative Verschiebung des Musters. Stattdessen verschiebst du das Muster um 1.

a b b b a a a a b a b b a

a b a b a a

_ a b a b a a

Die letzte Situation zeigt, dass die bereits gewonnene Information, dass die drei letzten Zeichen des Musters mit dem Text übereinstimmen, hier gar nicht ausgenutzt wird.

Deswegen verwendest du beim Boyer-Moore-Algorithmus noch eine zweite Strategie, die sogenannte Gutes-Ende-Strategie (good suffix heuristics). Mit diesen beiden Strategien erreichst du nicht nur im besten Fall, sondern auch im durchschnittlichen Fall eine Laufzeit von $n/m$ Schritten und im schlechtesten Fall von $n$ Schritten. Allerdings ist die Gutes-Ende-Strategie ziemlich kompliziert anzuwenden – deswegen ersparst du dir an dieser Stelle die Einzelheiten und wirfst, wenn du willst, nur einen Blick auf die prinzipielle Funktionsweise.

Vorlauf für die Schlechtes-Zeichen-Strategie

In einem Vorlauf berechnest du die möglichen Verschiebungen des Musters aufgrund der Schlechtes-Zeichen-Strategie.

Hierfür benötigst du eine sogenannte Occurrence-Tabelle (engl. occurrence – das Auftreten, das Vorkommen). In diese Tabelle trägst du für jedes Alphabetzeichen folgendes ein:

die am weitesten rechts liegende Position, in der es im Muster auftritt,
oder -1, falls es nicht im Muster auftritt.

Wenn beispielsweise das Alphabet $A=$ {a, b, c} lautet und $p=$ bbabaa das Muster ist, so erhältst du als Occurrence-Tabelle

a: 5

b: 3

c: -1

Denn das a tritt am weitesten rechts an Position 5 auf, das b an Position 3 und das c überhaupt nicht.

In der Programmiersprache Python implementierst du die Occurrence-Tabelle am besten als Dictionary.

# Occurrence-Tabelle erstellen
def initOcc():
    global occ
    occ={}    # Dictionary
    for a in alphabet:
        occ[a]=-1
    for j in range(m):
        occ[p[j]]=j

Wie gesagt, ist der Boyer-Moore-Algorithmus mit seinen beiden Strategien, der Schlechtes-Zeichen-Strategie und der Gutes-Ende-Strategie, ziemlich kompliziert. Häufig wird daher der Suchalgorithmus nur mit der Schlechtes-Zeichen-Strategie angewendet.

Eine besonders einfache Variante dieses Suchalgorithmus, der auf der Schlechtes-Zeichen-Strategie basiert, ist der Sunday-Algorithmus.

Sunday-Algorithmus

Beim Sunday-Algorithmus nutzt du die Tatsache aus, dass das unmittelbar rechts neben der Position des Musters stehende Textzeichen bei der nächsten Verschiebung des Musters auf jeden Fall beteiligt ist, wenn dort ein Vorkommen vorliegt.

Wenn das Textzeichen im Muster gar nicht vorkommt, verschiebst du das Muster hinter dieses Textzeichen.
Wenn das Zeichen dagegen im Muster vorkommt, verschiebst du das Muster so, dass sein letztes Auftreten im Muster auf das Textzeichen ausgerichtet ist.

Die nächsten beiden Situationen veranschaulichen dir diese beiden Fälle.

Im ersten Fall kommt das Textzeichen c überhaupt nicht im Muster vor. Du verschiebst das Muster hinter das c.

a b a b b a c a a b a b b a

a b a b a a

_______ a b a b a a

Im zweiten Fall verschiebst du das Muster so weit, dass das letzte Auftreten von c im Muster auf das Textzeichen c ausgerichtet ist.

a b a b b a c a a b a b b a

c b a c a a

___ c b a c a a

Vorlauf

Beim Sunday-Algorithmus verwendest du dieselbe Occurrence-Tabelle wie beim Boyer-Moore-Algorithmus. Du berechnest diese Tabelle mit der oben angegebenen Python-Funktion initOcc.

Suchalgorithmus

Tatsächlich musst du beim Sunday-Algorithmus das Muster nicht wie beim Boyer-Moore-Algorithmus von rechts nach links mit dem Text vergleichen, sondern du kannst es genauso gut von links nach rechts oder in einer beliebigen Reihenfolge vergleichen.

Im Suchalgorithmus sundaySearch verwendest du daher eine Funktion matchesAt, die das Muster in irgendeiner bestimmten Reihenfolge mit dem Text vergleicht. Die Funktion report gibt ein Vorkommen des Musters an der entsprechenden Position aus.

# Suchverfahren Sunday-Algorithmus
def sundaySearch():
    i=0
    while i<=n-m:
        if matchesAt(i):
            report(i)
        i+=m
        if i<n:
            i-=occ[t[i]]
 
# vergleicht das Muster p mit dem Text t an Position i
def matchesAt(i):
    for j in range(m):
        if p[j]!=t[i+j]:
            return False
    return True

# gibt Vorkommen von p an Position i aus        
def report(i):
    print(i*" " + p)

Ähnlich wie der Boyer-Moore-Algorithmus benötigt der Sunday-Algorithmus im günstigsten Fall nur $n/m$ Schritte, im schlechtesten Fall allerdings $n \cdot m$ Schritte, wobei $n$ die Länge des Textes und $m$ die Länge des Musters ist. In der Praxis, insbesondere bei großen Alphabeten, ist der Sunday-Algorithmus sehr schnell.

Hauptprogramm

Zum Testen verwendest du am besten das folgende Hauptprogramm.

if __name__=="__main__":
    alphabet="abc"
    p="ababaa"
    m=len(p)
    initOcc()
    print(occ)
    t="abababbbabaacbaacababaab"
    n=len(t)
    print(t)
    sundaySearch()

Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das?