Die Webseiten der Fachschaft Informatik am ERG SaalfeldSuchen 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. Text: Muster: Abarbeitung: er sagte abrakadabra, es bewegte sich aber nichts 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 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 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 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.
© ERG Saalfeld - Hans-Dietrich Kirmse 26.04.2013 |