Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

38.2 Verbesserte lineare Suche

38.2 Verbesserte lineare Suche

Gerade dann, wenn es sich um Texte handelt, die man nicht sortieren darf, braucht man eine schnellere Möglichkeit, als das Suchwort an den Anfang des Textes anzulegen und dann immer Zeichenweise weiter zu verschiebt, um dann immer die Komplette Zeichenkette zu vergleichen. Gerade bei sehr sehr langen Texten und langen Suchwörtern, würde dies extrem lange dauern. Deswegen möchte ich Ihnen hier den Boyer-Moore-Algorithmus vorstellen, welcher sehr viel schneller das gesuchte Wort findet.

Die Grundidee ist, dass man am Anfang, das zu suchende Wort an den Text anlegt und den letzten Buchstaben mit dem Buchstaben vergleicht, der im Text an dieser Stelle steht. Wenn es eine Übereinstimmung gibt, wird der Buchstabe davor verglichen und wenn es wieder eine Übereinstimmung gibt, wird der Buchstabe davor betrachtet. Wenn alle Buchstaben übereinstimmen ist die Position gefunden. Sobald der Vergleich fehlschlägt, wird geprüft, ob der Buchstabe des Textes im Suchwort vorkommt. Ist dies nicht der Fall, wird das Suchwort um seine Länge verschoben und der Algorithmus beginnt von vorne. Ist der Buchstabe im Suchwort enthalten, wird die Differenz aus der Position des hintersten vorkommenden Buchstabe (vor dem Bereich in welchem es Übereinstimmungen zum Text gab) mit der Position der letzten Übereinstimmung ermittelt und das Suchwort um diese Anzahl verschoben. Da dies jetzt sehr theoretisch klingt, werde ich dies an einem kleinen Beispiel zeigen.

Veranschaulichung des Boyer-Moor-Algorithmus

Im Ersten Schritt wird also das a aus dem Text, mit dem a aus dem Suchwort verglichen und eine Übereinstimmung festgestellt. Dies hat zur Folge, dass das l mit dem r verglichen wird und da sich diese zwei Buchstaben unterscheiden, wird jetzt nach dem hintersten l im Suchwort, vor "ra", linear gesucht. Zwei Positionen weiter vorne, wird jetzt ein l gefunden und somit wird das Suchwort um zwei verschoben.

Im nächsten Schritt wird jetzt das i aus dem Text, mit dem a aus dem Suchwort verglichen. Da es nicht übereinstimmt und das i nicht im Suchwort vorkommt, wird das Suchwort um seine gesamte Länge verschoben.

Der Rest sollte jetzt klar sein und wie Sie sehen, benötigt man weniger Schritte, als würde man das Wort immer Zeichen für Zeichen verschieben und alles Prüfen.

Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012