String Matching

String Matching
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

String-Matching-Algorithmen, etwa Zeichenketten-Übereinstimmungs- oder Zeichenketten-Such-Algorithmen, sind mathematische Formeln, die sich mit dem Problem befassen, eine gegebene Zeichenkette, Suchmaske genannt, innerhalb einer anderen, Text genannt, zu finden.

Unter einer Zeichenkette versteht man in diesem Zusammenhang eine geordnete Kette von Symbolen, die aus einem Alphabet stammen.

Das Problem besteht darin, diese Aufgabe möglichst effizient zu lösen. Sie zählen somit zur Klasse der Zeichenkettenalgorithmen.

Im engeren Sinne suchen die hier angesprochenen Algorithmen nach exakten Übereinstimmungen (matches). Im weiteren Sinne werden auch Algorithmen eingeschlossen, die "ungefähre" Übereinstimmungen zulassen, wobei der Begriff ungefähr durch ein Toleranzkriterium genau definiert sein muss.

Eine derartige Suche wird dann interessant, wenn ein großer Korpus von Strings, wie etwa die Wikipedia, nach z. B. Begriffen durchsucht werden soll.

Inhaltsverzeichnis

Exakte Suche

Problemstellung

Grundsätzlich sind zwei Situationen zu unterscheiden:

  1. Die Suchmaske ist vorgegeben, und dann sollen beliebige Texte durchsucht werden.
  2. Der Text ist vorgegeben, und dann sollen beliebige Suchmasken im Text gefunden werden.

Der zweite Fall entspricht etwa der Aufgabe, die Wikipedia derart aufzubereiten, dass beliebige Suchmasken schnell und effizient aufgefunden werden. Auch Suchmaschinen im Internet finden sich in der zweiten Situation.

Im Folgenden wird jedoch nur auf die erste Situation eingegangen.

Lösungsmethoden

Naiver Algorithmus

Der einfachste Algorithmus besteht darin, ein so genanntes Suchfenster von der Länge der Suchmaske über den Text zu schieben. In jeder Position der Suchmaske werden die Symbole der Maske mit denen des darunterliegenden Textes verglichen. Wenn ein nichtübereinstimmendes Symbol gefunden wird, wird das Fenster um eine Position verschoben, und erneut ein Vergleich angestellt; wenn alle Symbole im Fenster übereinstimmen, ist die Suchmaske gefunden worden. Der Algorithmus endet, wenn der ganze Text vom Fenster abgesucht worden ist.

Dieser Algorithmus hat eine Laufzeit von der Ordnung O=n*m, wenn m die Länge der Suchmaske und n die Länge des Textes ist.

Pseudocode

Eingabe: Strings T = T1... Tn und P = P1 ... Pm
Ausgabe: q die Stellen an denen P in T auftritt
For q = 0 to n − m do
    If P1 = Tq+1 and P2 = Tq+2 and ... and Pm = Tq+m:
    Print q

Überraschenderweise ist der naive Ansatz in der Praxis sehr schnell, da Fehler in natürlichsprachigen Texten nach 1 bis 2 Zeichen auftauchen. Für die englische Sprache ergibt sich eine Wahrscheinlichkeit von 1.07 Zeichen. Somit ist der naive Ansatz nahezu linear schnell.

Dies wird auch deutlich wenn man sich den Worst-Case selbst ansieht. Er lautet

Text:   aaa...aab
Muster: ab

Derartige Fälle sind in natürlich sprachlichen Texten äußerst unwahrscheinlich.

Der Morris-Pratt-Algorithmus

Der Morris-Pratt Algorithmus baut auf dem naiven Suchalgorithmus auf. Wesentlicher Unterschied ist, dass das Vergleichsfenster nicht immer um nur eine Position weitergerückt wird, sondern eventuell um mehr als eine Position.

Dazu muss zu Anfang die Suchmaske analysiert werden, so dass bei jeder teilweisen Übereinstimmung, etwa der ersten k Symbole, bekannt ist, ob der Anfang der Suchmaske mit dem Ende der letzten übereinstimmenden Teilmaske übereinstimmt. Die Verschiebung der Suchmaske erfolgt nach der überlappenden Übereinstimmung; zusätzlicher Vorteil ist, dass die schon verglichenen Symbole nicht noch einmal verglichen werden müssen.

Suche im Suffixbaum

Insbesondere, wenn der zu durchsuchende Text im voraus bekannt ist, und in diesem später nach vielen unterschiedlichen Mustern gesucht werden soll, bietet sich die Konstruktion eines Suffixbaums an. Diese Konstruktion kann O(n) erfolgen. Anschließend kann jedes Muster ohne erneute Vorbereitung des Texts in O(m) gesucht werden: Sofern es vorhanden ist, kann man von der Quelle des Suffixbaums den entsprechenden Knoten erreichen, ansonsten schlägt die Suche fehl (es ist kein entsprechender Knoten vorhanden).[1]

Übersicht

Vorbereitungszeit Suchzeit
Naiver Algorithmus 0 (keine) Θ(n m)
Karp-Rabin-Algorithmus Θ(m) average Θ(n+m),
worst Θ(n m)
Endlicher Automat O(m |Σ|) Θ(n)
Knuth-Morris-Pratt-Algorithmus Θ(m) Θ(n)
Boyer-Moore-Algorithmus Θ(m) average Θ(n/m),
worst Θ(n)
Shift-Or-Algorithmus (Bitap Algorithmus, Baeza-Yates-Gonnet) Θ(m+|Σ|) Θ(n)
Suche im Suffixbaum Θ(n) Θ(m)

Wobei m die Länge der Suchmaske und n die Länge des Textes ist.

Weitere Algorithmen

Mustervergleichssuche

Hauptartikel: Pattern Matching

Die Suche nach Mustern ist zwischen unscharfer und exakter Suche anzusiedeln, da der Benutzer explizit angeben muss, welchen Spielraum er für bestimmte Zeichenklassen an bestimmten String-Positionen zulässt.

Unscharfe Suche

Hauptartikel: Fuzzy-Suche, Phonetische Suche

Bei der unscharfen Suche entscheidet üblicherweise der Algorithmus nach Vorgabe eines Güte- oder Abstandskriteriums, wie groß die Abweichung von Treffern gehen darf.

Siehe auch

Suchverfahren, Levenshtein-Distanz (Approximative Suche), Volltextrecherche

Einzelnachweise

  1. Gusfield, Dan (1999 [1997]) Algorithms on Strings, Sequences and Trees. ISBN 0-521-58519-8. Kapitel 7.1.APL1.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • String-Matching-Algorithmen — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. String Matching Algorithmen, etwa Zeichenketten Übereinstimmungs… …   Deutsch Wikipedia

  • String-Matching-Algorithmus — Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf… …   Deutsch Wikipedia

  • Aho–Corasick string matching algorithm — The Aho–Corasick string matching algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary matching algorithm that locates elements of a finite set of strings (the dictionary ) within …   Wikipedia

  • Approximate string matching — In computing, approximate string matching is the technique of finding approximate matches to a pattern in a string. The closeness of a match is measured in terms of the number of primitive operations necessary to convert the string into an exact… …   Wikipedia

  • String searching algorithm — String searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. Let Σ be… …   Wikipedia

  • String metric — String metrics (also known as similarity metrics) are a class of textual based metrics resulting in a similarity or dissimilarity (distance) score between two pairs of text strings for approximate matching or comparison and in fuzzy string… …   Wikipedia

  • Matching — may refer to: Matching (graph theory), in graph theory, a set of edges without common vertices Matching (statistics), a technique for reducing bias when analyzing data from observational studies String matching, in computer science Matchmaking,… …   Wikipedia

  • Matching (disambiguation) — Matching may refer to:* Matching, in graph theory, a set of edges without common vertices * String matching * Impedance matching and Impedance bridging, in electronics, attempting to make the output impedance of a source equal to the input… …   Wikipedia

  • String-Algorithmus — Bei Zeichenkettenalgorithmen (englisch string algorithms) handelt es sich um Algorithmen, die auf Zeichenketten arbeiten. Dabei werden beispielsweise Übereinstimmungen innerhalb eines oder zwischen mehreren Zeichenketten gesucht. Anwendungen sind …   Deutsch Wikipedia

  • String (computer science) — In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet. In computer programming, a string is traditionally a sequence of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”