4. Mustersuche in Feldern

Ein eigenes Kapitel ist die Suche nach einer bestimmten Folge von Elementen in einem Feld. Das kann die Suche nach einer (relativ kurzen) Zeichenfolge in einem (längeren) Text sein, oder ebenso eine bestimmte Folge von Zahlen in einem Feld ganzzahliger Werte oder ähnliches.

Als Beispiel wird aufgrund der Anschaulichkeit die Suche nach einer Zeichenfolge (,,Muster``) in einer mehr oder weniger langen Folge von Zeichen (,,Text``) betrachtet; die vorgestellten Verfahren sind aber eindeutig nicht auf Zeichenfolgen beschränkt.

Ein typisches Beispiel ist ein Editor: hier möchte der Benutzer gelegentlich den vorhandenen Text nach einem bestimmten Wort oder einem Teil-Wort durchsuchen.

Der Text soll die Länge N haben; das Muster die Länge M.

Beispiel: in dem N=10 Zeichen langen Text:
text [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
a x b y c z a x y z

taucht das M=3 Zeichen lange Muster:
muster [0] [1] [2]]
a x y

ab text[6] auf.

Gesucht ist also ein Verfahren, um anhand eines Textes und eines Musters die zugehörige Startposition des Musters im Text (hier: 6) zu finden, beziehungsweise die Erkenntnis zu gewinnen, daß das Muster im Text überhaupt nicht vorkommt.

Eine derartige Suche ist häufig nötig, beispielsweise in einem Editor bei der Suche nach einem enthaltenen Wort, oder in einem Virenscanner beim Suchen nach der Signatur bestimmter Viren.

Wenn man sich die mögliche Länge des zu durchsuchenden Textes vorzustellen versucht, wird schnell klar, daß man einen möglichst effizienten Algorithmus benötigt.



Unterabschnitte
www.wachtler.de