Folien als PDF

13 Suche in Texten
13.1 Suchen in Texten
13.2 Brute Force
13.3 Knuth-Morris-Pratt
13.4 Boyer-Moore
13
13.5 Pattern Matching und Automaten
181
13 Suche in Texten
Teil XIII
Suche in Texten
Überblick
Suchen in Texten
Brute Force
Knuth-Morris-Pratt
Boyer-Moore
Pattern Matching und Automaten
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–1
Suchen in Texten
◮
◮
Problem: Suche eines Teilwortes in einem (langem)
anderen Wort
typische Funktion der Textverarbeitung
→ effiziente Lösung gesucht
◮ Maß der Effizienz: Anzahl der Vergleiche zwischen
Buchstaben der Worte
◮
Begriffe: String-Matching als Vergleich von Zeichenketten,
Mismatch als nicht übereinstimmende Position
Saake/Schallehn
182
Algorithmen & Datenstrukturen II
13–2
Uni Magdeburg, WS 2005/06
13 Suche in Texten
Probleme der Worterkennung
Direkte Lösung (brute force):
◮
a
a
1
b
a
b
a
2
3
a
b
c
c
4
a
a
5
a
b
a
c
c
a
b
a
c
a
b
a
a
b
b
b
6
a
c
a
b
b
a
c
a
7
a
8
b
9
a
22
Saake/Schallehn
b
23
a
24
c
25
a
26
b
27
Algorithmen & Datenstrukturen II
13–3
Vorgegebene Daten
Worte als Array:
◮
◮
◮
text[] zu durchsuchender Text
pat[] ‘Pattern’, gesuchtes Wort
Wortlängen:
◮
◮
◮
13
◮
n Länge des zu durchsuchenden Textes
m Länge des gesuchten Wortes
Σ Alphabet, ǫ leerer String
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–4
Naiver Algorithmus
for i=1 to n − m + 1 do
Prüfe ob pat = text[i...i + m − 1]
◮
Auch: Brute Force Algorithmus
Saake/Schallehn
Algorithmen & Datenstrukturen II
Uni Magdeburg, WS 2005/06
13–5
183
13 Suche in Texten
Algorithmus: Brute Force
i := 1
WHILE i <= n-m+1 DO
j := 1
WHILE j <= m AND pat[j] = text[i+j-1] DO
j := j+1
END
IF j = m+1 THEN RETURN TRUE
i := i+1
END
RETURN FALSE
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–6
Algorithmus: Brute Force /2
Analyse:
◮
Komplexität (worst case): O((n − m) ∗ m) = O(nm)
◮
Zusätzlicher Platzbedarf: O(1)
◮
Ziel: Verbesserung der Laufzeitkomplexität, ggf. unter
Verschlechterung beim Platzbedarf
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–7
Verschiedene bessere Algorithmen
Knuth-Morris-Pratt: Idee: verschiebe Wort mehr als eine Stelle
nach rechts basierend auf bisherigen Tests
Boyer-Moore: Idee: Beginne hinten zu testen
Saake/Schallehn
184
Algorithmen & Datenstrukturen II
13–8
Uni Magdeburg, WS 2005/06
13 Suche in Texten
Knuth-Morris-Pratt
Idee: nutze bereits gelesene Information bei einem
Mismatch
◮
Kommt es an Stelle j von pat zum Mismatch, so gilt:
◮
pat[1...j − 1] = text[i...i + j − 2]
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–9
a
a
1
b
b
2
a
a
3
c
c
4
a
a
5
a
a
b
a
c
c
a
c
a
b
a
b
a
c
a
a
c
a
b
b
a
a
b
13
Knuth-Morris-Pratt /2
b
b
6
b
7
a
8
b
9
a
10
c
11
a
b
12
a
b
13
a
14
Saake/Schallehn
b
15
a
16
c
17
a
18
b
19
Algorithmen & Datenstrukturen II
13–10
Knuth-Morris-Pratt: Realisierung mit
Fehlerfunktion
◮
◮
Bestimme für jedes j Länge f [j] des längsten Präfix von
pat der Suffix von pat[1...j] ist
Fehler an Stelle j → verschiebe Suchposition im Muster
auf j := f [j − 1] + 1 = border [j]
Position j im Pattern
Pattern pat[j]
Längster Präfix f[j]
Verschiebeposition
1
a
0
0
2
b
0
1
3
a
1
1
4
c
0
2
5
a
1
1
6
b
2
2
◮ hier: Realisierung mit Fehlerfunktion nach Goodrich / Tamassia; später:
elegantere Darstellung durch endliche Akzeptoren
Saake/Schallehn
Algorithmen & Datenstrukturen II
Uni Magdeburg, WS 2005/06
13–11
185
13 Suche in Texten
Knuth-Morris-Pratt im Detail
◮
Preprocessing: Bestimme für jedes j, 1 ≤ j ≤ m das größte
k so daß
pat[1...k − 1] ist echter Suffix von pat[1...j − 1]
Genauer berechnet und als border bezeichnet:
border [j] = max {k | pat[1...k − 1] = pat[j − k + 1...j − 1]}
1≤k ≤j−1
◮
bei Mismatch an Position j verschiebe
Position im Text auf i := i + j − border [j] und
Position im Suchmuster auf j := border [j] oder 1 falls
nicht definiert (z.B. erste Position)
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–12
Die border-Tabelle
◮
1
a
0
◮
Beispiel (drei Zeilen: j, pat[j], border [j]):
2
b
1
3
a
1
4
a
2
5
b
2
6
a
3
7
b
4
8
a
3
9
a
4
10
b
5
11
a
6
12
a
7
13
b
5
j
pat[j]
border[j]
Bemerkung: Beispiel ist sogenannter Fibonacci-String F7 :
1. F0 = ǫ, F1 = b, F2 = a
2. Fn = Fn−1 Fn−2
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–13
Berechnung von border
/* Computation of the Border-Table */
border[1] := 0
FOR j := 2 TO m DO border[j] := 1
j = 1; i = 2
WHILE i <= m DO
WHILE i+j-1 <= m AND pat[j] = pat[i+j-1] DO
j := j+1
border[i+j-1] := j
END
i := i+j-border[j]
j := MAX(border[j], 1)
END
Saake/Schallehn
186
Algorithmen & Datenstrukturen II
13–14
Uni Magdeburg, WS 2005/06
13 Suche in Texten
sborder als Verbesserung von border
Problem:
pat:
a b a a b a - text: - - - - - - a b a a b c - Mismatch an Stelle j = 6, border [6] = 3 → verschiebe um
j − border [j] = 3
pat:
a b a a b a - text: - - - - - - a b a a b c - Resultat: sofort wieder Mismatch!
Verbesserungspotential: Wir wissen bereits, daß an der
Mismatch-Stelle kein a stehen kann.
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–15
sborder als Verbesserung von border /2
Verbesserung:
13
◮
sborder [j] = max {k | pat[1...k −1] = pat[j−k +1...j−1]∧pat[k ] 6= pat[j]}
1≤k ≤j−1
◮
Falls kein derartiges k existiert dann 0
◮
Beispiel (vier Zeilen: j, pat[j], border [j], sborder [j]):
1
a
0
2
b
1
3
a
1
4
a
2
5
b
2
6
a
3
7
b
4
8
a
3
9
a
4
10
b
5
11
a
6
12
a
7
13
b
5
j
pat[j]
border[j]
0
1
0
2
1
0
4
0
2
1
0
7
1
sborder[j]
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–16
Algorithmus: Knuth-Morris-Pratt /1
/* Algorithm: Knuth/Morris/Pratt */
i := 1
j := 1
WHILE i <= n-m+1 DO
WHILE j <= m AND pat[j] = text[i+j-1] DO
j := j+1
END
IF j = m+1 THEN RETURN TRUE
i := i+j-sborder[j]
j := MAX(sborder[j],1)
END
RETURN FALSE
Saake/Schallehn
Algorithmen & Datenstrukturen II
Uni Magdeburg, WS 2005/06
13–17
187
13 Suche in Texten
Algorithmus: Knuth-Morris-Pratt /2
/* Computation of the Border-Table */
FOR j := 1 TO m DO sborder[j] := 0
j = 1; i = 2
WHILE i <= m DO
WHILE i+j-1 <= m AND pat[j] = pat[i+j-1] DO
j := j+1
IF i+j-1 <= m THEN
sborder[i+j-1] := sborder[j]
END
IF i+j-1 <= m THEN
sborder[i+j-1] := MAX(j, sborder[i+j-1])
i := i+j-sborder[j]
j := MAX(sborder[j], 1)
END
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–18
Komplexität: Knuth-Morris-Pratt
◮
Komplexität: O(n + m)
◮
◮
◮
O(n) für Schleife
O(m) für Berechnung von border
Platzbedarf: O(m)
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–19
Beispiel KMP
a b a a b a b a a b a a b
a b a a b a b a a b a c a b a a b a b a a b a a b
a b a a b a b a a b a a b
a b a a b a b a a b a c a b a a b a b a a b a a b
a b a a b a b a a b a a b
a b a a b a b a a b a c a b a a b a b a a b a a b
a b a a b a b a a b a a b
a b a a b a b a a b a c a b a a b a b a a b a a b
a b a a b a b a a b a a b
a b a a b a b a a b a c a b a a b a b a a b a a b
Saake/Schallehn
188
Algorithmen & Datenstrukturen II
13–21
Uni Magdeburg, WS 2005/06
13 Suche in Texten
Beispiel KMP /2
◮
erster Mismatch: i = 1, j = 12, sborder [12] = 7
führt zu i = 1 + 12 − sborder [12] = 6 und j = sborder [12] = 7.
◮
zweiter Mismatch: i = 6, j = 7, sborder [7] = 4
führt zu i = 6 + 7 − sborder [7] = 9 und j = sborder [7] = 4.
◮
dritter Mismatch: i = 9, j = 4, sborder [4] = 2
führt zu i = 9 + 4 − sborder [4] = 11 und j = sborder [4] = 2.
◮
vierter Mismatch: i = 11, j = 2, sborder [2] = 1
führt zu i = 11 + 1 − sborder [2] = 11 und j = sborder [2] = 1.
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–22
Boyer-Moore
◮
◮
13
Basisidee:
Vergleich von rechts nach links ermöglicht Verschiebung
um mehr Positionen (bis zu m)
bei wiederkehrenden Teilmustern kann Verschieben
ähnlich KMP eingesetzt werden
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–23
Boyer-Moore: Heuristiken
◮
bad character- oder occurence-Heuristik
◮
◮
◮
Verschieben um die gesamte Wortlänge,
bis zum letzten Auftreten des geflesenen Buchstabens.
Die good suffix- oder match-Heuristik, für die die
Verschiebedistanzen aus der Struktur des Musters
abgeleitet werden.
Saake/Schallehn
Algorithmen & Datenstrukturen II
Uni Magdeburg, WS 2005/06
13–24
189
13 Suche in Texten
Boyer-Moore: Vergleich des letzten Zeichens I
A C B B A D A B C A B A
…
A B C A A B
A B C A A B
◮
gelesenes Zeichen kommt im Muster nicht vor
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–25
Boyer-Moore: Vergleich des letzten Zeichens II
A C B B A C A B C A B A
…
A B C A A B
A B C A A B
◮
gelesenes Zeichen kommt im Muster nicht vor
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–26
Boyer-Moore: Verschiebung bei
Muster-Nichtübereinstimmung
C B A B B C B B C A B A
…
A B B C B C
A B B C B C
◮
Fall 1: Es gibt noch ein weiteres Vorkommen der
gelesenen Zeichenfolge im Muster.
Saake/Schallehn
190
Algorithmen & Datenstrukturen II
13–27
Uni Magdeburg, WS 2005/06
13 Suche in Texten
Boyer-Moore: Verschiebung bei
Muster-Nichtübereinstimmung
B A A B B C A B C A B A
…
B C A A B C
B C A A B C
◮
Fall 2: Ein Präfix des Musters stimmt mit einem Teil des
Suffixes überein.
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–28
13
Boyer-Moore: Verschiebung bei
Muster-Nichtübereinstimmung
C B A B B C B B C A B A
…
A B B A B C
A B B A B C
◮
Fall 3: Der Suffix tritt — auch nicht teilweise — im Muster
nicht wieder auf.
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–29
Boyer-Moore: Grösseres Beispiel
a
b
a
c
a
a
b
a
c
a
a
b
a
c
c
a
c
a
a
b
a
c
a
b
a
a
b
b
b
1
a
b
a
c
4
a
3
a
b
2
b
b
5
a
b
a
9
c
8
a
7
a
15
Saake/Schallehn
b
6
b
14
a
13
c
12
Algorithmen & Datenstrukturen II
Uni Magdeburg, WS 2005/06
a
11
b
10
13–30
191
13 Suche in Texten
Boyer-Moore: Benötigte Tabellen
◮
◮
last-Tabelle, die für jedes Zeichen des Textes (oder
praktischerweise des zugrunde liegenden Alphabets) die
sichere Verschiebedistanz speichert
shift-Tabelle, die zu jedem Suffix des Musters, das
eventuell zu einer Nichtübereinstimmung führen kann, die
sichere Verschiebedistanz enthält.
Konkret bedeutet dies, dass nach der Übereinstimmung
zwischen dem Teilmuster pat[j + 1 . . . m − 1] und dem Text
und einer Nichtübereinstimmung von pat[j] der Wert shift[j]
die mögliche Distanz zur Verschiebung liefert.
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–31
Boyer-Moore: last-Tabelle
Für ein Muster pat der Länge m mit pat = p0 p1 . . . pm−1 und ein
Alphabet Σ kann last(pat, a) für alle c ∈ Σ wie folgt bestimmt
werden:
last[c] = max{j | pj = c}
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–32
Boyer-Moore: shift-Tabelle
◮
Berechnung basiert auf zwei Bedingungen:
◮
Shift-Condition: Cs(i, s): für jedes k mit i < k < m gilt:
s ≥ k ∨ pat[k − s] = pat[k ]
◮
Occurence-Condition: Co(i, s): wenn s < i dann gilt:
pat[i − s] 6= pat[i]
◮
Für alle i mit 0 ≤ i < m berechnen sich die Werte der
Tabelle wie folgt:
shift[i + 1] = min{s > 0 | Cs(i, s) und Co(i, s) gelten}
◮
shift[0] wird auf m gesetzt
Saake/Schallehn
192
Algorithmen & Datenstrukturen II
13–33
Uni Magdeburg, WS 2005/06
13 Suche in Texten
Boyer-Moore: suffix-Tabelle
◮
Hilfsfeld suffix mit
suffix[i] = max{k | pat[i − k + 1 . . . i] = pat[m − k . . . m − 1]}
für alle i mit 1 ≤ i < m
◮
Dieses Hilfsfeld enthält an der Position i die Länge der
längsten Zeichenfolge, die gleichzeitig Suffix des
gesamten Musters und des Teilmusters pat[0 . . . i] ist.
k
k
pat
i
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–34
Boyer-Moore: Beispiel
13
Muster „ACBABCBA“
A A B B A C C B A C B A C B A B C B A
A C B A B C B A
shift=1
A C B A B C B A
shift=4
A C B A B C B A
last=2
shift=4
A C B A B C B A
A C B A B C B A
c
last[i]
i
pat[i]
suffix[i]
shift[i]
Saake/Schallehn
0
A
1
7
1
C
0
7
A
7
B
6
C
5
2
B
0
7
3
A
3
7
4
B
0
4
D
-1
5
C
0
7
6
B
0
7
7
A
8
1
8
0
0
Algorithmen & Datenstrukturen II
13–35
Boyer-Moore: Pseudo-Code
algorithm BMSearch (text, pat)
Eingabe: zu durchsuchender Text text der Länge n,
gesuchtes Muster pat der Länge m
i := 0;
while i ≤ n − m do
j := m − 1;
while j ≥ 0 ∧ pat[j] 6= text[i + j] do j := j − 1 od;
if j < 0 then
return i
else
i := i + max(shift[j + 1], j − last[text[i + j]])
fi
od;
return -1
Saake/Schallehn
Algorithmen & Datenstrukturen II
Uni Magdeburg, WS 2005/06
13–36
193
13 Suche in Texten
Pattern Matching und Automaten
Motivation:
◮
◮
einheitliches Modell für die Mustererkennung
erweiterte Suchfunktion nach regulären Ausdrucken
◮
◮
◮
◮
◮
◮
Sequenz
Oder / Disjunktion
Wildcards: Überspringe einen Buchstaben
Hüllenbildung: Wiederholung (0 bis n mal)
optionale Teile, Auswahl, etc
Werkzeuge wie grep, awk, Standardfunktionen beim
Auflisten von Dateinamen
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–37
Beispiel: Reguläre Ausdrücke in Unix-Systemen
◮
. : Wildcard
◮
a* : beliebige Anzahl von a
◮
[abc] : irgendein Buchstabe der Aufzählung
◮
Spezialzeichen für Zeilenbeginn, Zeilenende
◮
a+ : beliebige Anzahl größer 0 von a
◮
a? : genau 0 oder 1 mal a
◮
| : Alternative, () : Gruppierung,
Metazeichenumwandlung, etc
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–38
Endliche Akzeptoren
auch: endliche nichtdeterministische (Zustands-) Automaten
◮
S Menge von Zuständen (states)
◮
Alphabet Σ
◮
s0 ∈ S initialer Zustand
◮
◮
F ⊆ S Menge der Endzuständen
Übergangsfunktion move, die ein Paar (s, a), bestehend
aus Zustand s ∈ S und Symbol a ∈ Σ ∪ ǫ (), auf eine
Menge von Zuständen abbildet
◮
ǫ steht hier für den leeren String
Saake/Schallehn
194
Algorithmen & Datenstrukturen II
13–39
Uni Magdeburg, WS 2005/06
13 Suche in Texten
Arbeitsweise von Akzeptoren
◮
◮
◮
◮
markierter gerichteter Graph
Ausgehend vom Startzustand wird mit jedem gelesenen
Zeichen die Übergangsfunktion ausgewertet und
gegebenfalls ein neuer Zustand eingenommen. Ist ein
Endzustand erreicht, so wurde der Ausdruck erkannt.
Anders ausgedrückt, ein Automat akzeptiert eine
Zeichenfolge genau dann, wenn es einen Pfad vom
Startzustand zu einem Endzustand gibt und die
Markierungen der Kanten des Pfades exakt diese
Zeichenfolge bilden.
Ergebnis einer Wortabarbeitung ist eigentlich eine Menge
von Zuständen enstprechend möglichen korrekten Pfaden
◮
nichtdeterministischer endlicher Automat NEA
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–40
13
Beispiel für Akzeptor
A
Start
0
A
B
1
2
A
3
B
NEA für Ausdruck „A(A+B)∗ BA“
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–41
Konstruktion von NEA I
A
Start
atomarer NEA für Symbol A
Saake/Schallehn
Algorithmen & Datenstrukturen II
Uni Magdeburg, WS 2005/06
13–42
195
13 Suche in Texten
Konstruktion von NEA II
Start
atomarer NEA für leeres Wort
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–43
Konstruktion von NEA III
N(r1)
Start
N(r2)
Kombination mittels Disjunktion +
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–44
Konstruktion von NEA IV
Start
N(r1)
N(r2)
Kombination mittels Sequenz +
Saake/Schallehn
196
Algorithmen & Datenstrukturen II
13–45
Uni Magdeburg, WS 2005/06
13 Suche in Texten
Konstruktion von NEA V
Start
N(r1)
Wiederholung / Hüllenbildung
Saake/Schallehn
Algorithmen & Datenstrukturen II
13–46
13
Beispiel
Start
0
1
A
B
3
2
◮
formale Kontruktion für Ausdruck „A*BA“
◮
kann natürlich vereinfacht werden....
Saake/Schallehn
4
Algorithmen & Datenstrukturen II
A
5
13–47
Kodierung der Automaten
◮
◮
nach Konstruktionsvorschrift kann es maximal zwei
ausgehende Kanten von einem Knoten geben
Kodierung als Tabelle möglich
state
symbol
next1
next2
Saake/Schallehn
0
ǫ
1
3
1
A
2
2
2
ǫ
3
1
3
B
4
4
4
A
5
5
Algorithmen & Datenstrukturen II
Uni Magdeburg, WS 2005/06
5
ǫ
0
0
13–48
197

Download Report