Wie zuvor beschrieben, geht es hier darum, Suchanfragen so zu optimieren, dass bereits durchschaute Bereiche nicht mehrfach durchsucht werden müssen. Aus diesem Grund schauen wir uns zunächst das Suchpattern an, ob sich aus dem Suchpattern bereits Rückschlüsse ziehen lassen.

Häufig ist es so, dass die Daten, die wir verarbeiten implizit Informationen in sich tragen, die wir uns zu Nutzen machen können. Dazu muss man sich ganz klar vor Augen führen, was man eigentlich tut, hier zum Beispiel, in dem man sich erneut Gedanken über Dinge macht, die einem als Trivial erscheinen. Hierzu haben wir uns zuvor ja bereits nochmal Gedanken darüber gemacht, was eigentlich ein Text überhaupt ist.

Wir haben am BruteForce-Beispiel gesehen, wie man mit reiner Rechenpower und ohne jeden Verstand Suchmuster in Texten finden kann. Nun wollen wir uns nochmal zurückziehen und uns anschauen, wie man mit Verstand an die Sache herangehen kann.

Nun sind wir nicht die ersten, die sich zu dem Thema Gedanken machen, deswegen möchte ich die Wege nachgehen, die bereits Donald Ervin Knuth, James Hiram Morris und Vaughan Ronald Pratt gegangen sind und nach denen der folgende Algorithmus auch benannt wurde.

Hier wird das gesuchte Pattern daraufhin untersucht, ob es ein Präfix gibt, dass ich in der bisherigen Suche bereits wiederholt hat.

• Knuth-Morris-Pratt-Algorithmus-Algorithmus

Knuth-Morris-Pratt haben damit einen Algorithmus vorgelegt, welcher in kleinen Alphabeten die Suche beschleunigen kann. Ein Computer arbeitet jedoch häufig mit Bytes und so sind auch lesbare Texte häufig als ASCII-Texte (256 Zeichen Alphabet) oder sogar Unicode (65536 Zeichen Alphabet) kodiert und auch Worte, die lange Wortbestandteile vom Anfang gleichlautend in der Wortmitte wiederholen sind eher selten, die Wiederholungen eher kurz und bereits die Groß-/Kleinschreibung kann hier Ähnlichkeiten verhindern, wenn der Wortanfang groß geschrieben wird, in der Wortmitte aber natürlich keine Großbuchstaben mehr auftauchen.

Der BruteForce Algorithmus, wie auch Knuth-Morris-Pratt-Algorithmus haben einen üblichen Ansatz gewählt: Es gibt ein Problem zu lesen, also schauen wir nach, ob wir die Lösung gefunden haben. Man sucht in der Regel nach etwas, was man finden möchte. Die Frage lautet: Ist hier mein Suchmuster? Beide Algorithmen sind also darauf ausgelegt, jetzt etwas zu finden und die Optimierung findet da statt, wenn sich die Annahme nicht bewahrheitet hat. Nun ist es dem Algorithmus allerdings vollkommen egal, ob er einen Fund meldet oder nicht.

Wenn man ein Problem optimieren möchte, so findet sich gelegentlich ein gleichwertiges Ziel, dass aber schneller zu prüfen ist. Hierzu haben sich Bob Boyer und J Strother Moore Gedanken gemacht und ihren eigenen Algorithmus entwickelt. Die Problemstellung lautet hier nicht 'Ist hier mein Suchmuster', sondern 'Zeige, dass ein Suchmuster nicht im Text enthalten ist'.

• Boyer-Moore-Algorithmus-Algorithmus