String-Matching-Algorithmus - LinkFang.de





String-Matching-Algorithmus


Dieser Artikel oder Abschnitt bedarf einer Überarbeitung.

In der Informatik sind String-Matching-Algorithmen eine Gruppe von Algorithmen, die das Finden von Textsegmenten in einer Zeichenkette (engl. string) anhand eines vorgegebenen Suchmusters beschreiben. Sie zählen somit zur Klasse der Zeichenkettenalgorithmen.

Im engeren Sinne suchen diese Algorithmen nach exakten Übereinstimmungen (engl. matches). Im weiteren Sinne sind auch Algorithmen gemeint, die ungefähre Übereinstimmungen zulassen, wobei der Begriff ungefähr durch ein Toleranzkriterium genau definiert sein muss.

Das Problem besteht darin, diese Aufgabe möglichst effizient zu lösen. In der Praxis ist dies bedeutsam, wenn in großen Textmengen (wie z. B. einer Wikipedia) Suchbegriffe gefunden werden sollen.

Exakte Suche

Problemstellung

Grundsätzlich sind zwei Situationen zu unterscheiden:

  1. Nach Vorgabe einer Suchmaske 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 [math]\textstyle \mathcal{O} (n \cdot m )[/math], 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 P[1] = T[q+1] and P[2] = T[q+2] andand P[m] = T[q+m] then
      write 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 ungünstigsten Fall selbst ansieht. Er lautet

Text:   aaa...aab
Muster: ab

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

Endlicher Automat

Bei dem String-Matching-Algorithmus mit Hilfe von endlichen Automaten wird ein für ein Alphabet [math]\Sigma[/math] und ein gegebenes Suchmuster der Länge [math]m[/math] ein Automat [math](Q, \Sigma, \delta, q_0, \{q_m\})[/math] mit Zustandsmenge [math]\textstyle Q = \{q_i \mid 0 \le i \le m\}[/math] erstellt. Dabei stellt [math]\textstyle i[/math] die Anzahl von übereinstimmenden Buchstaben an der aktuellen Stelle vom Anfang des Suchmusters an betrachtet dar. Zur Einfachheit sei [math]\textstyle P_i[/math] der Präfix des Suchmusters bis einschließlich dem Buchstaben an der Stelle [math]\textstyle i[/math]. Die Übergangsfunktion [math]\delta(q_i, a)[/math] mit [math]a \isin \Sigma[/math] gibt nun für [math]0 \le i \le m - 1[/math] wieder einen Zustand [math]q_j[/math] zurück, bei dem [math]j[/math] die maximale Anzahl von Buchstaben darstellt, mit der [math]P_j[/math] ein Suffix vom Wort [math]P_i a[/math] ist. Also [math]\delta(q_i, a) = q_{max\{j \mid P_j \text{ ist Suffix von } P_i a\}}[/math]. Ist das Suchmuster gefunden, wird im Endzustand verharrt, also [math]\delta(q_m, a) = q_m[/math].

Der Vorteil dieses Algorithmus gegenüber dem naiven Algorithmus liegt darin, dass er auch beim finden eines nicht-passenden Zeichens das erlangte Wissen über den bereits verarbeiteten Teil der Zeichenkette nicht verwirft. Angenommen, wir suchen das Muster anax im Text ananax. Trifft der automatenbasierte Algorithmus bei der Suche auf das Zweite n in ananax, so wird er die ersten beiden Buchstaben verwerfen und beginnend mit ananax" weitersuchen. Der naive Algorithmus hingegen hätte den kompletten bereits verarbeiteten Teil verworfen und hätte beginnend mit ananax einen nächsten Versuch begonnen.

Python-Implementation

def is_suffix(suffix, word):
    '''Überprüft ob der suffix ein Suffix von word ist.'''
 
    return word.endswith(suffix)
 
def transition(pattern, state, event):
    '''Hier wird die Übergangsfunktion berechnet.'''
 
    for k in range(state + 1, 0, -1):
        if is_suffix(pattern[:k], pattern[:state] + event):
            return k
    return 0
 
def create_matcher(alphabet, pattern):
    '''Erzeugt alle Zustände und eine Übergangsfunktions-Tabelle'''
 
    transition_table = {}
    for state in range(0, len(pattern) + 1):
       for event in alphabet:
            transition_table[(state, event)] = \
                transition(pattern, state, event)
    return transition_table, len(pattern)
 
def match(matcher, text):
    '''Gibt die gefundenen Treffer im Text mit dem Automaten der aus create_matcher
    erstellt wurde.'''
 
    transition_table, last_state = matcher
    matches = []
    state = 0
    text_pos = 0
    for text_pos in range(0, len(text)):
        state = transition_table[(state, text[text_pos])]
        if state == last_state:
            matches.append(text_pos - last_state + 1)
    return matches
 
def find(alphabet, pattern, text):
    matcher = create_matcher(alphabet, pattern)
    return match(matcher, text)

Der Knuth-Morris-Pratt-Algorithmus

Der Knuth-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 in [math]\textstyle \mathcal{O}(n)[/math] erfolgen. Anschließend kann jedes Muster ohne erneute Vorbereitung des Texts in [math]\textstyle \mathcal{O}(m)[/math] 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

Algorithmus Vorbereitungszeit Suchzeit
Naiver Algorithmus [math]0[/math] (keine) [math]\Theta \left(\left(n-m+1\right) \cdot m\right)[/math]
Rabin-Karp-Algorithmus [math]\Theta \left(m\right)[/math] average [math]\Theta \left(n+m\right)[/math],
worst [math]\Theta \left(n \cdot m\right)[/math]
Endlicher Automat [math]\mathcal{O} \left(m \cdot | \Sigma | \right)[/math] [math]\Theta \left(n\right)[/math]
Knuth-Morris-Pratt-Algorithmus [math]\Theta \left(m\right)[/math] [math]\Theta \left(n\right)[/math]
Boyer-Moore-Algorithmus[2] [math]\Theta \left(m\right)[/math] average [math]\Theta \left(n/m\right)[/math],
worst [math]\Theta \left(n \cdot m\right)[/math]
Shift-Or-Algorithmus (Bitap Algorithmus, Baeza-Yates-Gonnet) [math]\Theta \left(m + | \Sigma | \right)[/math] [math]\Theta \left(n\right)[/math]
Suche im Suffixbaum [math]\Theta \left(n\right)[/math] [math]\Theta \left(m\right)[/math]

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: unscharfe Suche und 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

Weblinks

Einzelnachweise

  1. Dan Gusfield: Algorithms on Strings, Sequences and Trees. 1999 [1997], ISBN 0-521-58519-8, Kapitel 7.1.APL1.
  2. R. S. Boyer, J. S. Moore: A fast string searching algorithm. In: Communications of the ACM. 20, 1977, S. 762–772. doi:10.1145/359842.359859 .

Kategorien: Suchalgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/String-Matching-Algorithmus (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.