Textsuche: Naiver Algorithmus

Das Problem

Du hast einen langen Text und einen kurzen Text, das Muster (engl. pattern) . Du möchtest gern wissen, ob das Muster in dem langen Text vorkommt, und wenn ja, an welchen Stellen.

naiver Algorithmus

Die einfachste Möglichkeit besteht darin, das Muster unter den Text zu legen und zeichenweise von links nach rechts miteinander zu vergleichen. Hier ein Beispiel mit dem Text aaabaabacabca und dem Muster aaba:

a a a b a a b a c a b c a

a a b a

Du stellst fest, dass die ersten beiden Zeichen aa des Musters mit dem Text übereinstimmen, aber das dritte Zeichen, das b, an dieser Position nicht mit dem Text übereinstimmt - es liegt hier ein Mismatch vor. Dies bedeutet, dass an der gezeigten Stelle das Muster nicht im Text vorkommt.

Nun schiebst du das Muster um eine Position weiter nach rechts und beginnst wieder von vorne zu vergleichen:

a a a b a a b a c a b c a

_ a a b a

Nun stimmen alle Zeichen des Musters mit dem Text überein. Du hast also ein Vorkommen des Musters im Text gefunden!

Um ein weiteres Vorkommen zu finden, schiebst du das Muster erneut um eine Position weiter (denn es kann auch überlappende Vorkommen geben):

a a a b a a b a c a b c a

__ a a b a

Hier kommt es beim zweiten Zeichen des Musters zu einem Mismatch. Also schiebst du das Muster erneut um eine Position weiter:

a a a b a a b a c a b c a

_ __ a a b a

Und so weiter und so fort (beim nächsten Mal hast du wieder Erfolg und findest ein Vorkommen).

Analyse

Warum "naiver" Algorithmus? Weil du bei diesem Algorithmus - was du sicher nie tun würdest - einfach ohne viel nachzudenken drauflos vergleichst. Denn eigentlich weißt du ja schon, dass zum Beispiel in der letzten gezeigten Situation das a des Musters nicht mit dem b des Textes übereinstimmt, denn das hast du in der Situation davor bereits schmerzlich erfahren.

Du vergleichst also beim naiven Algorithmus viel zu viel doppelt und dreifach. Vielleicht sagst du: "Na und? Der Computer ist doch geduldig, und schnell genug ist er auch!" Aber das wäre dann tatsächlich naiv. Denn anders als in dem gezeigten Beispiel gibt es auch sehr lange Texte und auch längere Muster. Und du suchst auch nicht ausschließlich in deutschsprachigen Texten, sondern vielleicht auch in Binärdateien. Es kommt also durchaus auf Effizienz an.

Wie lange braucht der naive Algorithmus im schlechtesten Fall? Stell dir vor, der Text $t$ hat die Länge $n$ und besteht aus lauter a's, und das Muster $p$ hat die Länge $m$ und lautet aaa...aaab, d. h. es beginnt mit lauter a's und endet mit b. Dann kommt es immer erst beim letzten Zeichen des Musters, dem b, zu einem Mismatch. Du vergleichst also immer alle Zeichen des Musters mit dem Text, und das an jeder möglichen Stelle des Textes.

Insgesamt sind dies größenordnungsmäßig $n \cdot m$ Vergleiche - jedenfalls wenn $n$ sehr viel größer als $m$ ist.

Geht es schneller? Ja, es gibt eine Vielzahl von Ideen - eine dieser effizienteren Ideen ist der Knuth-Morris-Pratt-Algorithmus.