Aus Das deutschsprachige Scratch-Wiki
In Text-Editoren und Web-Browsern öffnet sich mit der Tastenkombination "Strg F" (es gibt natürlich auch einen Menüpunkt dafür) ein Fenster, in das man ein Wort eingeben kann, das dann in dem angezeigten Text gesucht wird.
Was passiert bei dieser Volltextsuche eigentlich?
Direktes Mustersuchen
Man vergleicht den Text mit dem Muster (dem eingegebenen Suchwort). Stimmt der erste Buchstabe des Musters nicht mit dem ersten Buchstaben des Text überein, wird dieser mit dem zweiten Buchstaben des Texts verglichen. So schiebt man das Muster am Test entlang, bis es passt oder das Ende des Texts erreicht ist.
Wenn der Text N Zeichen hat und das Muster M, dann benötigt man N * M Vergleiche.
Dieser intuitive Algorithmus kann jedoch deutlich verbessert werden, denn es geht wertvolle Information verloren, wenn nach mehreren erfolgreichen Vergleichen das Muster trotzdem nur um eine Stelle weitergeschoben wird.
Der Knuth-Morris-Pratt-Algorithmus (1974)
Nachdem festgestellt wurde, dass zum Beispiel das 5. Zeichen des Musters nicht mit dem Text übereinstimmt, kennen wir die 4 letzten Zeichen des Textes, weil sie gleich den ersten 4 Zeichen des Musters sind. Falls keines dieser Zeichen dem 5. Zeichen des Textes entspricht, kann das Vergleichen mit dem 6. Zeichen des Texts fortgesetzt werden!
Dazu muss vor Beginn der Vergleiche eine Liste errechnet werden, wie weit das Muster pro Buchstabe des Musters verschoben werden kann. (Wie oft kann mit Zuhilfenahme einer geeigneten Datenstruktur ein Algorithmus verbessert werden.)
Der KMP-Algorithmus benötigt im besten Fall nur N + M Vergleiche.
Geht es noch besser? Ja!
Der Boyer-Moore-Algorithmus (1977)
Die Strategie des KMP-Algorithmus liefert eigentlich nur dann einen Vorteil, wenn eine Übereinstimmung zwischen einem längeren Teil des Musters und dem Text gefunden wurde, bevor ein ungleiches Zeichenpaar auftritt. Denn nur in diesem Fall kommt es zu einer Verschiebung des Musters um mehr als eine Stelle. Leider ist das aber eher die Ausnahme als die Regel.
Der Boyer-Moore-Algorithmus basiert auf der Idee, die Zeichenvergleiche nicht am Anfang, sondern am Ende des Musters zu beginnen.
Dann kann das Muster oft um die gesamte Musterlänge verschoben werden. Dabei kombiniert der Algorithmus eine "Schlechtes-Zeichen-Strategie" und
eine "Gutes-Ende-Strategie". Für beide muss vorab eine Liste errechnet werden.
Beide Strategien können Verschiebungen um m bewirken: die Schlechtes-Zeichen-Strategie, wenn das erste verglichene Textzeichen nicht im Muster vorkommt und die Gutes-Ende-Strategie, wenn die übereinstimmenden Textzeichen nicht an anderer Stelle im Muster vorkommen.
Der BM-Algorithmus benötigt im günstigsten Fall nur N / M Vergleiche. Er wird in vielen Text-Editoren verwendet.
Der Vorlauf für die Gutes-Ende-Strategie ist schwierig zu verstehen und zu implementieren. Daher findet man gelegentlich Versionen des Boyer-Moore-Algorithmus, in denen die Gutes-Ende-Strategie schlicht weggelassen wird. Die Begründung ist, dass die Schlechtes-Zeichen-Strategie ausreichend sei und die Gutes-Ende-Strategie nicht viele Vergleiche einspare.
Der Horspool-Algorithmus (1980)
Bei diesem Algorithmus wird die "Gutes-Ende-Strategie" weggelassen und die "Schlechtes-Zeichen-Strategie" wird verändert: Es wird für das Verschieben nicht das Zeichen herangezogen, das nicht übereingestimmt hat, sondern stets das ganz rechte Zeichen des Textfensters.
Der Sunday-Algorithmus (1990)
Hier wird noch weiter gegangen: Falls keine Übereinstimmung zwischen Muster und Text festgestellt wird, dann wird das nächste Zeichen im Text betrachtet.
Kommt dieses Zeichen im Muster nicht vor, dann kann hinter dieses Zeichen verschoben werden!
Zwar benötigen auch Horspool und Sunday N / M Vergleiche, aber beide Algorithmen sind einfacher zu implementieren.
setze [Buchstaben v] auf [ enirsatdhulmcgowbfkzvüßäpöj-qxy] lösche (alles v) aus [shift v] lösche (alles v) aus [matches v] Definiere SundayInit (muster) setze [len_muster v] auf (Länge von (muster)) setze [len_text v] auf (Länge von (text)) wiederhole (Länge von (Buchstaben)) mal füge [-1] zu [shift v] hinzu ende setze [index_muster v] auf [1] wiederhole bis <(index_muster) > (len_muster)> setze [index v] auf [1] wiederhole bis <<(index) > (Länge von (Buchstaben))> oder <(Zeichen(index)von(Buchstaben)) = (Zeichen(index_muster)von(muster))>> ändere [index v] um (1) ende ersetze Element (index) von [shift v] durch ((index_muster) - (1)) ändere [index_muster v] um (1) ende Definiere falls (muster) passt beim (text_index) dann merke es dir setze [index v] auf [1] setze [gefunden v] auf [True] wiederhole bis <<(index) > (len_muster)> oder <nicht <(gefunden) = [True]>> setze [zeichen v] auf (Zeichen ((text_index)+(index)) von (text)) setze [gefunden v] auf <(zeichen) = (Zeichen (index) von (muster))> ändere [index v] um (1) ende falls <(gefunden) = [True]>, dann füge ((text_index)+(1)) zu [matches v] hinzu ende Definiere SundaySuche (muster) setze [index_text v] auf [0] wiederhole bis <(index_text) > ((len_text)-(len_muster))> falls (muster) passt beim (index_text) dann merke es dir ändere [index_text v] um (len_muster) falls <(index_text) < (len_text)>, dann setze [index v] auf [1] setze [gefunden v] auf <[1] = [0]> setze [zeichen v] auf (Zeichen ((index_text) + (1)) von (text)) wiederhole bis <<(index) > (Länge von (buchstaben))> oder <(gefunden) = [True]>> setze [gefunden v] auf <(Zeichen (index) von (Buchstaben)) = (zeichen)> ändere [index v] um (1) ende ändere [index_text v] um ((0) - (Element ((index)-(1)) von [shift v])) ende ende
Leider kann man in Scratch für den Index von Listen keine Buchstaben verwenden. Das würde die Umsetzung dieses Algorithmus sehr vereinfachen.
Beispiel
Durchsucht mit dem Sunday-Algorithmus das gesamte Buch "Heidis Lehr- und Wanderjahre" von Johanna Spyri.
|
|
