Alternative zu PosEx

[Gausi]

Zitat von Sinspin:

Ich habe aber bisher noch keinen Anwendungsfall gehabt bei dem die Untersuchung eines Strings zeitkritisch gewesen wäre.

Wenn die Strings größer werden, und man oft (oder viele) Teilstrings in vielen verschiedenen Texten suchen will, dann wird das schon interessant. Aber dann nimmt man ggf. auch andere Suchalgorithmen. Knuth-Morris-Pratt, Boyer-Moore, QuickSearch oder ein paar weitere, die ggf. auf bestimmte Spezialfälle hin optimiert sind. Parameter dafür sind u.a.

• Länge der gesuchten Teilstrings
• Größe des verwendeten Alphabets (also Anzahl der verschiedenen Zeichen)

Pos und PosEx laufen dabei unter "naive Verfahren".

Ein Anwendungsfall ist z.B. das Durchsuchen eines Genoms nach einer bestimmten DNA-Sequenz. Zumindest war das öfter ein Beispiel in der Literatur, als ich damals meine Diplomarbeit über "Algorithmen zur Mustersuche in Zeichenketten" geschrieben habe.

Aber es stimmt schon, dass das meistens irrelevant ist - denn selbst der "naive Algorithmus" hat eine (erwartete) lineare Laufzeit. KMP ist interessant, weil da auch die Worst-Case-Laufzeit linear ist (im Gegensatz zu quadratisch bzw. "rechteckig", d.h. Textlänge*Musterlänge im Worst Case bei Pos). Boyer-Moore z.B. wird schneller, wenn die Suchmuster länger werden.

Oder halt komplette andere Ansätze, wie z.B. vorher einen Suchindex über die zu durchsuchenden Texte aufbauen, aber das ist dann wirklich was komplett anderes.