Google
 
Web www.grundstudium.info
  Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Scanlines Aufwärts: Hauptseite Algorithmen Vorherige Seite: Netzwerkflußproblem   Inhalt

Unterabschnitte

Mustererkennung

Bei der Mustererkennung wird in einem Text ein Muster gesucht. Anwendung ist zum Beispiel eine Textverarbeitung, bei der ein String im Text gesucht wird. Aber es gibt auch andere Anwendungsbereiche, z.B. DNA Analyse oder Virenerkennung.

Naives Verfahren

Bei dem naiven Verfahren setzen wir das Muster immer um eine Position nach vorne und testen alle Stellen durch, ob kein Mismatch auftritt.
Dies erfordert dann $O(n\cdot k)$ Zeit.

KMP - Knuth, Morris und Pratt

Beim KMP-Algorithmus geht es darum, daß Muster, welches an den Text gelegt wird, um schon besuchte Zeichen im Text nach vorne zu schieben, bei denen man sicher gehen kann, daß sie nicht mit dem Wort übereinstimmen. Dafür benötigen wir eine Hilfsfunktion, welche einmalig für das Suchwort erstellt wird. In dieser Hilffunktion ist aufgezeichnet, wie groß der Rand des aktuellen schon verglichenen Präfixes des Suchwortes ist, wenn genau an der Stelle ein Fehler auftritt. Beispielsweise ist der Rand von $aba$ $a$, da das $a$ sowohl vorne als auch hinten vorhanden ist. Der Rand von $acbac$ ist $ac$. Der Rand für $abcabfg$ ist $ab$, falls nur bis zur 5. Position gelesen wird. In der Hilfsfunktion wird jeweils gespeichert, wie groß der Rand ist. Beispiel:
a a b a a b
0 1 0 1 2 3
Der Text wird nun überprüft, indem das Muster darunter gelegt wird. Wenn ein Mismatch auftritt, verschieben wir das Muster um $h(i)+1$ Stellen nach vorne. Also die Zahl in der Hilfsfunktionstabelle an der Stelle stehend +1.
Die Laufzeit dieses Verfahrens ist $O(n+k)$

Boyer-Moore

$\delta_{1}$:
Fall Aktion
1. X kommt in dem Muster rechts neben dem Zeiger vor / Die aktuelle Position hat einen Mismatch, da das Zeichen im Text X ist im Muster aber nicht Eine Position nach rechts verschieben. Der Worst-Case tritt dann auf, wen wir beispielsweise einen Text aus nur a's haben und das Muster baa in diesem suchen. Jedesmal wird ein Mismatch a$\not=$b erzeugt und es darf nur eine Position weiter gerutscht werden.
2. X kommt in dem Muster links neben dem Zeiger vor. / Im Text steht ein X aber im Muster nicht. Das Muster wird so verschoben, daß das erste X im Suchstring an der Zeigerposition steht.
3. Es gibt gar kein X im Muster Wir können das Muster um die ganze Länge des Musters nach rechts verschieben.
$\delta_{2}$: Diese Heuristik ist dafür da, um den Fall 1 besser zu machen, d.h. um mehr Stellen nach rechts zu gehen.
next up previous contents
Nächste Seite: Scanlines Aufwärts: Hauptseite Algorithmen Vorherige Seite: Netzwerkflußproblem   Inhalt