Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Suchen in Texten / Algorithmus nach Boyer-Moore

Diese Seite stammt aus den Materialien der LFK Informatik und wurde m.E. von Dr. Fothe erstellt. Die damals von mir gesicherten Inhalte dieser Seite wurden komplett und 1:1 übernommen und nur etwas im Layout den anderen Seiten von unserer Schule angepasst.
 

Bei vielen Anwendungen wird ein Muster in einem Text gesucht, so z. B. bei der Volltextsuche im Internet.
Ein schneller Algorithmus soll nachfolgend in seiner prinzipiellen Arbeitsweise vorgestellt werden. Es handelt sich um den Algorithmus nach Boyer-Moore.

Text:
er sagte abrakadabra, es bewegte sich aber nichts

Muster:
aber

Abarbeitung:

er sagte abrakadabra, es bewegte sich aber nichts
aber

Es wird das r aus dem Muster mit dem vierten Zeichen im Text verglichen. Es ergibt sich keine Übereinstimmung. Da das s im Muster nicht enthalten ist, kann das Muster sofort um vier Zeichen nach rechts geschoben werden.

er sagte abrakadabra, es bewegte sich aber nichts
    aber

Es wird r mit e verglichen. Es ergibt sich keine Übereinstimmung. Das e ist im Muster enthalten, und zwar als drittes Zeichen. Das Muster kann daher nur um ein Zeichen nach rechts geschoben werden.

er sagte abrakadabra, es bewegte sich aber nichts
     aber

Der Vergleich des r mit dem Leerzeichen ergibt keine Übereinstimmung. Ein Leerzeichen ist im Muster nicht enthalten. Daher kann das Muster gleich um vier Zeichen nach rechts geschoben.

Der weitere Verlauf wird nun beschrieben:

er sagte abrakadabra, es bewegte sich aber nichts
         aber
            aberaber
                  aber
                   aberaberaber
                             aberaberaber
                                      aber

Es waren nur wenige Vergleiche auszuführen, um das Muster im Text zu finden.

2. Literaturhinweis

Ottmann, Thomas; Widmayer, Peter: Algorithmen und Datenstrukturen. 2. Aufl.
BI Wissenschaftsverlag Mannheim, Leipzig, Wien, Zürich 1993, ISBN 3-411-16602-9
 
 

zurück