Wiederkehrende Patterns in einem Text finden

[Gausi]

Wenn man weiß, welche Pattern man finden möchte, gibt es diverse schnelle Algorithmen.

Da wäre zum einen der Aho-Corasick-Algorithmus (ca. 1977) (Prinzip vergleichbar mit dem Algorithmus von Knuth, Morris und Pratt, nur auf Multipattern erweitert). Dann gibts Commentz-Walter (ca. 1979), den ich nocht nicht richtig verstanden habe, und den Wu-Manber-Algorithmus (ca 1994), der in den meisten Fällen am schnellsten ist. Wenn extrem viele Pattern simultan gesucht werden sollen, dann vielleicht noch den Set-Backward-Oracle-Matching-Algorithmus (ca. 1999) anschauen. Obs danach nocht interessante Weiterentwicklungen gibt, weiß ich nicht.

Um die Muster zu bestimmen, die man sucht, könnte man den Text in eine Baumstruktur speichern, die ca. O(n^2) Platz benötigen wird. An den Knoten sind die Zeichen des Textes gespeichert. Zuerst fügt man den gesamten Text zeichenweise ein, dann den Text ohne das erste Zeichen, dann ohne das zweite etc. Das einfügen immer so, dass schon vorhandene Kanten weitergenutzt werden, und dass ein Weg von der Wurzel zu einem Blatt ein Suffix des Textes ist. Beim Aufbau merken, wenn eine Kante mehrfach benutzt wird und diesen Wert an der Kante speichern.
Den fertigen Baum sucht man dann ausgehend von der Wurzel möglichst lange Wege mit hohen Kantenwerten, und erstellt daraus seine Musterliste.
Die Idee ist bei mir noch nicht ganz ausgereift, aber das mit dem Baum hat Hagen ja schon eingeworfen, so komplett falsch kann das also nicht sein