Textsuche

Textsuchproblem

 aufwärts

Jedes Text­verarbeitungs­programm hat eine Suchfunktion, mit der man in einem Text alle Vorkommen eines bestimmten Wortes suchen kann. Sucht man beispiels­weise in diesem Absatz das Wort "Text", so wird das erste Vorkommen am Anfang von "Text­verarbeitungs­programm" gefunden und dann noch an drei weiteren Stellen.

Es folgt zunächst die formale Definition einiger Begriffe.

Grundlagen

Definition:  Ein Alphabet ist eine endliche, nichtleere Menge von Zeichen.

Sei A ein Alphabet. Ein Wort über A ist eine endliche Folge

w  =  w0 ... wn-1     mit  wi Element A,   n Element natürliche Zahlen0.

Hierbei ist |w| = n die Länge des Wortes w.

Das Wort der Länge 0 ist das leere Wort, es wird mit ε bezeichnet.

Der Begriff "Wort" nach dieser Definition bezeichnet also jede beliebige endliche Folge von Zeichen; die Bedeutung der Zeichen spielt keine Rolle. Insofern unter­scheidet sich der Begriff hier vom Begriff "Wort" im umgangs­sprachlichen Sinne.

Das Text­such­problem (engl.: string matching problem) stellt sich wie folgt: Gegeben ist ein Wort t, der Text, und ein kürzeres Wort p, der Suchbegriff oder das Muster. Gesucht sind alle Positionen i, an denen das Muster p im Text t vorkommt.

Definition:  Sei A ein Alphabet und seien t = t0 ... tn-1 und p = p0 ... pm-1  Wörter der Länge n bzw. m über A.

Ein Textfenster wi ist ein Teilwort von t der Länge m, das an Position i beginnt:

wi  =  ti ... ti+m-1

Ein Textfenster wi, das mit dem Muster p über­einstimmt, heißt Vorkommen des Musters an Position i:

wi  ist Vorkommen  genau dann wenn  p = wi

Ein Mismatch in einem Textfenster wi ist eine Position j, an der das Muster mit dem Textfenster nicht über­einstimmt:

j  ist Mismatch in wi  genau dann wenn  pj  ≠  (wi)j

 

Textsuchproblem
Eingabe:Text  t = t0 ... tn-1  und Muster   p = p0 ... pm-1 über einem Alphabet A
Ausgabe:Alle Positionen von Vorkommen von p in t, d.h.  { i  |  p = wi }

 

Beispiel:  

012345678...
jedes textverarbeit...
text

Das Muster p = text kommt an Position i = 6 im Text t vor.

Es sind auch überlappende Vorkommen des Musters möglich, wie in folgendem Beispiel:

Beispiel:  

012345678...
aaabaabacabca
aaba
aaba

Das Muster p = aaba kommt an den Positionen i1 = 1 und i2 = 4 im Text t vor.

Strategie

Der einfachste Algorithmus überprüft das Muster an allen Positionen i = 0, ...,  n-m. Das Muster wird an der jeweiligen Position zeichenweise von links nach rechts mit dem ent­sprechenden Textfenster verglichen. Bei einem Mismatch oder bei voll­ständiger Über­ein­stimmung wird das Muster um eine Position weiter­geschoben und an dieser Position verglichen usw. Dieser Algorithmus wird als der naive Algorithmus bezeichnet. Er benötigt im schlechtesten Fall n·m Zeichen­vergleiche.

Durch Ausnutzung unter­schiedlicher Informationen lässt sich die Anzahl der Zeichen­vergleiche verringern. Es gibt verschiedene Ansätze, alle untersuchen das Muster in einem Vorlauf (engl.: preprocessing), um Vorab­information über die Struktur des Musters und über die vorkommenden Zeichen zu gewinnen.

Struktur des Musters

In folgendem Beispiel stimmen die ersten vier Zeichen des Musters mit dem Text überein, das fünfte Zeichen führt zu einem Mismatch. Es ist in dieser Situation nicht nötig, das Muster an den Positionen i = 2, 3, und 4 zu vergleichen, sondern das Muster kann gleich bis Position i = 5 weiter­geschoben werden. Keines der Textzeichen t2, t3 und t4 kann nämlich ein a sein, denn die Textzeichen hatten ja mit den von a ver­schiedenen Zeichen c, b und e des Musters überein­gestimmt. Die nächste mögliche Über­ein­stimmung des Musters ist also an Position 5, wie im Beispiel gezeigt.

Beispiel:  

012345678...
aacbeabababca
acbed
acbed

Anders stellt sich die Situation in folgendem Beispiel dar. Das Muster kann nur um zwei Positionen weiter­geschoben werden, da ein Präfix des Musters (ab) als Suffix des über­einstimmenden Teils abab vorkommt.

Beispiel:  

012345678...
aacbeabababca
ababd
ababd

Es geht also in der Vorlaufphase darum, die Struktur des Musters daraufhin zu analysieren, wie weit es bei einem Mismatch an einer jeweiligen Position weiter­geschoben werden kann.

Vorkommende Zeichen

Ist ti ein Zeichen, das im Muster überhaupt nicht vorkommt, so kann das Muster an keiner der m Positionen i-m+1, ..., i über­einstimmen. In folgendem Beispiel kommt das e nicht im Muster vor. Das Muster kann daher bis hinter das e weiter­geschoben werden.

Beispiel:  

012345678...
ababeabababca
ababd
ababd

In der Vorlaufphase wird eine Tabelle angelegt, die für jedes Zeichen des Alphabets die Position seines letzten Vorkommens im Muster enthält, bzw. -1, falls das Zeichen nicht im Muster vorkommt.

Wahr­schein­lich­keit der Zeichen

Es ist prinzipiell nicht notwendig, die Zeichen des Musters von links nach rechts mit dem Text zu vergleichen, sondern sie können in beliebiger Reihenfolge verglichen werden. Ist die Wahr­schein­lich­keitsverteilung der Zeichen des Textes bekannt (oder zumindest annähernd bekannt), so kann es vorteilhaft sein, zuerst dasjenige Zeichen des Musters mit dem Text zu vergleichen, das die geringste Wahr­schein­lich­keit hat. Mit hoher Wahr­schein­lich­keit wird es dann zu einem Mismatch kommen, und das Muster kann weiter­geschoben werden.

Signatur

Anstatt das Musters mit dem jeweiligen Textfenster zeichenweise direkt zu vergleichen, wird bei diesem Ansatz ein indirekter Vergleich durchgeführt. Aus dem Muster wird ein Wert berechnet, die Signatur. Diese Signatur wird jeweils mit der Signatur des ent­sprechenden Textfensters verglichen. Nur dort, wo die Signaturen über­einstimmen, können auch Muster und Text über­einstimmen.

Philosophie

"Suchen" bedeutet "Versuchen, etwas zu finden". Wenn wir Vorkommen eines Musters in einem Text suchen, sollten wir uns eigentlich über jedes über­einstimmende Zeichen freuen. Um so größer wird schließlich die Hoffnung, ein Vorkommen zu finden.

Diese optimistische Heran­gehens­weise führt jedoch nicht zu besonders effizienten Algorithmen. Die effizientesten Algorithmen entstehen aus der Haltung des Pessimisten: "Wetten, das Muster kommt sowieso nicht vor." Der Algorithmus erbringt den Beweis, dass das Muster nirgendwo im Text vorkommen kann, außer möglicher­weise an ein paar Stellen. An diesen Stellen wird dann geprüft, ob das Muster dort tatsächlich vorkommt.

Die Strategie, dasjenige Zeichen des Musters zuerst zu vergleichen, das am wenigsten wahr­scheinlich über­einstimmt, geht in diese Richtung. Ein Optimist hätte zuerst das wahr­scheinlichste Zeichen verglichen.

Der Pessimist jubelt, wenn er auf ein Textzeichen trifft, das im Muster überhaupt nicht vorkommt. Der Optimist verfällt in, natürlich nur kurzlebige, Depressionen ob dieses Miss­geschicks. Der Pessimist darf, der Optimist muss, notgedrungen, das Muster hinter dieses Zeichen weiter­schieben.

Im Ergebnis macht der Optimist aufgrund seines Wunsch­denkens, das Muster könnte passen, mehr Vergleiche als der Pessimist.

Geschichte

Erstaunlich spät, erst 1974, erschien ein Algorithmus, der im schlechtesten Fall O(n) Vergleiche benötigt. Der Algorithmus von Knuth, Morris und Pratt [KMP 77] nutzt hierbei die Information über die Struktur des Musters aus, um unnötige Mehrfach­vergleiche zu vermeiden.

Aho und Corasick verall­gemeinerten diesen Ansatz für die gleich­zeitige Suche nach mehreren Mustern [AC 75].

Aufsehen erregte 1977 die Idee von Boyer und Moore, das Muster von rechts nach links zu vergleichen und außer der Struktur des Musters auch die vorkommenden Zeichen zu berück­sichtigen. Das Ergebnis ist ein sublinearer Algorithmus, der im Durchschnitt lediglich O(n/m) Vergleiche benötigt [BM 77].

Beim Boyer-Moore-Verfahren bestimmt sich die Schiebe­distanz durch das Vorkommen desjenigen Textzeichens, das zu einem Mismatch geführt hat. Das Verfahren von Horspool [Hor 80] verwendet stets das Vorkommen des ganz rechten Zeichens im Textfenster. Dies führt zu einer Ver­einfachung des Verfahrens; die Struktur des Musters braucht nicht mehr berück­sichtigt zu werden.

Noch weiter geht die Idee von Sunday [Sun 90], das Vorkommen des unmittelbar rechts neben dem Textfenster stehenden Zeichens zu verwenden, denn dieses Zeichen muss beteiligt sein, wenn das Muster an der nächsten Position verglichen wird. Diese kleine Veränderung erlaubt es darüber hinaus, die Vergleiche im Textfenster in beliebiger Reihenfolge durch­zuführen. Es kommt nicht mehr darauf an, möglichst weit rechts im Textfenster einen Mismatch zu entdecken, um das Muster möglichst weit verschieben zu können. Es kann somit eine Reihenfolge aufgrund der Wahr­schein­lich­keit der Zeichen gewählt werden.

Auf dem Signatur-Ansatz beruht das Verfahren von Karp und Rabin [KR 87]. Da es möglich ist, die Signatur eines Textfensters aus der Signatur des vorher­gehenden Textfensters in konstanter Zeit zu berechnen, erreicht das Verfahren eine Komplexität von O(n).

Mit Bitvektoren als Signaturen arbeitet der Shift-And-Algorithmus [WM 92]. Die Signatur des jeweiligen Fensters wird aus der Signatur des vorherigen Fensters durch eine Shift- und eine And-Operation von Bitvektoren der Länge m ermittelt. Der Algorithmus erreicht eine Komplexität von O(n), wenn die Shift- und die And-Operation in konstanter Zeit ausgeführt werden können, insbesondere also dann, wenn mkleiner gleich32 (z.Zt. Länge eines Maschinen­wortes) ist.

Literatur

Original­artikel:

Der Algorithmus [KMP 77] erschien 1974 als Instituts­bericht und erst 1977 in einer Fach­zeitschrift.

[AC 75]A.V. Aho, M.J. Corasick: Efficient String Matching: An Aid to Bibliographic Search. Communications of the ACM, 18, 6, 333-340 (1975)
[BM 77]R.S. Boyer, J.S. Moore: A Fast String Searching Algorithm. Communications of the ACM, 20, 10, 762-772 (1977)
[Hor 80]R.N. Horspool: Practical Fast Searching in Strings. Software - Practice and Experience 10, 501-506 (1980)
[KMP 77]D.E. Knuth, J.H. Morris, V.R. Pratt: Fast Pattern Matching in Strings. SIAM Journal of Computing 6, 2, 323-350 (1977)
[KR 87]R. Karp, M. Rabin: Efficient Randomized Pattern-Matching Algorithms. IBM Journal of Research and Development 31, 249-260 (1987)
[Sun 90]D.M. Sunday: A Very Fast Substring Search Algorithm. Communications of the ACM, 33, 8, 132-142 (1990)
[WM 92]S. Wu, U. Manber: Fast Text Searching Allowing Errors. Communications of the ACM 35, 10, 83-91 (1992)
Bücher:
[OW 90]T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. BI-Wissenschaftsverlag (1990)
[Sed 88]R. Sedgewick: Algorithms. 2. Auflage, Addison-Wesley (1988)
[Schö 97]U. Schöning: Algorithmen -- kurz gefasst. Spektrum (1997)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Alle hier erwähneten Textsuchverfahren (außer Karp-Rabin) finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Naiver Algorithmus]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 22.02.2001   Updated: 29.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik