Kapitel 4 Algorithmen zur exakten Suche in Texten

Kapitel 4
Algorithmen zur exakten Suche
in Texten
In diesem Kapitel wird ein Problem aus der Sequenzanalyse näher
betrachtet, die exakte Textsuche: Gegeben ein Text und ein Muster,
finde alle Vorkommen von dem Muster in dem Text. Man wird sehen, dass zur Lösung dieses einfachen Problem einige nicht-triviale,
aber sehr effiziente Algorithmen entwickelt wurden. Zunächst soll jedoch ein kurzer Blick auf die Art und Weise geworfen werden, wie
Sequenzen üblicherweise in Java repräsentiert sind.
4.1
Die Klasse String
Zeichenketten sind in Java Objekte. Sie können mit dem +-Operator zu neuen
Objekten verknüpft werden.
String str1 = "hello";
String str2 = " world";
String str3 = str1 + str2;
Grundlegende objektbezogene Methoden der Klasse String:
public int length()
liefert die Anzahl der Zeichen in der Zeichenkette.
public int charAt(int index)
liefert das Zeichen an der Position index der Zeichenkette.
public int indexOf(int ch, int fromIndex)
liefert die erste Position ≥ fromIndex, an der das Zeichen ch in der Zeichenkette vorkommt, bzw. −1, falls das Zeichen nicht vorkommt.
43
public int lastIndexOf(int ch, int fromIndex)
liefert die letzte Position ≤ fromIndex, an der das Zeichen ch in der Zeichenkette vorkommt, bzw. −1, falls das Zeichen nicht vorkommt (lastIndexOf
liest also im Gegensatz zu indexOf die Zeichenkette von rechts nach links).
public boolean startsWith(String prefix)
liefert true gdw. die Zeichenkette mit dem angegebenen prefix beginnt.
public boolean endsWith(String suffix)
liefert true gdw. die Zeichenkette mit dem angegebenen suffix endet.
public String substring(int beginIndex, int endIndex)
liefert das Teilwort der Zeichenkette zwischen den Positionen beginIndex
und endIndex−1.
public char[] toCharArray()
wandelt die Zeichenkette in ein Feld von Zeichen um.
public boolean regionMatches (int start, String other, int ostart,
int len)
liefert true gdw. der Bereich der Zeichenkette mit dem Bereich der Zeichenkette String other übereinstimmt (s.u.). Der Vergleich beginnt bei der Position start bzw. ostart. Es werden nur die ersten len Zeichen verglichen.
public boolean equals(Object anObject)
liefert true gdw. die übergebene Objektreferenz auf ein Objekt vom Typ
String mit demselben Inhalt zeigt. (Dies steht im Gegensatz zu ==, was die
Objekt-(referenz-)gleichheit testet.)
Man beachte den Rückgabetyp int von charAt bzw. den Parametertyp int von
ch in indexOf und lastIndexOf. Dennoch können die Methoden auf (Unicode-)
Zeichen angewendet werden: Ein char-Wert in einem Ausdruck wird automatisch
in einen int-Wert umgewandelt, wobei die oberen 16 Bit auf Null gesetzt werden.
Beispiel 4.1.1
public class DemoStringClass {
public static void main(String[] args) {
String str = "bielefeld";
System.out.println(str.length());
System.out.println(str.charAt(0));
System.out.println(str.indexOf(’e’,3));
System.out.println(str.lastIndexOf(’e’,3));
System.out.println(str.startsWith("biele"));
System.out.println(str.endsWith("feld"));
44
System.out.println(str.substring(0,5));
System.out.println(str.substring(5,9));
System.out.println(str.regionMatches(0,"obiele",1,5));
if(str == args[0])
System.out.println("str == args[0]");
if(str.equals(args[0]))
System.out.println("str.equals(args[0])");
}
}
> java DemoStringClass bielefeld
9
b
4
2
true
true
biele
feld
true
str.equals(args[0])
4.2
Grundlegende Definitionen
Die Suche nach allen (exakten) Vorkommen eines Musters in einem Text ist ein
Problem, das häufig auftritt (z.B. in Editoren, Datenbanken etc.). Wir vereinbaren folgende Konventionen (wobei Σ ein Alphabet ist):
Muster P = P [0 . . . m − 1] ∈ Σm
Text T = T [0 . . . n − 1] ∈ Σn
P [j] = Zeichen an der Position j
P [b . . . e] = Teilwort von P zwischen den Positionen b und e
Beispiel 4.2.1 P = abcde, P [0] = a, P [3] = d, P [2 . . . 4] = cde.
Notation:
• leeres Wort: ε
• Länge eines Wortes x: |x|
• Konkatenation zweier Worte x und y: xy
45
Definition 4.2.2 Ein Wort w ist ein Präfix eines Wortes x (w ! x), falls x = wy
gilt für ein y ∈ Σ∗ . w ist ein Suffix von x (w " x), falls x = yw gilt für ein y ∈ Σ∗ .
x ist also auch ein Präfix bzw. Suffix von sich selbst.
Lemma 4.2.3 Es seien x, y und z Zeichenketten, so dass x " z und y " z gilt.
Wenn |x| ≤ |y| ist, dann gilt x " y. Wenn |x| ≥ |y| ist, dann gilt y " x. Wenn
|x| = |y| ist, dann gilt x = y.
Beweis: Übung (Aufgabe 4.7.1).
4.3
Das Problem der exakten Suche
Definition 4.3.1 Ein Muster P kommt mit der Verschiebung s im Text T vor,
falls 0 ≤ s ≤ n − m und T [s . . . s + m − 1] = P [0 . . . m − 1] gilt. In dem Fall
nennen wir s eine gültige Verschiebung.
Das Problem der exakten Textsuche ist nun, alle gültigen Verschiebungen zu
finden. Mit den Bezeichnungen S0 = ε und Sk = S[0 . . . k − 1] (d.h. Sk ist das
k-lange Präfix eines Wortes S ∈ Σ! für 0 ≤ k ≤ ") können wir das Problem der
exakten Textsuche folgendermaßen formulieren: Finde alle Verschiebungen s, so
dass P " Ts+m .
Beispiel 4.3.2
T = bielefeld oh bielefeld
P = feld
Gültige Verschiebungen: s = 5 und s = 18.
Die naive Lösung des Problems sieht in Pseudo-Code wie folgt aus:
Naive-StringMatcher(T, P )
1 n ← length[T ]
2 m ← length[P ]
3 for s ← 0 to n − m do
4
if P [0 . . . m − 1] = T [s . . . s + m − 1] then
5
print “Pattern occurs with shift” s
Am Beispiel T = abrakadabraxasa und P = abraxas erkennt man das ineffiziente Vorgehen, insbesondere wenn Text und Muster immer komplett verglichen
werden:
46
a b r a k a d a b r a x a s a
|
|
|
|
"
|
"
"
"
"
"
"
"
"
"
"
"
|
"
|
"
|
"
"
"
"
"
"
"
"
"
|
"
"
"
|
"
"
"
"
|
"
"
"
"
"
"
"
"
|
|
|
|
|
|
|
"
"
"
"
"
"
a b r a x a s
!
a b r a x a s
!
a b r a x a s
!
a b r a x a s
!
a b r a x a s
!
a b r a x a s
!
a b r a x a s
!
a b r a x a s
!
"
a b r a x a s
Eine Implementierung in Java verläuft analog:
public static void naiveMatcher(String text, String pattern) {
int m = pattern.length();
int n = text.length();
for(int s=0; s<=n-m; s++) {
if(text.regionMatches(s,pattern,0,m))
System.out.println("naiveMatcher: Pattern occurs with shift "+s);
}
}
Aber selbst wenn Text und Muster zeichenweise von links nach rechts und nur
1
bis zum ersten Mismatch
werden, ist die worst-case Zeiteffizienz des
! verglichen
"
naiven Algorithmus O n · m , z.B. wird für T = an , P = am die for-Schleife
n−m+1 mal ausgeführt und in jedem Test in Zeile 4 werden m Zeichen verglichen.
Wie kann man den naiven Algorithmus verbessern?
Idee 1: Überspringe ein Teilwort w von T , falls klar ist, dass w &= P (BMAlgorithmus 1977).
Idee 2: Merke Informationen über bisherige Vergleiche und nutze diese, um neue,
unnötige Vergleiche zu vermeiden (KMP-Algorithmus 1977).
1
Die zwei Zeichen stimmen nicht überein.
47
4.4
Der Boyer-Moore-Algorithmus
Der BM-Algorithmus legt wie der naive Algorithmus das Muster zunächst linksbündig an den Text, vergleicht die Zeichen des Musters dann aber von rechts
nach links mit den entsprechenden Zeichen des Textes. Beim ersten Mismatch
benutzt er zwei Heuristiken, um eine Verschiebung des Musters nach rechts zu
bestimmen.
4.4.1
Die bad-character Heuristik
Falls beim Vergleich von P [0 . . . m − 1] und T [s . . . s + m − 1] (von rechts nach
links) ein Mismatch
P [j] &= T [s + j] für ein j mit 0 ≤ j ≤ m − 1
festgestellt wird, so schlägt die bad-character Heuristik eine Verschiebung des
Musters um j − k Positionen vor, wobei k der größte Index (0 ≤ k ≤ m − 1) ist
mit T [s + j] = P [k]. Wenn kein k mit T [s + j] = P [k] existiert, so sei k = −1.
Man beachte, dass j − k negativ sein kann.
4.4.2
Die good-suffix Heuristik
Falls beim Vergleich von P [0 . . . m − 1] und T [s . . . s + m − 1] (von rechts nach
links) ein Mismatch
P [j] &= T [s + j] für ein j mit 0 ≤ j ≤ m − 1
festgestellt wird, so wird das Muster so weit nach rechts geschoben, bis das bekannte Suffix T [s + j + 1 . . . s + m − 1] wieder auf ein Teilwort des Musters passt.
Hierfür ist eine Vorverarbeitung des Musters notwendig, auf die wir hier aber
nicht näher eingehen wollen.
Im Boyer-Moore Algorithmus wird das Muster um das Maximum von beiden
vorgeschlagenen Verschiebungen verschoben. Es kann gezeigt werden, dass die
Laufzeitkomplexität dann im worst case O(n + m) ist.
Beispiel 4.4.1 Die Ausgangssituation ist in Abbildung 4.1(a) dargestellt. Die
bad-character Heuristik schlägt eine Verschiebung von j − k = (m − 3) − 5 =
(12 − 3) − 5 = 4 Positionen vor; dies ist im Fall (b) illustriert. Aus der Darstellung (c) wird ersichtlich, dass die good-suffix Heuristik eine Verschiebung von 3
Positionen vorschlägt. Also wird das Muster um max{4, 3} = 4 Positionen nach
rechts verschoben.
48
bad character
good suffix
"
"#$%&
... w r i t t e n _ n o t i c e _ t h a t ...
'
s! r e m i n i s c e n c e
(a)
... w r i t t e n _ n o t i c e _ t h a t ...
s+4
!
reminiscence
(b)
... w r i t t e n _ n o t i c e _ t h a t ...
s+3 ! r e m i n i s c e n c e
(c)
Abbildung 4.1: Verhalten des Boyer-Moore Algorithmus
4.5
Der Boyer-Moore-Horspool-Algorithmus
Der BM-Algorithmus verdankt seine Schnelligkeit vor allem der bad-charakter
Heuristik. Daher wurde 1980 von Horspool eine Vereinfachung des BM-Algorithmus
vorgeschlagen: Die bad-charakter Heuristik wird derart modifiziert, dass sie immer eine positive Verschiebung vorschlägt. Damit wird die good-suffix Heuristik
überflüssig (und auch die Vorverarbeitung einfacher).
Der BMH-Algorithmus geht in den meisten Fällen analog zur bisherigen badcharacter Heuristik vor.
Aber: Falls P [j] &= T [s + j] für ein j (0 ≤ j ≤ m − 1) gilt, so wird s um m − 1 − k
erhöht, wobei k der größte Index zwischen 0 und m−2 ist mit T [s+m−1] = P [k].
Wenn kein k (0 ≤ k ≤ m − 2) mit T [s + m − 1] = P [k] existiert, so wird s um m
erhöht. Das Muster wird also um
)
'
(
*
+,
λ T [s+m−1] = min {m}∪ m−1−k | 0 ≤ k ≤ m−2 und T [s+m−1] = P [k]
'
verschoben.
Wenn ein Match gefunden wurde, dann wird ebenfalls um λ T [s +
(
m − 1] verschoben.
Die Funktion λ lässt sich wie folgt berechnen:
computeLastOccurrenceFunction(P, Σ)
1 m ← length[P ]
2 for each character a ∈ Σ do
3
λ[a] = m
4 for j ← 0 to m − 2 do
49
... g o l d e n _ f l e e c e _ o f ...
'
s! r e m i n i s c e n c e
⇓
... g o l d e n _ f l e e c e _ o f ...
s+3 ! r e m i n i s c e n c e
Abbildung 4.2: Verhalten des BMH-Algorithmus bei einem Mismatch
... g o l d e n _ f l e e c e _ o f ...
s
!
fleece
⇓
... g o l d e n _ f l e e c e _ o f ...
s+2
!
fleece
Abbildung 4.3: Verhalten des BMH-Algorithmus bei einem Treffer
'
(
5
λ P [j] ← m − 1 − j
6 return λ
!
Die
worst-case-Komplexität
von
computeLastOccurrenceFunction
ist
O
|Σ| +
"
m .
Der BMH-Algorithmus sieht in Pseudo-Code folgendermaßen aus:
BMH-Matcher(T, P, Σ)
1 n ← length[T ]
2 m ← length[P ]
3 λ ← computeLastOccurrenceFunction(P, Σ)
4 s←0
5 while s ≤ n − m do
6
j ← m−1
7
while j ≥ 0 and P [j] = T [s + j] do
8
j ← j−1
9
if j = −1 then
10
print “Pattern
occurs (with shift” s
'
11
s ← s + λ T [s + m − 1]
Zur Verifikation, ob eine Verschiebung s gültig ist, wird O(m) Zeit benötigt.
50
!
Insgesamt
hat
der
BMH-Algorithmus
die
worst-case
Zeitkomplexität
O
n·m+
"
|Σ| (z.B. für T = an , P = am ).
4.6
4.6.1
Der Knuth-Morris-Pratt-Algorithmus
Einführendes Beispiel
Der naive Algorithmus ist ineffizient, da unabhängig von bereits stattgefundenen
erfolgreichen Vergleichen das Muster immer um ein Zeichen verschoben wird. Im
folgenden Beispiel ist dies noch einmal anhand der Suche nach dem Wort abraxas
im Text abrakadabra dargestellt.
a b r a
| | | |
a b r a
'
! a b r
'
! a b
|
! a
k a d a b r a
'
x a s
a x a s
r a x a s
'
b r a x a s
Man erkennt, dass im zweiten und dritten Schritt das Zeichen a an Position
1 im Muster mit den Zeichen b und r an der zweiten und dritten Position des
Textes verglichen wird, obwohl bereits nach dem positiven Vergleich von abra klar
sein musste, dass hier keine Übereinstimmung existieren kann. Verwendet man
dagegen Information aus vorangegangenen Vergleichen, so muss man nach einer
Verschiebung mit den zeichenweisen Vergleichen zwischen Muster und Text nicht
wieder am Anfang des Musters anfangen. Der Knuth-Morris-Pratt-Algorithmus
geht nach folgendem Schema vor: Wenn ein Teilwort (Präfix) des Musters bereits
erkannt wurde, aber dann ein mismatch auftritt, so ermittelt der Algorithmus
das längste Präfix dieses Teilwortes, das gleichzeitig echtes Suffix davon ist, und
schiebt das Muster dann so weit nach rechts, dass dieses Präfix an der bisherigen
Position des Suffixes liegt.
Beispiel 4.6.1 Im obigen Beispiel ist das bereits erkannte Teilwort abra. Das
längste Präfix von abra, das gleichzeitig echtes Suffix davon ist, ist a. Also schiebt
der Algorithmus das Muster so, dass das erste a von abraxas an der Position
steht, an der sich vorher das zweite a befunden hat. Der nächste stattfindende
Vergleich ist der von k mit b, da die Verschiebung ja gerade so durchgeführt
wurde, dass die beiden as übereinander liegen und somit nicht mehr verglichen
werden müssen.
51
a b r a k a d a b r a
| | | | '
a b r a x a s
'
! a b r a x a s
Man erkennt, dass hier drei unnötige Vergleiche vermieden wurden.
4.6.2
Funktionsweise
Beim KMP-Algorithmus wird das Muster P zeichenweise von links nach rechts
mit dem Text T verglichen. Es werden Informationen über bereits stattgefundene Vergleiche ausgenutzt, um weitere unnötige Vergleiche zu vermeiden. Als
Ausgangssituation sei Pq ein Präfix von P , das an Position s im Text vorkommt.
...
Pq
s!
Pq
...
Dann gehen wir gemäß der folgenden Fälle vor:
(A) q = m, d.h. s ist gültige Verschiebung:
1.
Bestimme k ∗ = π[m] = max{k : k < m und Pk " Pm }.
2.a) Falls k ∗ > 0, verschiebe das Muster nach rechts, so dass das Präfix Pk∗
von P unter dem Suffix Pk∗ von T [s . . . s + |P | − 1] liegt.
...
Pk ∗
...
Pk ∗
...
Pk ∗
...
⇓
Pk ∗
2.b) Falls k ∗ = 0, verschiebe das Muster P um die Länge |P |.
...
...
52
(B) q < m:
...
%
%
Pk
&#
Pq
Pk
&#
Pq
(a) a &= b und q &= 0:
$
$
a
...
b
• bestimme π[q] = max{k : k < q und Pk " Pq }, d.h. die Länge des
längsten Präfixes von P , das auch Suffix von Pq ist;
• verschiebe P nach rechts, so dass das Suffix Pk von Pq über dem
Präfix Pk von P liegt.
a
Pk
...
...
Pk
b
(b) a &= b und q = 0:
• verschiebe P um 1 nach rechts.
... a
...
b
(c) a = b:
• mache weiter mit q + 1.
...
Pq
a
Pq
a
...
Pq+1
s!
Pq+1
...
⇓
...
Beobachtung: Für jeden der vier Fälle gilt:
• das Muster wird nie nach links geschoben
• entweder wird ein neues Zeichen des Textes gelesen (B.c), oder das
Muster wird um mindestens eine Position nach rechts geschoben (A),
(B.a), (B.b).
53
Insgesamt können die Fälle also höchstens 2n-mal vorkommen.
Wir bestimmen die worst-case Zeitkomplexität des KMP-Algorithmus:
• Fälle (B.b) und (B.c) erfordern jeweils konstanten Zeitaufwand.
• In (A) und (B.a) wird die Funktion π benötigt mit π[q] = max{k : k < q
und Pk " Pq }, d.h. π[q] = Länge des längsten Präfixes von P , das ein
echtes Suffix von Pq ist. π hängt nur von P ab und kann daher in einem
Vorverarbeitungsschritt (V V ) berechnet und als Tabelle abgespeichert werden. Gegeben diese Tabelle, erfordern auch (A) und (B.a) nur konstanten
Zeitaufwand.
Damit ergeben sich folgende Komplexitäten: O(V V ) + O(n) Zeit und O(m) Speicherplatz im worst-case!
Beispiel 4.6.2 Die Präfixfunktion π : {1, 2, . . . , m} → {0, 1, . . . , m − 1} für ein
Muster P [0 . . . m − 1] ist definiert durch π[q] = max{k : k < q und Pk " Pq },
also die Länge des längsten Präfixes von P , das ein echtes Suffix von Pq ist. Sie
lautet für unser Beispielwort P = abrakadabra:
0 1 2 3 4 5 6 7 8 9 10 11
q
P [q] a b r a k a d a b r a ⊥
π[q] ⊥ 0 0 0 1 0 1 0 1 2 3 4
Für q = 9 wäre das entsprechende Teilmuster also abrakadab. Das längste Präfix,
das gleichzeitig echtes Suffix davon ist, ist ab. Es hat die Länge 2, darum findet
sich in der Tabelle an der Position q = 9 der Eintrag π[q] = 2.
Die Präfixfunktion π kann naiv folgendermaßen berechnet werden (die Laufzeit
beträgt O(m3 ), aber wir werden später sehen, wie es auch effizienter geht):
computePrefixFunction(P )
1 m ← length[P ]
2 π[1] ← 0
3 for q ← 2 to m do
4
k ← q−1
5
while k > 0 and P [0 . . . k − 1] &" P [0 . . . q − 1] do
6
k ← k−1
7
π[q] ← k
8 return π
Damit können wir den KMP-Algorithmus in Pseudo-Code formulieren:
KMP-Matcher(T, P )
1 n ← length[T ]
2 m ← length[P ]
54
3 π ← computePrefixFunction(P )
4 q←0
5 for i ← 0 to n − 1 do
6
while q > 0 and P [q] &= T [i] do
7
q ← π[q]
8
if P [q] = T [i] then
9
q ← q+1
10
if q = m then
11
print “Pattern occurs with shift” i − m + 1
12
q ← π[q]
Wir gehen nun der Frage nach, wie die Funktion π effizienter berechnet werden
kann. Unter der Annahme, dass die Werte von π für 1, . . . , q − 1 schon berechnet
sind, wollen wir π[q] berechnen. Gesucht:
π[q] = max{k : k < q und Pk " Pq }
Welche Pk kommen in Frage? Alle Pk = P [0 . . . k − 1] für die gilt:
Pk−1 " Pq−1
%&#$
%&#$
P [0...k−2]
und P [k − 1] = P [q − 1],
P [0...q−2]
also alle echten Suffixe von Pq−1 , die sich zu einem echten Suffix von Pq erweitern
lassen. Die Menge der Längen aller echten Suffixe von Pq−1 , die auch Präfixe von
P sind, ist:
{k − 1 : k − 1 < q − 1 : Pk−1 " Pq−1 } = {k $ : k $ < q − 1 : Pk" " Pq−1 }.
Damit muss gelten:
π[q] = max{k $ + 1 : k $ < q − 1, Pk" " Pq−1 und P [k $ ] = P [q − 1]}.
Nun kann man folgende Gleichheit zeigen (Lemma 4.6.4):
'
(
{k $ : k $ < q − 1 : Pk" " Pq−1 } = {π[q − 1], π π[q − 1] , π 3 [q − 1], . . . , π t [q − 1]},
% &# $
=π 2 [q−1]
wobei π t [q − 1] = 0 gilt. Schließlich erhalten wir:
π[q] = max{k $ + 1 : k ∈ {π[q − 1], . . . , π t [q − 1]} und P [k $ ] = P [q − 1]}.
Damit erhalten wir folgendes Verfahren, um π[q] zu berechnen: Wir schauen
π[q − 1] in der Tabelle von π nach und prüfen, ob sich das echte Suffix Pπ[q−1]
von Pq−1 zu einem echten Suffix von Pq erweitern lässt. Wenn ja, so ist π[q] =
55
π[q − 1] + 1. Wenn nein, so iterieren wir diesen Prozess, d.h. wir machen das Gleiche mit π(π[q − 1]) usw. Diese Überlegungen sollten die folgende Berechnungsmethode der Funktion π motivieren. Wir werden deren Korrektheit im nächsten
Unterabschnitt beweisen.
computePrefixFunction2(P )
1 m ← length[P ]
2 π[1] ← 0
3 k←0
4 for q ← 2 to m do
5
while k > 0 and P [k] &= P [q − 1] do
6
k ← π[k]
7
if P [k] = P [q − 1] then
8
k ← k+1
9
π[q] ← k
10 return π
Die Laufzeit von computePrefixFunction2 beträgt O(m). Dies kann man folgendermaßen sehen:
1. Die for-Schleife in Zeile 4 wird m − 1-mal durchlaufen, demzufolge auch
die Zeilen 7-9.
2. Der Wert von k ist anfangs 0 und wird insgesamt höchstens m − 1-mal in
Zeile 8 um jeweils 1 erhöht.
3. Bei jedem Durchlauf der while-Schleife in den Zeilen 5 und 6 wird der Wert
von k um mindestens 1 erniedrigt. Da k nicht negativ wird (Zeile 5), kann
die while-Schleife insgesamt also höchstens k-mal durchlaufen werden.
4.6.3
Korrektheit der Berechnung der Präfixfunktion
Das wesentliche Lemma im Korrektheitsbeweis besagt, dass man alle Präfixe
Pk , die Suffix eines gegebenen Präfixes Pq sind, berechnen kann, indem man die
Präfixfunktion π iteriert.
Definition 4.6.3 Es sei
*
+
π ∗ [q] = q, π[q], π 2 [q], π 3 [q], . . . , π t [q]
'
(
wobei π 0 [q] = q und π i+1 [q] = π π i [q] für i ≥ 0; dabei sei vereinbart, dass die
Folge in π ∗ [q] abbricht, wenn π t [q] = 0 erreicht wird.
Lemma 4.6.4 Es sei P [0 . . . m − 1] ein Muster und π die dazu gehörige Präfixfunktion.
Dann gilt π ∗ [q] = {k : Pk " Pq } für q = 1, . . . , m.
56
Beweis: Wir beweisen das Lemma, indem wir (1) π ∗ [q] ⊆ {k : Pk " Pq } und (2)
{k : Pk " Pq } ⊆ π ∗ [q] zeigen.
1. Wir zeigen: i ∈ π ∗ [q] impliziert Pi " Pq . Sei also i ∈ π ∗ [q]. Für i gibt es ein
u ∈ N mit i = π u [q]. Wir beweisen Pπu [q] " Pq durch Induktion über u.
Induktionsanfang: u = 0. Dann ist i = π 0 [q] = q und die Behauptung gilt.
Induktionshypothese: Für i0 = π u0 [q] gilt Pi0 " Pq .
Induktionsschritt:
Zu zeigen ist: für i = π u0 +1 [q] gilt Pi " Pq . Es gilt i =
' u (
π π 0 [q] = π[i0 ]. Mit der Induktionshypothese folgt Pi0 " Pq . Weiterhin
gilt
i = π[i0 ] = max{k : k < i0 und Pk " Pi0 },
also gilt Pi " Pi0 " Pq . Da " transitiv ist, folgt Pi " Pq .
2. Wir beweisen {k : Pk " Pq } ⊆ π ∗ [q] durch Widerspruch. Wir nehmen an
∃j ∈ {k : Pk " Pq }\π ∗ [q].
Ohne Einschränkung der Allgemeinheit sei j die größte Zahl mit dieser
Eigenschaft. Da
j ≤ q und q ∈ {k : Pk " Pq } ∩ π ∗ [q]
gilt, folgt j < q. Es sei j $ die kleinste Zahl in π ∗ [q], die größer als j ist (da
q ∈ π ∗ [q] gilt, existiert solch ein j $ immer). Wegen j ∈ {k : Pk " Pq } gilt
Pj " Pq . Weiterhin impliziert j $ ∈ π ∗ [q] wg. (1) Pj " " Pq . Mit j < j $ folgt
damit Pj " Pj " . Es gibt kein
j $$ , j < j $$ < j $ , mit Pj " Pj "" " Pj "
Gäbe es solch ein j $$ , so müsste j $$ ∈ π ∗ [q] gelten, denn j ist die größte Zahl
mit
j ∈ {k : Pk " Pq }\π ∗ [q].
j $$ ∈ π ∗ [q] kann aber nicht gelten, denn j $ ist die kleinste Zahl in π ∗ [q], die
größer als j ist. Also muss j = max{k : k < j $ und Pk " Pj " } = π[j $ ] und
damit j ∈ π ∗ [q] gelten. Dieser Widerspruch beweist {k : Pk " Pq } ⊆ π ∗ [q].
#
Definition 4.6.5 Für q = 2, 3, . . . , m sei
*
+
Eq−1 = k : k < q − 1, k ∈ π ∗ [q − 1], P [k] = P [q − 1] .
Die Menge Eq−1 ⊆ π ∗ [q − 1] enthält alle
k ∈ π ∗ [q − 1] = {k : Pk " Pq−1 }
mit k < q − 1 und Pk+1 " Pq ; denn aus
Pk = P [0 . . . k − 1] " Pq−1 = P [0 . . . q − 2] und P [k] = P [q − 1]
folgt Pk+1 = P [0 . . . k] " Pq = P [0 . . . q − 1]).
57
Lemma 4.6.6 Sei P [0 . . . m−1] ein Muster und π die zugehörige Präfixfunktion.
Für q = 2, 3, . . . , m gilt:
0
falls Eq−1 = ∅
π[q] =
1 + max{k ∈ Eq−1 } falls Eq−1 &= ∅
Beweis: Mit der Vereinbarung max{} = 0 gilt:
*
+
π[q]
=
max *k : k < q und Pk " Pq
+
=
max k : k < q, Pk−1 " Pq−1 und P [k − 1] = P [q − 1]
*
+
(4.6.4)
=
max k : k − 1 < q − 1, k − 1 ∈ π ∗ [q − 1] und P [k − 1] = P [q − 1]
*
+
k" =k−1
$
∗
$
=
max *k $ + 1 : k $ < q − 1,
k
∈
π
[q
−
1]
und
P
[k
]
=
P
[q
−
1]
+
=
max k $ + 1 : k $ ∈ Eq−1
Fall 1: Eq−1 = ∅: Dann gilt π[q] = max{} = 0.
Fall 2: Eq−1 &= ∅: Dann gilt π[q] = max{1 + k $ : k $ ∈ Eq−1 } = 1 + max{k $ : k $ ∈
Eq−1 }.
#
Satz 4.6.7 computePrefixFunction2(P) berechnet die Funktion π korrekt.
Beweis: Am Anfang jeder Iteration der for-Schleife gilt k = π[q − 1], denn beim
ersten Betreten der for-Schleife gilt k = 0, q = 2 und π[q − 1] = 0 = k und diese
Eigenschaft bleibt wegen Zeile 9 bei jeder Iteration der for-Schleife erhalten. Die
Eigenschaft k = π[q − 1] wird daher auch Invariante der Schleife genannt. Die
while-Schleife untersucht alle Werte
k ∈ π ∗ [q − 1]\{q − 1},
bis einer mit P [k] = P [q − 1] gefunden wird; an diesem Punkt gilt
k = max{k ∈ Eq−1 },
so dass π[q] den Wert k + 1 = 1 + max{k ∈ Eq−1 } erhält. Wird kein solcher Wert
k gefunden, so wird π[q] der Wert 0 zugewiesen, denn es gilt k = 0 in den Zeilen
7-9.
Das in Zeile 10 zurückgegebene Feld π hat also folgende Werte:
π[1] = 0 und für q = 2, 3, . . . , m
.
0
π[q] =
1 + max{k ∈ Eq−1 }
falls Eq−1 = ∅
falls Eq−1 &= ∅
#
58
4.7
Aufgaben
Aufgabe 4.7.1 Beweisen Sie Lemma 4.2.3.
Aufgabe 4.7.2 Implementieren Sie den Boyer-Moore-Horspool-Algorithmus in
Java.
Aufgabe 4.7.3 Bestimmen Sie die worst-case Zeiteffizienz der naiven Implementierung von computePrefixFunction.
Aufgabe 4.7.4 Implementieren Sie den Knuth-Morris-Pratt-Algorithmus in Java.
Aufgabe 4.7.5 Geben Sie konkrete Beispiele an, in denen
(a) der Knuth-Morris-Pratt-Algorithmus
(b) der Boyer-Moore-Horspool-Algorithmus
(c) der Boyer-Moore-Algorithmus
sich besser verhält als die beiden anderen (unter Vernachlässigung der Vorverarbeitung). Das Kriterium ist hierbei die Anzahl der Vergleiche von Zeichen, die
jeweils durchgeführt werden müssen.
Aufgabe 4.7.6 Man erreicht eine verbesserte Version des Knuth-Morris-PrattMatchers, indem man π in der Zeile 7 (nicht aber in Zeile 12) durch π $ ersetzt.
π $ ist rekursiv für q = 1, 2, . . . , m − 1 definiert:

wenn π[q] = 0,
 0
π $ [π[q]]
wenn π[q] &= 0 und P [π[q]] = P [q],
π $ [q] =

π[q]
wenn π[q] &= 0 und P [π[q]] &= P [q].
Erklären Sie, warum der modifizierte Algorithmus korrekt ist und inwiefern diese Modifikation eine Verbesserung darstellt. Stellen Sie die Funktion π $ für das
Muster P = ababababca tabellarisch dar.
Aufgabe 4.7.7 Geben Sie einen Algorithmus an, der herausfindet, ob ein Text
T eine zyklische Verschiebung eines Textes T $ ist. Zum Beispiel ist der Text reif
eine zyklische Verschiebung von frei. Der Algorithmus soll linear im Zeitaufwand
sein. Implementieren Sie Ihren Algorithmus in Java.
Aufgabe 4.7.8 Erklären Sie, wie man alle Vorkommen des Musters P im Text
T unter Zuhilfenahme der π Funktion für die Zeichenkette P T bestimmen kann.
P T ist die Konkatenation von P und T (also m+n Zeichen lang). Implementieren
Sie Ihren Vorschlag in Java.
59
60

Download Report