Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMittwoch, 22. Mai 2013 

String-Matching-Algorithmen


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
String-Matching-Algorithmen etwa Zeichenketten -Übereinstimmungs- oder Zeichenketten-Such- Algorithmen befassen sich mit dem Problem eine Zeichenkette Suchmaske genannt innerhalb einer anderen Text genannt zu finden. Das Problem besteht diese Aufgabe möglichst effizient zu lösen.

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

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

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

Unter UNIX erlaubt das grep-Kommando die Textsuche in

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 etwa die Wikipedia derart aufzubereiten dass beliebige Suchmasken schnell effizient aufgefunden werden. Auch Suchmaschinen im Internet finden sich in der Situation.

Im folgenden wird jedoch nur auf erste Situation eingegeangen.

Lösungsmethoden

Naiver Algorithmus

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

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

Der Morris-Pratt-Algorithmus

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

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

Weitere Algorithmen

  • Knuth-Morris-Pratt-Algorithmus
  • Boyer-Moore-Algorithmus
    • Modifizierter Boyer-Moore-Algorithmus
  • Horspool-Algorithmus
  • Sunday-Algorithmus
  • Skip-Search-Algorithmus
  • Karp-Rabin-Algorithmus
  • Shift-And- (Shift-Or-)Algorithmus

Approximative Suche

Zunächst muss festgelegt werden bis zu Fehlerschwelle gefundene Strings noch als ungefähre Suchtreffer dürfen. Dafür wurde das Konzept der edit distance formuliert das zählt wieviel der folgenden minimal den einen in den anderen String

  1. Einfügen eines Zeichens
  2. Löschen eines Zeichens
  3. Verändern eines Zeichens

Siehe auch: Baum (Datenstruktur) Endlicher Automat

Weblinks

  • http://www-igm.univ-mlv.fr/~lecroq/string/ - Java-Animationen die die Funktionsweise so wie aller exakten Suchalgorithmen veranschaulichen. Sehr empfehlenswert!




Bücher zum Thema String-Matching-Algorithmen

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/String-Matching-Algorithmen.html">String-Matching-Algorithmen </a>