String - inf.fu-berlin.de · String Matc hing Algorithmen Skript v on Stephan Hell zur V orlesung F...

String Matching Algorithmen

Skript von Stephan Hell zur Vorlesung von Frank Ho�mann

Sommersemester 2000

2

Inhaltsverzeichnis

1 Exaktes Pattern Matching : Klassische Methoden 4

1.1 Z{Algorithmus (nach Gus�eld) . . . . . . . . . . . . . . . . . 4

1.2 Boyer{Moore Algorithmus (`77) . . . . . . . . . . . . . . . . . 7

1.3 Knuth{Morris{Pratt Algorithmus ('77) . . . . . . . . . . . . . 8

2 Exaktes Matching mit mehreren Mustern 9

2.1 Aho{Corasick Algorithmus . . . . . . . . . . . . . . . . . . . . 10

2.1.1 Bestimmung der Fehler{Links in O(n) . . . . . . . . . 11

2.1.2 Anwendung 1: Matching mit Wildcards . . . . . . . . . 14

2.1.3 Anwendung 2: Zweidimensionales Matching . . . . . . 15

3 Matching mit regul�aren Ausdr�ucken 15

3.1 Wiederholung: Regul�are Ausdr�ucke . . . . . . . . . . . . . . . 15

3.2 Der Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Seminumerisches Stringmatching 18

4.1 Shift{AND{Methode (nach Baeza{Yates, Gonnet '92) . . . . . 18

4.1.1 Exaktes Matching . . . . . . . . . . . . . . . . . . . . . 18

4.1.2 Matching mit Fehlern (Wu, Manber '92) . . . . . . . . 19

4.2 Fingerprint{Methode nach Karp{Rabin '87 . . . . . . . . . . . 20

4.2.1 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 20

4.2.2 Einiges �uber Primzahlen . . . . . . . . . . . . . . . . . 21

4.2.3 Die Wahrscheinlichkeit f�ur ein falsches Match . . . . . 22

5 SuÆx{B�aume und ihre Anwendungen 23

5.1 Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.1.1 Exaktes Matching . . . . . . . . . . . . . . . . . . . . . 24

5.1.2 Eine Datenbank f�ur Muster . . . . . . . . . . . . . . . 24

5.1.3 Longest{Common{Substring von S1 und S2 . . . . . . 25

5.1.4 All{Pairs{SuÆx{Pr�a�x{Matching . . . . . . . . . . . . 25

5.2 Konstruktion von SuÆxb�aumen in Linearzeit . . . . . . . . . . 26

5.2.1 Erster Trick: SuÆx{Links . . . . . . . . . . . . . . . . 28

5.2.2 Zweite Verbesserung: Skip & Count . . . . . . . . . . . 30

5.3 SuÆx{Arrays und Anwendungen . . . . . . . . . . . . . . . . 33

3

6 SuÆxb�aume und lca{Anfragen 34

6.1 lca{Anfragen in konstanter Zeit . . . . . . . . . . . . . . . . . 35

6.1.1 lca{Anfragen in vollst�andigen bin�aren B�aumen . . . . . 35

6.1.2 lca{Anfragen in allgemeinen B�aumen { Vorverarbeitung 36

6.1.3 Beantwortung der lca{Anfragen in konstanter Zeit . . . 38

6.2 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

7 Approximatives Matching 42

7.1 Editierabstand, globales & lokales Alignment . . . . . . . . . 42

7.2 �Ahnlichkeit von Strings . . . . . . . . . . . . . . . . . . . . . 44

7.3 Das local{Alignment{Problem . . . . . . . . . . . . . . . . . 45

7.4 Gaps und Gap Weights . . . . . . . . . . . . . . . . . . . . . . 46

7.5 Verbesserung der dynamischen Programmierung . . . . . . . 47

7.5.1 Linearer Speicherbedarf . . . . . . . . . . . . . . . . . 47

7.5.2 k{di�erence Alignment/Matching . . . . . . . . . . . . 49

7.6 SuÆxb�aume und gewichtete Alignments . . . . . . . . . . . . 52

7.6.1 P{against{all . . . . . . . . . . . . . . . . . . . . . . . 52

7.6.2 All-against{all . . . . . . . . . . . . . . . . . . . . . . . 53

7.7 Ausschlu�verfahren . . . . . . . . . . . . . . . . . . . . . . . . 54

7.7.1 Verbesserung: Mehrfach�lter f�ur k{Mismatches . . . . 56

7.8 Ein kombinatorischer Algorithmus f�ur lcs . . . . . . . . . . . 56

4

1 Exaktes Pattern Matching : Klassische Me-

thoden

De�nition 1 Sei � ein Alphabet aus Zeichen, S 2 �� nennen wir Wortoder String. S(i) bezeichnet den i.ten Buchstaben von S, S[i; j] das TeilwortS(i) : : : S(j).

Aufgabe:

� Gegeben: Text T 2 ��; jT j = m, Pattern P 2 ��; jP j = n � m.

� Gesucht: alle Vorkommen von P als Teilwort in T .

Naive Methode:

PT

Abbildung 1: Naive Methode

Das Muster P (=Pattern) wird von links nach rechts �uber den Text T gescho-ben, und jede Stelle von T wird als m�oglicher Anfang des Musters getestet.Dabei werden n � (m� n+ 1) Vergleiche gemacht, der Algorithmus ben�otigtalso O(n �m) Zeit (1 Vergleich = 1 Zeiteinheit).

Eine o�ensichtliche untere Schranke f�ur das Problem ist (n+m), denn derText und das Pattern m�ussen gelesen werden. Das Ziel ist es nun, einfache Li-nearzeitalgorithmen zu entwickeln (deren erwartete Laufzeit sogar sublinearist).

Idee: Beim Testen von P lernen wir T lokal, dadurch sind gr�o�ere Spr�ungem�oglich ! Vorverarbeitung von Text (SuÆxtrees) und/oder Pattern.

1.1 Z{Algorithmus (nach Gus�eld)

De�nition 2 Sei S ein String, i > 1 eine Position. Wir de�nieren:

Zi = Zi(S) = L�ange des l�angsten Pr�a�x von S, der auch Pr�a�x von S[i; jSj]ist.

5

Beispiel. S = aabcaabxaaz; Z5(S) = 3.

De�nition 3 Es sei S[i; i+Zi � 1] Z{Box f�ur die Position i, wobei Zi > 0.

F�ur i � 1 sei ri das gr�o�te rechte Ende einer Z{Box, die vor oder bei ibeginnt, und li das zu diesem ri geh�orige linke Ende.

Sriili

Z-Box

Position

Abbildung 2: Z { Box

Satz 1 Die Z{Boxen k�onnen in O(jSj) berechnet werden.

Korollar 1 Pattern matching geht in linearer Zeit.

Beweisskizze zum Korollar: Findet man in diesem S eine Z{Box mit L�angejP j, so hat man das Pattern gefunden und ein Matching liegt vor.

P

S = $

T

Z-Box mit L�ange jP jTrennsymbol

Abbildung 3: Beweisskizze

Beweis. (vom Satz)

� Z2 wird explizit berechnet.

� Die erste Z{Box wird berechnet:

r = r2 =

�Z2 + 1 : Z2 > 0

0 : sonst

l = l2 =

�2 : Z2 > 00 : sonst

6

� Angenommen Zi sei f�ur 1 < i < k bekannt, setze r = rk�1 und l =lk�1. Wir berechnen nun Zk; lk; rk.

1. Fall: k > r

Dann setze rk := k + Zk � 1 und lk = k; falls Zk > 0.

r k neues r

Abbildung 4: 1.Fall: k > r

2. Fall: k � r

Die Position k liegt somit in einer schon berechneten Z{Box �,welche wie der Anfang aussieht. Nennen wir den Teilstring T [k; r]�. Nun gibt es am Anfang die Position k0 = k � l + 1, die genauwie die Position k aussieht und von der wir die Z{Box - nachAnnahme - schon berechnet haben.

k0 l k r

��

�

Abbildung 5: 2.Fall: k � r

(a) Zk0 = j j < j�j; dann setzeZk = Zk0, r und l wie vorher.

(b) Zk0 = j j � j�j, dann vergleiche S(r + 1) mit S(j�j + 1) : : :,bis ein Mismatch bei Position q � r + 1 auftritt. Dann setzeZk = q � k, r = q � 1 und l = k. 2

Analyse:

� Zeit = #Iterationen + #Vergleiche, wobei gilt:

Man hat jSj = #Iterationen und die Anzahl der Vergleiche h�angt vonden Matches und Mismatches ab. Dabei hat man #Mismatches �jSj; rk � rk�1 und #Matches � jSj.

� O(jSj) zus�atzlicher Speicher wird ben�otigt.

� Die Laufzeitbetrachtung ist alphabetunabh�angig.

7

1.2 Boyer{Moore Algorithmus (`77)

Idee:

1. Das Pattern P wird von links nach rechts �uber den Text T geschoben,aber von rechts nach links verglichen. Ziel: Spr�unge beim Vergleichen.

PT

bis ein Mismatch auftritt

Abbildung 6: Idee

2. (a) Bad{Character{Regel

Tx yx

PPosition i

Position k

Abbildung 7: 2. Fall: k � r

De�nition 4

R(x) =

�rechteste Position von x in P0, wenn kein x in P

Wenn es nun zu einem Mismatch T (k) 6= P (i) kommt, besagt dieRegel: Verschiebe P um maxf1; i�R(T (k))g Positionen.Beispiel.

Sei i = 3; k = 5.

T : xpbctbxabpqxctb

P : tpaxab

Somit ist T (k) = t und R(T (k)) = 1, und daraus erh�alt man nachder Regel einen shift um 3� 1 = 2 Positionen.

(b) Strong{good{SuÆx{Regel

Nach einem Mismatch verschieben wir das Pattern P bis zur rech-testen Kopie t0 von t, die in P links von t steht und bei der derBuchstabe links von t0 ein anderer ist als links von t. Wenn so

8

PT

tt0

Abbildung 8: Strong{good{SuÆx{Regel

eine Kopie t0 nicht existiert, verschieben wir das linke Ende von Psoweit in t, bis ein Pr�a�x von P einen SuÆx von t matcht. Fallsdieser Pr�a�x nicht existiert, verschieben wir um n Positionen.

Analog verfahren wir nach einem Matching.

Beispiel.

sp r t a b s t u b a b v : : :

q c a b d a b d a b

: : :dbacq

Text T

Pattern P

Abbildung 9: Beispiel

t = ab startet bei P (3) und Mismatch bei Position 10, damit shiftum 6 Positionen.

Der Boyer{Moore Algorithmus verschiebt um das Maximum der beiden shift{Werte, die von der Bad{Character{Regel und der Strong{good{SuÆx{Regelgeliefert werden. Zum AuÆnden der richtigen Kopien t0 an jeder Position desPatterns ist eine Vorverarbeitung des umgedrehten Patterns P rev mit demZ{Algorithmus notwendig.

Laufzeitanalyse (mit Modi�kation): Im worst{case O(n +m), die beste be-kannte Schranke ist � 2m Vergleiche (!Apostolico, Giancarlo '86).

1.3 Knuth{Morris{Pratt Algorithmus ('77)

Idee:

� Verschieben des Patterns P von links nach rechts.

� Vergleichen von links nach rechts.

� Wie weit kann man das Pattern nach einem Mismatch verschieben?

9

Position k

Position i+ 1

TP

Abbildung 10: Idee

De�nition 5 sp0i = L�ange des l�angsten SuÆx von P [1; i], der Pr�a�x von Pmatcht und P (i+ 1) 6= P (sp0i + 1).

Wir verschieben um (i � sp0i) Stellen, und testen als n�achstes T (k) gegenP (sp0i). Falls kein Mismatch auftritt, verschieben wir um n � sp0n Stellen.Dabei wird tats�achlich kein Auftreten des Patterns in T �ubersehen, Beweisin der �Ubung.

Beispiel.

r a b v : : :

d

a

Text Tp a c x a b c x

a b c x a b c e

c x

b

: : :ba

shift um i� sp0i = 7� sp07 = 7� 3 = 4 Positionen

Pattern P

Abbildung 11: Beispiel

Um die sp0i zu bestimmen, ist eine Vorverarbeitung des Patterns P mit demZ{Algorithmus notwendig.

2 Exaktes Matching mit mehreren Mustern

Sei T ein Text, jT j = m und eine Menge von Pattern

P = fP1; P2; :::; Pzg, mit jPj =zP

i=1

jPij = n,

gegeben.

Dann l�a�t sich auf triviale Art und Weise durch z{fache Anwendung derkennengelernten Algorithmen eine Laufzeit von O(n+ z �m) erreichen.

10

Das Ziel ist ein Algorithmus mit Laufzeit O(n + m + k), wobei k der An-zahl der Vorkommen der Pattern P1; P2; : : : ; Pz entspricht. Beachte: dieAnzahl k der Pattern kann echt gr�o�er sein als die Summe der Text- undPatternl�ange.Dazu ein

Beispiel. Sei T = aa : : : a und

P = faa : : : a| {z }m

2

, aa : : : a| {z }m

4

, : : :g

Dann hat man: jPj = O(m) und

#Vorkommen:m

2+3m

4+ : : :| {z }

log2m Summanden

! O(m logm).

2.1 Aho{Corasick Algorithmus

Annahme: Die Menge P der Muster sei teilstringfrei (d.h. kein Pi ist Teil-string eines anderen Pj).

Idee: Wir f�uhren als neue Datenstruktur einen Keyword{Baum K ein, derfolgende Eigenschaften hat:

� K ist ein gerichteter Baum mit Wurzel r.

� Die Kanten des Baumes tragen Zeichen aus dem Alphabet.

� Kanten, die von einem Knoten ausgehen, tragen verschiedene Zeichen.

� Ein Weg von der Wurzel zu einem Blatt entspricht einem Muster Pi.

Analog zum KMP Algorithmus wird der Baum gegen den Text getestet. Da-bei ist wieder die Frage, wie weit die Wurzel nach einemMismatch verschobenwerden kann. Um das entscheiden zu k�onnen, ist eine Vorverarbeitung desKeyword{Baumes notwendig. Dabei werden sogenannte Fehlerlinks gesetzt.

De�nition 6 Sei v 2 K ein Knoten. Wir nennen

L(v) := Wort von der Wurzel r bis zu v

das Label von v. Au�erdem bezeichne

lp(v) =

�L�ange des l�angsten echten SuÆx � vonL(v); der Pr�a�x eines Muster aus P ist.

11

��

��

��

��

��

��

��

��

p

o

t

a

P1

P2

t

t

t

h

e

a

t

e

h

t

o

Wurzel r

: : :Pz

a

r

Abbildung 12: Keyword{Baum mit Fehler{Links am linken Ast

Wir setzen Fehler{Links nv f�ur jedes v 2 K, wobei

nv = Knoten in K mit L(nv) = �:

Algorithmus:

Wir vergleichen den Text T mit dem Keyword{Baum K. Nun tritt ein Mis-match zwischen T (c) und der Kante (w;w0) auf. Dann setzen wir:

l = c� lp(w); w = nw, falls lp(w) > 0 und l = c; w = r, falls lp(w) = 0.

2.1.1 Bestimmung der Fehler{Links in O(n)

Wir bestimmen die Fehler{Links induktiv �uber den Abstand zur Wurzel r.

� Induktionsanfang: Sei v ein Knoten mit Abstand 1. Dann setzen wirnv = r.

� Induktionsannahme: Seien die Fehlerlinks f�ur Knoten mit Abstand � kzur Wurzel bekannt.

� Induktionsschritt: Sei v ein Knoten mit Abstand k+1 zur Wurzel. Wirsuchen nun nv.

12

��

��

��

w

nwT (c)

l

T

Fehler{Link

Abbildung 13: Aho{Corasick Alg.

Es existiert ein Vorg�anger v0 von v und eine Kante (v0; v) mit einemZeichen x. Der Abstand von v0 zur Wurzel ist k, und damit kennenwir seinen Fehler{Link nv0 nach Annahme. L(nv) mu� ein SuÆx vonL(nv0) � x sein. Geht nun von diesem Knoten nv0 eine Kante mit demZeichen x ab, so setzen wir den Fehler{Link nv von v auf die Endeckedieser Kante.

Existiert diese Kante nicht, so kennen wir nach Voraussetzung denFehler{Link nn

v0, denn der Abstand zur Wurzel wird in jedem Schritt

echt kleiner. Geht nun von diesem Knoten nnv0eine Kante mit dem

Zeichen x ab, so setzen wir den Fehler{Link nv von v auf die Endeckedieser Kante.

Existiert diese Kante nicht, so kennen wir den Fehler{Link . . . usw.

Die Fehlerlinks werden damit tats�achlich in Zeit O(n) bestimmt, das siehtman wie folgt:

Sei Pi; jPij = t, ein Muster aus P. Wieviel Zeit wird gebraucht, um dieFehler{Links der Knoten auf dem Pfad von P in K zu bestimmen? Wirwissen:

13

� lp(v) � lp(v0) + 1.

� Wenn die Schleife zur Berechnung der nv k{mal durchlaufen wurde,dann ist lp(v) � lp(v0)� k

� lp(v) < t und lp(v) � 0

Das hei�t also, f�ur alle Knoten auf dem Pfad eines Musters der L�ange t wirddie Schleife insgesamt h�ochstens t Mal durchlaufen, innerhalb der Schlei-fe wird konstante Zeit ben�otigt. Die Gesamtl�ange aller Muster ist n, alsokann es zu h�ochstens n Schleifendurchl�aufen kommen, und damit werdenalle Fehler{Links in O(n) Zeit bestimmt.

F�ur den Fall, da� man Pi als Teilstring von Pj zul�a�t, mu� man zus�atzlicheOutput{Links hinzuf�ugen, die einem sagen, da� man gerade �uber ein MusterPi gelaufen ist. Dabei hilft die folgende

Beobachtung. Angenommen, bei der Suche wird der Knoten v in K er-reicht, c ist die aktuelle Position in T . Dann gilt :

Pi ist in T und endet in c()

v ist mit i markiert oder es gibt einen gerichteten Pfad vonFehler{Links zu einem mit i markierten Knoten (! Output{Link).

��

��

��

��

��

��

��

��

��

��

Pi

i

Output{Link

Abbildung 14: Output{Links

Das hei�t, es reicht im Algorithmus, bei jeder Kante (w;w0) in K zus�atzlichein Auftreten von Pi mit Ende in Position c im Text zu melden, wenn w0

mit i markiert ist oder es einen Pfad von Fehler{Links von w0 zu einem miti markierten Knoten gibt.

14

2.1.2 Anwendung 1: Matching mit Wildcards

De�nition 7 Wir nennen ein Zeichen � =2 �, das jedes Zeichen a 2 �matcht, eine Wildcard.

Aufgabe: Exaktes Matching von einem Muster P; jP j = n, mit Wild-cards gegen einen Text T; jT j = m, ohne Wildcards.

Ansatz: Wir haben ein Muster P der Form

P = �� : : : P1� : : : �P2� : : : Pk� : : : ;

wobei die Pi Teilmuster ohneWildcards sind. Wir de�nieren die MultimengeP = fP1; : : : ; Pkg und bestimmen zus�atzlich den Vektor l der Anfangsposi-tionen der Pi in P

l = (l1; l2; : : : ; lk):

C

T

: : :

Position j

Pi: : :P2

C(j � li + 1) = C(j � li + 1) + 1

P1

Abbildung 15: wild cards

Nun wenden wir hierf�ur den Aho{Corasick Algorithmus an. In einem Kon-trollfeld C der L�ange jT j addieren wir bei einem Matching eines Pi an derPosition j im Text in C an der Stelle C(j� li+1) eins. D.h. jedes Auftreteneines Musters Pi an einer Stelle j dient als Zeuge einer eventuellen Anfangs-position von ganz P bei j � li + 1. Liegen am Ende k Zeugen an einer Stellel in C vor, so ist dies eine Anfangsposition von P . Oder kurz :

C(l) = k () P startet in T (l)

Es gilt: C(l) � k, denn jedes Pattern Pi kann an einer festen Stelle l nur einMal ein Heraufsetzen des Z�ahlers verursachen.

Analyse: Die Konstruktion des Keyword{Baumes geht in Zeit O(n). Beider Suche entspricht eine Zeiteinheit einem Vergleich oder einem Hochz�ahlenin C.

Man hat C(i) � k ) Der A.C. Algorithmus l�auft in Zeit O(n + r � m) =O(rm), wobei r die Anzahl der Vorkommen von Mustern aus P bezeichnet.Ist diese nach oben beschr�ankt, so erh�alt man als Laufzeit O(m).

15

2.1.3 Anwendung 2: Zweidimensionales Matching

Seien ein rechteckiger Text T mit jT j = m und ein rechteckiges Muster P mitjP j = n gegeben. Dabei seien zuerst alle Zeilen von P verschieden. Gesuchtsind alle Auftreten von P in T .

P; jP j = nl Spaltenz ZeilenT; jT j = m; k Spalten

Abbildung 16: 2{dim. Matching

Man wandelt T um in die Form T 0 = Zeile1 $ Zeile2 $ . . . , wobei $ als Son-derzeichen dient, um ein Matching �uber das Zeilenende hinaus zu verhindern.Es sei Pi die i{te Zeile des Musters P , und P= fP1; : : : ; Pzg. Der Algorith-mus von Aho{Corasick, angewendet auf den Text T 0 und die PatternmengeP, liefert nun alle Auftreten von Zeilen von P in T .

In einem rechteckigen Kontrollfeld C; jCj = m, tr�agt man i an der Stelle(p; q) ein, wenn das Pattern Pi in Zeile p und Spalte q anf�angt.

Um die Vorkommen von ganz P in T zu �nden, mu� man in C das Pattern1 2 : : : z in einer Spalte �nden. Das geht mit einem beliebigen der nun schonvorgestellten Algorithmen zur Mustersuche in Zeit O(m+ z).

Die Restriktion, da� alle Zeilen von P verschieden sein m�ussen, l�a�t sichleicht aufheben: Identische Zeilen erhalten ein gemeinsames Label (z.B. dasder kleinsten Zeile dieser Gestalt), und zum Schlu� wird in C nach demPattern gesucht, das an der i{ten Stelle das Label der i{ten Zeile hat.

3 Matching mit regul�aren Ausdr�ucken

3.1 Wiederholung: Regul�are Ausdr�ucke

De�nition 8 Sei � ein endliches Alphabet f�ur das gilt: ( ; ) ; + ; � 62 �.Wir de�nieren induktiv:

16

1. � ist ein regul�arer Ausdruck und 8a 2 � gilt: a ist ein regul�arer Aus-druck.

2. Seien R1 und R2 regul�are Ausdr�ucke, dann sind auch die VereinigungR1 +R2, die Konkatenation R1 �R2 und (R1) regul�are Ausdr�ucke.

3. Sei R regul�arer Ausdruck, dann auch der Kleene{Abschlu� (R)�.

Zu jedem regul�aren Ausdruck l�a�t sich ein gerichteter Graph, der einem nicht-deterministischen, endlichen Automaten (nfa) entspricht, mit ausgezeichne-ten Knoten s und t sowie Kantenlabels aus �[ � konstruieren. Es entsprichtdann jeder gerichtete Weg von s nach t einemWort, das gem�a� dem regul�arenAusdruck gebildet wurde. Die Konstruktionsbeschreibung dieses Graphen istebenfalls induktiv:

s ta R = a

s t

s1

s2

t1

R1

R = R1 +R2

s1 t2

t1 = s2

R = R1 �R2

t1R1 R = (R1)�s t

t2

� �

��

R2

�

�

�

�

s1

Zu 1.

Zu 2.

Zu 3.

17

Beobachtung. # Zust�ande � 2jRj, denn in jedem Schritt werden h�ochstenszwei neue Knoten zum Graphen hinzugef�ugt.

Beispiel. R = (d+ o+ g)((n+ o)w)�(c+ l + �)(c+ l)

s

d

o

g

�

n

o

�

c

l

e

c

l

w t

3.2 Der Algorithmus

Aufgabe: Sei T ein Text und R ein regul�arer Ausdruck. Wir suchen dieVorkommen von R in T , anders ausgedr�uckt: Gibt es k; j, so dass T [k; j]entsprechend R gebildet ist?

Dazu bilden wir den regul�aren Ausdruck ��R und testen f�ur alle i, ob ��Rden Pr�a�x T [1::i] matcht. Das wiederum geht wie folgt.

De�nition 9 Sei G der gerichtete Graph zu ��R, dann de�nieren wir dieN(i){Nachbarschaft von s in G induktiv:

N(0) = Alle Zust�ande, die von s auf �-Wegen erreichbar sind.N(i) = Alle Zust�ande, die von N(i� 1) mit T (i){ oder

�{ �Uberg�angen zu erreichen sind.

Damit gilt: T [1; i] matcht R () t 2 N(i).

Satz 2 (ohne Beweis) Sei T; jT j = m, ein Text und R ein regul�arer Aus-druck mit n Zeichen. Dann kann man in Zeit O(n �m) testen, ob ein Teil-string von T den Ausdruck R matcht.

18

4 Seminumerisches Stringmatching

Bisher haben wir Zeichen f�ur Zeichen Text und Pattern miteinander vergli-chen, nun wenden wir uns Algorithmen zu, in denen wir uns der Algebra,Zahlentheorie, . . . bedienen.

4.1 Shift{AND{Methode (nach Baeza{Yates, Gonnet '92)

Diese Methode benutzt Bitoperationen und ist besonders e�ektiv f�ur kurzeMuster.

4.1.1 Exaktes Matching

Ein exaktes Matching zwischen einem Text T; jT j = m und einem MusterP; jP j = n geht wie folgt:

De�nition 10 Wir de�nieren eine n � m{Matrix M , die nur Nullen undEinsen als Eintr�age enth�alt.

Mij =

�1 ; wenn P [1; : : : ; i] T [j � i + 1; : : : ; j] matcht0 ; sonst

Wenn der Eintrag Mnj = 1 ist, dann haben wir ein Matching von P an derPosition j endend. Diese Matrix l�a�t sich folgenderma�en aufbauen:

De�nition 11 Sei x 2 �. Zu x de�niere den Vektor U(x) 2 f0; 1gn durchU(x)i = 1 () P (i) = x, also U(x) = (0; : : : ; 0; 1|{z}

Position i

; 0; : : : ; 0)

und Vektor Bitshift(M(j)) = Spalte j von M um eine Position nach untenverschoben und eine 1 an die oberste Position gesetzt. Bitshift(M(j)) 2f0; 1gn.

Beobachtung. Mij = 1 () Mi�1 j�1 = 1 und U(T (j))i = 1.

Im Algorithmus gehen wir bei der Berechnung von M induktiv vor.

1. Wir initialisieren die 1. Spalte M(1):

M11 =

�1 : wenn T (1) = P (1),0 : sonst.

8i 2 f2::ng Mi1 = 0:

19

2. Sei M(j � 1) berechnet.

3. Setze M(j) = Bitshift(M(j � 1)) AND U(T (j)).

Beispiel. Sei P = abaac, T = xabxabaaxa. Damit ist T (7) = a, und

M(7) =

0BBBB@

10100

1CCCCA und U(a) =

0BBBB@

10110

1CCCCA.

Nun bestimmen wir M(8) 2 f0; 1gn mit Hilfe der De�nition. . .

P [1] = T [8] ) M18 = 1:P [1; 2] 6= T [7; 8] ) M28 = 0:P [1; 3] = T [6; 8] ) M38 = 0:P [1] = T [5; 8] ) M48 = 1:P [1] 6= T [4; 8] ) M58 = 0:

9>>>>=>>>>;)M(8) =

0BBBB@

10010

1CCCCA

. . . und nach Induktionsvorschrift:

M(8) =

0BBBB@

11010

1CCCCA AND

0BBBB@

10110

1CCCCA =

0BBBB@

10010

1CCCCA

Analyse.

� Es fallen O(n �m) Bitoperationen an. F�ur kleine n ist der Algorithmussehr eÆzient, da die Bitoperationen im Rechner sehr schnell ablaufen.

� Der Speicherverbrauch ist gering, da immer nur 2 Spalten aktiv sind.

4.1.2 Matching mit Fehlern (Wu, Manber '92)

Wir verallgemeinern nun den Algorithmus, indem wir bis zu k Fehler zulas-sen. Dabei k�onnen Fehler Mismatches, Insertions oder Deletions sein. DerUnix{Befehl agrep arbeitet mit diesem Algorithmus.

Wir wenden uns nur den Mismatches zu. Dazu de�nieren wir uns k + 1(n�m){Matrizen M0;M1; : : : ;Mk.

20

De�nition 12

M lij =

�1 ; wenn P [1; : : : ; i] matcht T [j � i+ 1; : : : ; j] mit � l Fehlern.0 ; sonst.

Beobachtung. Bei der induktiven Berechnung von M l(j) k�onnen 3 F�alleauftreten:

1. Es liegen maximal l � 1 Fehler bis zur Position j vor !M l�1(j).

2. Es liegen bis zur Position j � 1 schon l Fehler vor, und P (i) = T (j).

3. Es liegen bis zur Position j � 1 erst l � 1 Fehler vor,daher ist es egal,ob das letzte Zeichen richtig ist.

Daraus erhalten wir die Formel

M l(j) = M l�1(j) OR ( Bitshift(M l(j � 1)) AND U(T (j)) ) OR M l�1(j�1) :

Es ergibt sich eine Laufzeit von O(k �m � n).

4.2 Fingerprint{Methode nach Karp{Rabin '87

Wir betrachten das exakte Matching{Problem. Dabei werden arithmetischeOperationen an Stelle von Vergleichen durchgef�uhrt. Das Verfahren ist ran-domisiert, und liefert alle Matches sowie m�oglicherweise einige falsche Mat-ches. Wir werden sehen, da� es m�oglich ist, die Wahrscheinlichkeit f�ur einfalsches Match sehr klein zu halten.

In diesem Abschnitt schr�anken wir uns auf das Alphabet � = f0; 1g ein, dieMethode kann aber auch so modi�ziert werden, da� sie f�ur gr�o�ere Alphabetearbeitet.

4.2.1 Algorithmus

De�nition 13 Sei T; jT j = m, ein Text und P; jP j = n, ein Pattern. Dannf�uhren wir folgende Abbildung in die nat�urlichen Zahlen ein.

P 7! H(P ) :=nXi=1

2n�i � P (i)

21

Tr 7! H(Tr) =nXi=1

2n�i � Tr(i);

wobei Tr das bei r beginnende Teilwort von T bezeichnet (Also gilt Tr(i) =T (r + i� 1)).

Eine Verallgemeinerung des Algorithmus auf Alphabete mit s Zeichen erh�altman, indem man in der Abbildung Potenzen von s betrachtet.

Beobachtung. P startet in T an der Position r () H(P ) = H(Tr),denn jede nat�urliche Zahl hat eine eindeutige Darstellung als Summe von2{er Potenzen.

Die Zahlen, die dabei auftreten, k�onnen sehr gro� sein. Um dies zu vermei-den, rechnen wir modulo einer zuf�allig gew�ahlten Primzahl p. Dabei k�onnenallerdings falsche Matches entstehen, wenn p ein Teiler von jH(P )�H(Tr)jist.

Auf der einen Seite wollen wir p m�oglichst klein w�ahlen, um die Ergebnisseklein zu halten, andererseits werden dadurch falsche Matches wahrscheinli-cher. Wir verwenden eine zuf�allig gew�ahlte Primzahl, und es wird gezeigt,da� die Wahrscheinlichkeit f�ur ein dadurch entstehendes falsches Match kleinist.

Hp(P ) := H(P ) mod p

Bei der Berechnung von Hp(P ) gehen wir nach dem Hornerschema vor, soda� O(n) Rechenoperationen anfallen.

Hp(P ) = [[: : : [P (1)�2 mod p+P (2)]�2 mod p+: : : P (n�1)]�2 mod p+P (n)] mod p

Hp(T1) l�a�t sich ebenso mit O(n) Rechenoperationen berechnen. Wie wirin der �Ubung gesehen haben, l�a�t sich Hp(Tr) aus Hp(Tr�1) mit konstantemAufwand berechnen.

Bevor wir eine Aussage �uber die Wahrscheinlichkeit von falschen Matchesmachen, zuerst ein kleiner Aus ug in die Zahlentheorie.

4.2.2 Einiges �uber Primzahlen

De�nition 14 Sei n eine beliebige nat�urliche Zahl, dann sei

�(n) := Anzahl der Primzahlen � n:

Dazu nun ein Satz, ein Lemma und ein Korollar.

22

Satz 3 (ohne Beweis) Sei n 2 N. Dann gilt folgende Ungleichung:

n

lnn� �(n) � 1:26

n

lnn

Lemma 1 F�ur n � 29 gilt:

Yp�n; p prim

p > 2n

Korollar 2 Sei n � 29 und x � 2n. Dann hat x weniger als �(n) verschie-dene Primteiler.

Beweis. (indirekt)

Wir nehmen an, x habe mehr als �(n) verschiedene Primteiler q1; q2; : : : ; qk,und gleichzeitig 2n � x. Dann gilt:

x �kYi=1

qi �Y

(erste k Primzahlen) >Y

(erste �(n) Primzahlen) > 2n:

Widerspruch: 2n > 2n. 2

4.2.3 Die Wahrscheinlichkeit f�ur ein falsches Match

Satz 4 Sei P; jP j = n, ein Pattern, T; jT j = m, ein Text und n �m � 29.F�ur i 2 N gilt nun: Falls p eine zuf�allige Primzahl � i ist, so ist dieWahrscheinlichkeit eines falschen Matches zwischen P und T � �(n�m)

�(i).

Beweis. Sei R die Menge der Positionen von T , an denen P nicht beginnt:

s 2 R () H(P ) 6= H(Ts):

Dann ist jRj � jT j = m, und es giltQs2R

jH(P )�H(Ts)j| {z }�2n

� 2n�m.

Mit dem Korollar 2 erhalten wir:Ys2R

jH(P )�H(Ts)j hat � �(n �m) verschiedene Primteiler.

Zu einem falschen Match an der Stelle s im Text kommt es, wenn H(P ) =H(Ts) mod p ist, also wenn p die Zahl jH(P )�H(Ts)j teilt. In diesem Fall

23

teilt p nat�urlich das obige Produkt, also gibt es ein falsches Match im Textdann, wenn p einer der � �(n � m) Primteiler des Produktes ist, und dieWahrscheinlichkeit Pr daf�ur betr�agt

Pr � �(n �m)

�(i): 2

Beispiel. Sei n = 250; m = 4000 und i = n � m2. Dann erhalten wir:Pr(falsches Match)< 10�3 und i < 232. Die Zahlen bleiben damit f�ur einenComputer klein genug, und die Fehlerwahrschlichkeit ist auch relativ klein.

5 SuÆx{B�aume und ihre Anwendungen

Die Idee der SuÆxb�aume wurde erstmals von Weiner '73 ausgef�uhrt. Sie hatallerdings erst '95 wirklich Beachtung gewonnen, als Ukkonen einen einfa-chen Linearzeitalgorithmus zu ihrer Konstruktion gefunden hat. Dazu sp�atermehr.

Der herausragende Vorteil bei der Benutzung von SuÆx{B�aumen gegen�uberden nun schon bekannten Algorithmen zum String{Matching ist, da� derText in linearer Zeit vorverarbeitet wird, und nachfolgend jede Anfrage f�urbeliebige Pattern der L�ange m in Zeit O(m) beantwortet werden kann.

De�nition 15 Sei S; jSj = m, ein String. Dann nennen wir einen gerich-teten Baum T mit Wurzel und Bl�attern 1; : : : ; m den SuÆxbaum zu S, wennfolgende Eigenschaften erf�ullt sind:

� Die Kanten sind mit Teilstrings markiert.

� Innere Knoten haben Ausgrad � 2.

� Keine 2 Kanten aus einem Knoten starten mit dem selben Buchstaben.

� Die Kantenlabel auf dem Weg von der Wurzel zu Blatt i entsprechendem SuÆx S[i;m].

Bemerkung. Um zu vermeiden, dass ein SuÆx von S ein echter Teilstringist, f�ugen wir am Ende von S das Sonderzeichen $ an. Damit wird erreicht,dass wirklich jeder SuÆx von S einem Blatt von T entspricht. Konstruiertman den SuÆxbaum, indem von hinten startend immer wieder losl�auft, soerh�alt man f�ur seine Konstruktion eine Laufzeit von O(m2).

Man kann auch einen verallgemeinerten SuÆx{Baum f�ur mehrere Stringskonstruieren. Dabei mu� in den Bl�attern zus�atzlich die Information, auswelchem String der SuÆx, der hier endet, kommt, gespeichert werden.

24

3 5 2

4c6

xa

1bxacc

bxac

baxc

a

c

Beispiel. S = xabxac.

5.1 Anwendungen

Zur Motivation nun ein paar Anwendungsbeispiele von SuÆxb�aumen.

5.1.1 Exaktes Matching

Sei P; jP j = n; ein Pattern und T; jT j = m ein Text. Wir erstellen denSuÆxbaum T f�ur T in O(m) Zeit. Dann wird P mit T verglichen, d.h., dasMuster wird im SuÆxbaum bei der Wurzel beginnend

"abgelaufen\. Dabei

fallen O(n) Vergleiche an. Die Anfangsstellen von Matches von P in T ent-sprechen den Bl�attern unter einer Position im Baum mit Label P . DieseBl�atter �nden wir in O(k) Zeit, wobei k der Anzahl der Matches entspricht.Alles in allem l�auft exaktes Matching in O(n+m+k). Der Baum ist hierbeiunabh�angig von P , und mu� damit nur ein Mal erstellt werden. Bei erneutemMatching mit einem anderen Pattern ist die Laufzeit somit nur O(n+ k).

5.1.2 Eine Datenbank f�ur Muster

Sei eine Datenbank von Mustern Pi,P jPij = m, und ein String S der

L�ange n gegeben. Wir suchen alle Muster, die S als Teilstring enthalten.Nachdem der verallgemeinerte, gemeinsame SuÆxbaum f�ur die Muster einMal in Zeit O(m) konstruiert wurde, kann eine Anfrage f�ur ein beliebiges Sin Zeit O(n+k) bearbeitet werden: Der String S wird im SuÆxbaum bei derWurzel beginnend abgelaufen, und alle Bl�atter unter S geh�oren zu Mustern,die S als Teilstring enthalten.

25

5.1.3 Longest{Common{Substring von S1 und S2

Wir konstruieren den gemeinsamen SuÆxbaum von S1 und S2 und markierendie inneren Knoten mit i 2 f1; 2g, falls der Unterbaum ein mit i markiertesBlatt enth�alt. Um den LCS zu �nden, suchen wir den tiefsten Knoten mitbeiden Marken.

Bei der Verallgemeinerung auf S1; S2; : : : ; SK mit Gesamtl�ange n, wollen wirf�ur alle 2 � k � K die L�ange des l�angsten Teilstring, der in � k Stringsvorkommt, berechnen. Dazu de�nieren wir f�ur alle Knoten v des Baumes dieAbbildung

v 7! C(v) := Anzahl verschiedener Blattlabels unter v:

Gesucht sind dann die Knoten v mit C(v) � k. Die Abbildung bestimmenwir induktiv:

1. Wir fangen in den Bl�attern an. Deren Eltern wird ein (0-1)-Vektor wder L�ange K zugeordnet mit w(i) = 1 () Ein Blatt hat Marke i,und sonst w(i) = 0.

2. Sei v ein Knoten, dann ist

w(v) =_

c Kinder

w(c) und C(v) =KXi=1

w(i):

Nun mu� noch f�ur 2 � k � K ein tiefster Knoten mit k verschiedenenBlattlabels berechnet werden, und die Ergebnisse von K auf K�1; K�2; : : :akkumuliert werden (es mu� ja nicht f�ur jedes k ein Knoten mit C(v) = kexistieren).

Insgesamt fallen dabei O(K � n) Operationen an: O(n) f�ur die Konstruktiondes SuÆxbaumes, und O(K �n), um f�ur jeden der O(n) Knoten den Vektor derL�ange K zu bestimmen. Das Suchen der tiefsten Knoten und akkumulierender Werte geht ebenfalls in O(K � n) Zeit.Sp�ater werden wir eine L�osung kennenlernen, die nur lineare Zeit ben�otigt.

5.1.4 All{Pairs{SuÆx{Pr�a�x{Matching

Gegeben sind Strings S1; : : : ; Sk mit Gesamtl�ange n, gesucht ist f�ur alle Paare(i; j) der l�angste SuÆx von Si, der einen Pr�a�x von Sj matcht. Die Anzahlder Ergebnisse ist also k2. Dieses Problem tritt beim Suchen eines m�oglichst

26

kurzen Strings S auf, der alle Si als Teilstrings enth�alt. Insbesondere ist dasf�ur biologische Anwendungen relevant.

F�ur die Strings wird ein gemeinsamer SuÆx{Baum konstruiert. Dann spei-chern wir zu jedem inneren Knoten v eine Liste der Strings, f�ur die bei v eineTerminalkante (Kante nur mit dem Terminalzeichen $) abgeht. Wenn bei veine Terminalkante von Si abgeht hei�t das, dass in v ein SuÆx von Si endet.

Um nun die l�angsten SuÆx{Pr�a�x{Matches zu bestimmen, wird jeder StringSj im Baum abgelaufen. Dabei wird f�ur jedes i der tiefste Knoten v auf demPfad ausgegeben, bei dem i in der Liste der Terminalkanten steht.

Die Laufzeit betr�agt O(n) f�ur die Konstruktion des Baumes, und O(k2) f�urdas Finden der Matches, insgesamt also O(n+ k2).

5.2 Konstruktion von SuÆxb�aumen in Linearzeit

Sei im folgenden S ein String mit m Zeichen und � ein endliches Alphabet.Bei der Konstruktion folgen wir dem Artikel von Ukkonen von '95.

Grundidee des Algorithmus:

� Wir konstruieren SuÆxb�aume f�ur immer l�anger werdende Pr�a�xe S[1; i],i = 1; : : : ; m.

� Wir konstruieren zun�achst implizite SuÆxb�aume.

De�nition 16 Der implizite SuÆxbaum (SB) von S entsteht aus dem SBvon S$ durch folgende Regeln:

� Streiche $ aus den Kantenlabels.

� Entferne Kanten ohne Label.

� Entferne innere Knoten mit genau einem Kind.

Wir bezeichnen mit Ti den impliziten SuÆxbaum zu S[1; i].

Ukkonen's Algorithmus(high{level)

Erzeuge T1.for i = 1; ::; m� 1

for j = 1; ::; i+ 1Finde Ende des Weges S[j; i] in Ti undfalls notwendig, f�uge S(i+ 1) an.

end for

9>>=>>;Phase (i+ 1)

end for

27

Beispiel. S$ = xabxa$.

bxa$

36 $ 4

a

2

bxa$xa1

bxa$$$ = T 7!

bxa

abxa

xabxa= T5

5

Abbildung 17: SuÆxbaum und impliziter SuÆxbaum von S.

In der Phase (i + 1) werden die SuÆxe S[1; i + 1]; S[2; i + 1]; : : : ; S[i; i +1]; S[i + 1; i + 1] des Pr�a�xes S[1; i + 1] in Ti eingef�ugt. Dabei werden diefolgenden Erweiterungsregeln benutzt:

Es sei S(i+ 1) = b, und wir sind aktuell in der j{ten Erweiterung.

Regel 1: Der Weg endet in einem Blatt, dann erweitere das letzte Kanten-label um b.

Regel 2: Der Weg endet"im Baum\.

1.Fall: In innerem Knoten: Kante mit Label b zu Blatt j einf�ugen.

2.Fall: Auf Kante: Neuen inneren Knoten und Kante mit Label b erzeugen.

Regel 3: S[j; i] � b gibt es schon, dann tue nichts.

Beispiel. Sei der implizite SuÆxbaum T5 f�ur den Teilstring axabx schonkonstruiert, und das 6. Zeichen sei b. Wir betrachten nun die Erweiterungvon T5 nach T6. An den Kanten zu den Bl�attern 1, 3, 2 und 4 wird Regel1 angewendet und ein b angeh�angt. An der Kante zu Blatt 5 wird Regel 2angewendet und ein neuer innerer Knoten gescha�en. An der Kante zu Blatt4 wird f�ur den SuÆx b Regel 3 angewendet: b ist schon da, tue nichts.

1 3 2

45bxbxabxb

bxba

abx

b

x

b

28

Implementiert man die high{level{Version, dann fallen in der Phase (i + 1)O(i2) Operationen an, und insgesamt erh�alt man O(m3) als Laufzeitverhal-ten. Nun folgen einige Verbesserungen, die schlie�lich zu einem Linearzeital-gorithmus f�uhren.

5.2.1 Erster Trick: SuÆx{Links

Als erste Verbesserung f�uhren wir, �ahnlich wie die Fehler{Links im Aho{Corasick Algorithmus, SuÆx{Links ein, um Spr�unge in der Phase (i + 1)zu erm�oglichen. Diese Spr�unge werden es erlauben, die Enden der S[j; i]schneller zu erreichen.

De�nition 17 Sei x� ein String, x 2 �. Wenn es f�ur einen inneren Knotenv mit Label x� einen anderen inneren Knoten s(v) mit Label � gibt, so hei�t(v; s(v)) SuÆx{Link. Wenn � der leere String ist, setzen wir einen SuÆx{Link zur Wurzel.

v

s(v)�

�

x

Wurzel

Abbildung 18: SuÆx{Link

Lemma 2 Falls eine neue Kante mit Label b am inneren Knoten v mit Labelx� in der j{ten Erweiterung der Phase (i+ 1) entsteht, dann gibt es bereitseinen inneren Knoten w mit Label �, oder w entsteht in der (j + 1){tenErweiterung, n�amlich dann, wenn v selbst erst in der j{ten Erweiterungentstanden ist.

Beweis. Eine neue Kante entsteht, d.h. wir haben Regel 2 angewendet.

Fall 1: v ist schon vor der j{ten Erweiterung innerer Knoten, und es gehensomit mindestens zwei Kanten mit Zeichen c bzw. c0 beginnend bei v los,

29

j

x�

v

c0 j

�

c0

w

j

x�

v

c

j

w

�

cS(i+ 1)S(i+ 1)S(i+ 1)S(i+ 1) c c

Fall 2S(i+ 1) 6= c0Fall 1, S(i+ 1) 6= c;

wobei c 6= c0. Da � das SuÆx S[2; l] eines Pr�a�xes S[1; l], wobei l < i, ist,gibt es von der Wurzel einen Weg zu einem Knoten w mit Label � und � 2ausgehenden Kanten mit Label c bzw. c0.

Fall 2: v entsteht in der j{ten Erweiterung der Phase (i + 1), und es gehenzwei Kanten mit c bzw. S(i+1) beginnend aus. In der (j+1){ten Erweiterungwird nun � um S(i+ 1) erweitert, und der Knoten w entsteht analog zu v.

2

Korollar 3 In einem impliziten SuÆxbaum gibt es am Ende jeder Phase f�uralle inneren Knoten SuÆx{Links.

Was hilft uns das nun weiter? Es spart jede Menge Wege von der Wurzelabw�arts! Dazu die folgende

Beobachtung. Die erste Erweiterung in jeder Phase (i+1) ist trivial: S[1; i]endet in Ti immer in einem Blatt. Auf dieses Blatt halten wir einen Pointerfest. Von Erweiterung j kommen wir nun leicht zur (j+1){ten Erweiterung:

Sei S[j; i] = x�, dabei x 2 �, und sei (v; j) die Kante zu Blatt j. Gesuchtist f�ur die (j + 1){te Erweiterung ein Knoten mit Label �. Es k�onnen zweiF�alle auftreten:

1. v ist die Wurzel. Dann laufe � von der Wurzel aus.

2. v ist ein innerer Knoten. Dann gibt es einen SuÆx{Link (v; s(v)), unds(v) hat ein Label, das ein Pr�a�x von � ist. Nun m�ussen wir von s(v)aus nur noch den

"Rest\ laufen.

Das alleine verbessert die Laufzeit im worst{case noch nicht, daf�ur werdenweitere �Uberlegungen ben�otigt.

30

5.2.2 Zweite Verbesserung: Skip & Count

Hinter dem Skip & Count Trick verbirgt sich folgendes: Die Kantenlabelswerden nicht explizit an den Kanten gespeichert, sondern nur ihre Anfangs{und Endpositionen im String. Beim Herunterlaufen von s(v) aus wird nunnicht jeder Buchstabe verglichen, sondern nur der erste Buchstabe einer Kan-te. Da alle Kanten von einem Knoten aus mit unterschiedlichen Buchsta-ben beginnen, reicht das aus. Speichert man zu jeder Kante ihre L�ange,so kann man nach einem Vergleich die restlichen Buchstaben dieser Kante�uberspringen.

De�nition 18 Sei v Knoten in einem SuÆxbaum. Dann nennen wir dieAnzahl der Kanten auf dem Weg von v zur Wurzel Knotentiefe von v.

Lemma 3 Sei (v; s(v)) SuÆx{Link. Dann gilt:

Knotentiefe (v) � Knotentiefe (s(v)) + 1

Beweis. Zuerst ein Bild:

f

d

j

x

ab

c

d

e

g

h

i

j

a

b

c

e

f

g

h

i

Sei (v; s(v)) ein SuÆx{Link. Dann ist nach De�nition das Label L(v) = x�,wobei x 2 � Zeichen und � 2 �� Teilstring, und L(s(v)) = �. Sei w derKnoten mit Knotentiefe(w) = 1 auf dem Weg von der Wurzel r nach v,

31

und die Kante (w; r) nur mit einem Zeichen markiert. Dann ist (w; r) einSuÆx{Link. Sei nun u ein beliebiger Knoten, u 6= w, auf dem Weg von rnach v. Dann ist u ein innerer Knoten, und es existiert somit ein SuÆx-Link(u; s(u)). Der Knoten s(u) ist dann ein Knoten auf dem Weg von r nach s(v).Sei nun u0 ein weiterer Knoten auf dem Weg von r nach v mit u 6= u0, danngilt weiter s(u) 6= s(u0). Nach diesen Vor�uberlegungen nun zum Beweis. MitAusnahme des ersten Knotens auf dem Weg von r nach v existiert immer einKnoten auf dem Weg von r nach s(v), und diese sind paarweise verschieden.F�ur den ersten Knoten auf dem Weg von r nach v gibt es keinen SuÆx{Link(und damit keinen korrespondierenden Knoten auf demWeg von r nach s(v))genau dann, wenn die Kante von r dorthin nur ein Zeichen tr�agt. 2

Satz 5 Mit Skip & Count kann jede Phase (i+1) in O(m) realisiert werden.

Beweis. Zur Erinnerung noch einmal die Vorgehensweise bei Skip & Count:Wir be�nden uns w�ahrend einer Phase (i+1) nach der j{ten Erweiterung ir-gendwo im Baum, und wollen nun an S[j+1; i] das Zeichen S(i+1) anh�angen.Wir suchen also von S[j; i+ 1] aus das Ende von S[j + 1; i]. Dazu gehen wirim Baum nach oben zum n�achsten Knoten v (auch up{Schritt genannt), undfolgen dem SuÆx{Link (v; s(v)). Diese beiden Schritte laufen in konstan-ter Zeit ab und sind daher nicht f�ur die Laufzeitanalyse relevant. Bei s(v)vergleichen wir das erste Zeichen mit den ausgehenden Kanten und springendann bis zum n�achsten Knoten (down{skip).

Nun analysieren wir, wie viele down{skips ben�otigt werden. Dazu beobachtenwir den Verlauf der aktuellen Knotentiefe w�ahrend einer Erweiterung undschlie�lich einer Phase. Wir wissen, dass die aktuelle Knotentiefe bei jederErweiterung maximal m ist, da der Baum maximale Tiefe m hat.

In jeder Erweiterung passiert folgendes: Wir gehen im up{Schritt im Baum� 1 Schritte Richtung Wurzel, und beim Folgen des SuÆx{Links wird derAbstand zur Wurzel nach dem vorherigen Lemma um � 1 geringer. Insge-samt gehen wir also maximal 2 Schritte Richtung Wurzel, d.h. die aktuelleKnotentiefe verringert sich um h�ochstens 2. �Uber alle Erweiterungen 1 bisi+1 verringert sich damit die aktuellen Knotentiefe um� 2�m, da (i+1) � m.

Ohne die up{Schritte und SuÆxlinks k�onnten wir maximal bis zur Tiefe mhinunterspringen. Nun springen wir zus�atzlich um � 2�m nach oben, d.h. wirk�onnen insgesamt nur � 3 �m down{skips machen. Damit ergibt sich f�ur jedePhase eine Laufzeit von O(m). 2

Die resultierende Gesamtlaufzeit ist an dieser Stelle immer noch quadratisch,doch mit der n�achsten Beobachtung und einem weiteren kleinen Trick l�a�tsie sich zur versprochenen Linearzeit reduzieren.

32

Beobachtung.

1. Wenn Regel 3 das erste Mal angewendet wird, dann ist die Phase be-endet, da danach nur noch Regel 3 vorkommt.

2."Einmal Blatt, immer Blatt\. Wenn ein Blatt einmal erzeugt wordenist, so bleibt es immer ein Blatt. Alle folgenden Erweiterungen andieser Stelle gehen somit gem�a� Regel 1.

In der Phase (i+ 1) merken wir uns den gr�o�ten Index ji+1, f�ur den gilt:

8 1 � k � ji+1 : Die k{te Erweiterung erfolgte nach Regel 1 oder 2, d.h. alleSuÆxe S[1; i+ 1] : : : S[ji+1; i+ 1] geh�oren zu Bl�attern.

Bei der Implementierung gehen wir nach Beobachtung 2 beim Einf�ugen einerneuen Kante bzw. Blattes, wie folgt vor:

F�ur jede Kante, die zu einem Blatt f�uhrt, speichern wir das Paar (p; e). Dabeiist p die Anfangsposition des entsprechenden SuÆx in S und e ein globalerIndex, der nur ein Mal pro Phase von i auf i+1 erh�oht wird. Damit wird mitkonstantem Aufwand an allen Bl�attern gleichzeitig das neue Zeichen S(i+1)nach Regel 1 angef�ugt.

Diese �Uberlegungen verwenden wir nun, um den Algorithmus in der Phase(i+ 1) zu verbessern.

Phase (i+ 1):

1. Setze e auf (i+ 1). Damit werden alle Bl�atter nach Regel 1 erledigt.

2. Berechne die Erweiterungen ji + 1 bis j� explizit, wobei j� das ersteAnwenden von Regel 3 markiert.

3. Setze ji+1 auf j� � 1.

Bemerkung. In der Phase (i+2) fangen wir mit den expliziten Vergleichenalso bei der Erweiterung j� an.

Satz 6 T1; T2; : : : ; Tm k�onnen in O(m) konstruiert werden.

Beweis. In jeder Phase wird f�ur die impliziten Erweiterungen nach Regel 1nur konstante Zeit ben�otigt, siehe oben. �Uber alle m Phasen summiert sichdas also zu Zeit O(m).

33

Zwei aufeinander folgenden Phasen haben � 1 explizite Vergleiche gemein-sam, n�amlich bei j�. Die aktuelle Knotentiefe am Ende der expliziten Ver-gleiche einer Phase ist gleich der aktuellen Knotentiefe bei Beginn der expli-ziten Vergleiche der darau�olgenden Phase. Durch Betrachten der aktuellenKnotentiefe (die durch m beschr�ankt ist) im Verlauf des Algorithmus, undArgumente �ahnlich denen im Beweis von Satz 5 , kommt man auf insgesamtO(m) explizite Erweiterungen w�ahrend des gesamten Algorithmus. 2

Korollar 4 Der SuÆxbaum f�ur S$ l�a�t sich in O(m) konstruieren.

Beweis. Der implizite SuÆxbaum wird in linearer Zeit konstruiert, und dasEinf�ugen von $ als letztem Zeichen geht ebenfalls in Linearzeit. 2

5.3 SuÆx{Arrays und Anwendungen

SuÆx{Arrays sind eine speichereÆziente Variante von SuÆxb�aumen, die be-sonders bei gro�en Alphabeten Verwendung �ndet.

Wir speichern dazu in einem Array Pos der L�ange m die Anfangspositionender SuÆzes von S in lexikographischer Ordnung <, wobei gilt 8a 2 �; $ < a.

Beispiel. S = mississippi, Pos = 11; 8; 5; 2; 1; 10; 9; 7; 4; 6; 3

Fakt. Das SuÆx{Array erh�alt man aus dem SuÆx{Baum durch lexikogra-phische Tiefensuche in linearer Zeit.

Durch bin�are Suche kann man exaktes Matching in SuÆx{Arrays f�ur ein Pat-tern P; jP j = n und einen Text der L�angem in Zeit O(n�logm) durchf�uhren.Die Idee dazu ist:

Es bezeichnen L und R den linken und rechten Rand des aktuellen Suchin-tervalls in Pos, zu Anfang also L = 1; R = m. In jeder Iteration der bin�arenSuche wird P mit dem SuÆx Pos(M), wobei M = d(L + R)=2e ist, vergli-chen. Je nach Ergebnis wird dann L oder R auf M gesetzt. Es reicht, inPos den ersten und den letzten SuÆx zu �nden, der mit P anf�angt. Wegender lexikographischen Ordnung in Pos sind alle anderen Vorkommen von Pin T genau die, die in Pos zwischen diesen beiden stehen.

In jeder Iteration gibt es O(n) Vergleiche, und insgesamt O(logm) Iteratio-nen, was zu der oben angegebenen Laufzeit f�uhrt. Durch einige Tricks kannman das verbessern und eine Laufzeit von O(n+logm) erreichen (!�Ubung).

34

6 SuÆxb�aume und lca{Anfragen

De�nition 19 Sei T ein Baum, r seine Wurzel und v; u Knoten. Dannde�nieren wir den lowest common ancestor:

lca(u; v) = tiefster Knoten, der auf dem Weg von v nach r und auf dem Wegvon u nach r liegt.

Nehmen wir nun an, wir k�onnten nach einer Vorverarbeitung von T in Li-nearzeit, die lca{Anfragen in konstanter Zeit beantworten. Dann k�onntenwir folgende Probleme eÆzient l�osen.

Beispiel 1 Longest{Common{Extension:

Seien S1; S2 Strings. Zu einem gegebenen Paar (i; j) suchen wir nun das ma-ximale k, so dass S1[i; i+k] = S2[j; j+k]. Dazu betrachten wir den gemeinsa-men SuÆxbaum von S1 und S2 und bestimmen den lca(Blatt(1; i);Blatt(2; j)).Dabei bezeichnet Blatt(l; i); l = 1; 2; : : :, das Blatt, das im gemeinsamen Suf-�xbaum von S1 und S2 zum SuÆx Sl[i; nl] geh�ort.

Das Konstruieren des gemeinsamen SuÆxbaumes geht in linearer Zeit, undnach Annahme k�onnen wir nach ebenfalls linearer Vorverarbeitung die lca{Anfragen in konstanter Zeit beantworten.

Beispiel 2 Maximale Palindrome

Wir suchen zu einem vorgegebenen q in einem String S das maximale geradePalindrom mit Mitte zwischen Position q und q + 1. Palindrome sind Worte� 2 ��, mit � = �rev, und gerade soll gerade Anzahl von Zeichen in �bedeuten. Wir betrachten den gemeinsamen SuÆxbaum von S und Srev undbestimmen lca(q+1; n�q+1) f�ur das maximale gerade Palindrom mit Mittezwischen q und q + 1.

Beispiel 3 Matching mit � k Mismatches

Gegeben ein Pattern P der L�ange n und ein Text T der L�ange m, so sindalle Auftreten von P in T mit � k Mismatches gesucht. Eine M�oglichkeit,das Problem mit Hilfe von lca{Anfragen in Zeit O(k � m) zu l�osen, ist diefolgende:

F�ur jede Stelle i in T wird in Zeit O(k) bestimmt, ob hier ein Match mit� k Fehlern zwischen P und T anf�angt. Dazu wird die Longest{Common{Extension (kurz lce) zwischen P und T [i;m] bestimmt. Hat diese die L�angej, so gibt es also ein Mismatch zwischen P (j+1) und T (i+j). Weiter geht esmit lce von P [j+2; n] und T [i+j+1; m], . . . . Jede lce{Anfrage braucht lautBeispiel 1 nur konstante Zeit. Ist nach � k Wiederholungen das Ende von Perreicht, so ist Position i von T der Anfang eines der gesuchten Matches.

35

6.1 lca{Anfragen in konstanter Zeit

Dieses Kapitel pr�asentiert ein rein graphentheorethisches Resultat, das je-doch �au�erst wichtige Anwendungen im String{Matching Bereich hat, siehevorhergehendes Kapitel. Die Aufgabenstellung ist wie folgt:

Wir wollen nach linearer Vorverarbeitung eines Baumes T , f�ur dessen Kno-tenmenge gilt: jV (T )j = n, eine lca{Anfrage f�ur beliebige x; y 2 V (T ) inkonstanter Zeit (unabh�angig von n!) beantworten. Wir betrachten zuerstvollst�andige bin�are B�aume.

6.1.1 lca{Anfragen in vollst�andigen bin�aren B�aumen

Sei B ein vollst�andiger bin�arer Baum mit p Bl�attern. Damit hat B (2p� 1)Knoten und die Tiefe d = log2 p.

Nun f�uhren wir darauf folgende Abbildung von V (B) in die Menge der (0; 1){Vektoren der L�ange (d+ 1) ein.

v 7! Wegzahl(v) = Position in der InOrderTreeWalk{Nummerierung

Zur Erinnerung: Die InOrder{Traversierung besucht zuerst rekursiv das linkeKind, dann den Elternknoten, dann rekursiv das rechte Kind.

F�ur einen (0,1){Vektor a nennen wir die Position der letzten Eins { vonhinten gez�ahlt { H�ohe h(a). Die so de�nierte H�ohe entspricht dann in einemvollst�andigen, bin�aren Baum der

"nat�urlichen\ H�ohe, d.h. die Bl�atter haben

die H�ohe 1, die dar�uberliegenden Knoten die H�ohe 2 . . . .

Beispiel.

2 = 010 6 = 110

4 = 100

7 = 1111 = 001 3 = 011 5 = 101

Beobachtung. Eine andere M�oglichkeit, die Wegzahl zu beschreiben, istdie folgende: Die Wegzahl eines Knotens v kodiert den Weg von der Wurzel

36

zu v. Geht der i{te Schritt auf dem Weg nach links, so wird die i{te Stelleder Bin�ardarstellung der Wegzahl (jetzt gez�ahlt von vorne) auf Null gesetzt.Geht der Schritt nach rechts, wird sie auf 1 gesetzt. Um auf d + 1 Bitszu kommen, wird zum Schluss mit einer 1 und so vielen Nullen wie n�otigaufgef�ullt. Beweis zur Korrektheit dieser Charakterisierung in der �Ubung.

Der lca(v1; v2) von zwei Knoten v1; v2 mit Wegzahl(v1) < Wegzahl(v2) istnun genau der Knoten, dessen Wegkodierung das l�angste Anfangsst�uck derWegkodierungen von v1 und v2 ist, das �ubereinstimmt. Zuerst wird derFall lca(v1; v2) 2 fv1; v2g behandelt. Dies kann man leicht mit Hilfe derdfs{Nummerierung der Knoten tun, siehe �Ubung. Ansonsten �ndet manlca(v1; v2) mit folgendem Algorithmus:

1. Bilde die XOR{Summe der beiden Wegzahlen.

2. Finde darin die linkeste 1, und nenne diese Position k.

3. lca(v1; v2) hat dann die Wegzahl v1(1)v1(2) : : : v1(k� 1), aufgef�ullt miteiner 1 und (d+ 1)� k Nullen.

Bemerkung. Die L�ange der Au��ullung entspricht genau der H�ohe desKnotens im Baum.

Beispiel.1. lca(5; 7) : 101 XOR 111 = 010: Dann ist k = 2 und Wegzahl(lca(5; 7)) =110 bzw. lca(5; 7) = 6.

2. lca(2; 5) : 010 XOR 101 = 111: Dann ist k = 1 und Wegzahl(lca(2; 5)) =100 bzw. lca(2; 5) = 4.

6.1.2 lca{Anfragen in allgemeinen B�aumen { Vorverarbeitung

F�ur allgemeine B�aume werden wir die lca{Anfrage an einen Baum T mit nKnoten in einen passenden Bin�arbaum B abbilden. Dazu f�uhren wir als ersteseine Tiefensuche bzw. DepthFirstSearch in T durch. Deren Nummerierung�ubernimmt man dann als Knotennamen in T .Zur Erinnerung: Die Tiefensuche besucht zuerst den Elternknoten, dannnacheinander rekursiv alle Kinder.

Zus�atzlich de�nieren wir folgende Abbildung I von der Menge der Knoten-namen f1; : : : ; ng in sich selbst. Sei v ein Knoten, dann suchen wir im Unter-baum mit Wurzel v den Knoten w, dessen h(w){Wert maximal ist. Hierbei

37

sei h wie im vorigen Abschnitt die L�ange der Au��ullung, also die Anzahl vonZeichen ab der rechtesten 1 nach rechts.

v 7! I(v) = w

Beispiel.

3 = 0011 4 = 0100 10 = 10109 = 1001

8 = 10007 = 0111

5 = 0101

2 = 0010

1 = 0001

6 = 0110

Abbildung 19: Hier ist I(1) = I(5) = I(8) = 8; I(2) = 4.

Beobachtung. Die Abbildung I zerlegt den Baum T in Teilb�aume mitdemselben I{Wert. Diese werden Runs genannt. Man kann sich �uberlegen,dass jeder Run ein Pfad in T ist. Der Knoten eines Runs, der am n�achstenan der Wurzel ist, wird Kopf genannt.

Es ist jedoch noch zu kl�aren, ob I �uberhaupt wohlde�niert ist. Das ist nurdann der Fall, wenn in jedem Teilbaum der Knoten mit dem maximalenh{Wert eindeutig ist. Dazu ein Lemma.

Lemma 4 Der Knoten I(v) = w aus der Abbildung I ist eindeutig.

Beweis. Wir nehmen an, es g�abe zwei verschiedene Knoten u 6= w miti := h(u) = h(w) � h(q) f�ur alle Knoten q im Unterbaum von v. D.h. uund w unterscheiden sich in einem Bit links von i. Sei k das kleinste dieserunterschiedlichen Bits und o.E. u > w.

u . . . 1

k

1 0 . . . 0

i

w . . . 0 1 0 . . . 0gleich

38

Konstruiere x = : : :k

1|{z}wie u

0 : : : 0.

Dann gilt u > x > w, und damit ist x die dfs{Nummer eines Knotens unterv, denn diese Nummern bilden ein Intervall. Aber h(x) > i = h(u)!Wider-spruch zur Annahme, dass i der gr�o�te h{Wert ist, der in diesem Unterbaumauftaucht. 2

Aus dem Lemma folgt, dass jeder Run in T auf einen Knoten in B abgebildetwird. Ein Run ist immer ein Aufw�artsweg, d.h., dass ein Run Teil eines Pfadesvon der Wurzel zu einem Knoten ist. Damit ist es m�oglich, die I(v) Wertebottom{up zu berechnen.

Die lineare Vorverarbeitung von T :

1. Tiefensuche auf T , jeder Knoten bekommt einen Pointer zum Eltern-knoten.

2. Bottom{up Berechnung der Werte I(v), jeder dieser Werte erh�alt einenPointer zum Kopf des entsprechenden Runs.

3. T auf B abbilden, v 7! I(v).

4. F�ur jedes v berechnen von Av. Dabei ist Av eine Bitzahl der L�angelogn, und das i{te Bit ist 1 () es existiert ein Vorfahre u von v mith(I(u)) = i.

6.1.3 Beantwortung der lca{Anfragen in konstanter Zeit

Lemma 5 Sei z echter Vorfahre von x in T , dann ist I(z) Vorfahre von I(x)in B. Das bedeutet, unter der Abbildung I bleiben die Verh�altnisse zwischenden Runs erhalten.

Beweis. Falls I(z) = I(x) ist, sind wir fertig. Andernfalls gilt wegen derDe�nition von I und h

i := h(I(z)) > h(I(x)):

Wir wollen zeigen, dass I(z) und I(x) in allen Bits links von i (die Bitswerden von rechts gez�ahlt) identisch sind. Angenommen, das sei nicht derFall. Dann sei k > i die linkeste Position mit einem Unterschied in I(z) undI(x) in Position k, und zwar sei diese Stelle o.B.d.A. 1 in I(z) und 0 in I(x),folglich I(z) > I(x).

39

Analog der Argumentation im Beweis von Lemma 4 folgt nun die Existenzeines Knoten v 2 T mit I(x) < v < I(z) und h(v) > h(I(z)). Das wider-spricht der De�nition von I, da v wegen der ersten Bedingung im Unterbaumvon z liegt, und h(I(z)) den maximalen h{Wert bezeichnet, der in diesemUnterbaum auftaucht.

Nach De�nition von i ist das Bit an Position i die rechteste 1 in I(z), undlinks von diesem Bit ist der Weg von der Wurzel nach I(z) in B kodiert. Dadie Bits links von i in I(x) und I(z) gleich sind folgt, dass der Weg von I(x)durch I(z) geht. Damit ist I(z) ein Vorfahre von I(x) in B. 2

Satz 7 Seien x, y Knoten und z = lca(x; y). Sei h(I(z)) gegeben, dann l�a�tsich z in konstanter Zeit bestimmen.

Beweis. Wir werden im folgenden die Knoten oft mit ihrer dfs{Nummeridenti�zieren. Zuerst eine kleine Beobachtung: Wir betrachten den Run, derz enth�alt. Die Wege von x bzw. y zur Wurzel m�ussen diesen Run tre�en.Wir nennen x0 bzw. y0 den Knoten, in dem diese Wege auf den Run von ztre�en. Dann erhalten wir aus der De�nition von lca, da� z gleich x0 oder y0

ist, und z = x0 () x0 < y0.

Nun berechnen wir x0 bzw. y0 aus h(I(z)). Sei dazu h(I(z)) =: j.

1. Fall: Sei h(I(x)) = j, dann ist x im Run von z und x0 = x.

x

y

w

Run von z

z

y0

x0

I(z)

2. Fall: Sei h(I(x)) < j bzw. x 6= x0. Sei w der letzte Knoten auf dem Wegvon x nach x0, der au�erhalb des Runs von z liegt. Aus h(I(z)) und demVektor Ax berechnen wir nun h(I(w)), I(w), w und x0. Es gilt:

40

h(I(w)) < j und h(I(w)) ist die gr�o�te Position k < j, so dass Ax eine 1 imBit k hat. Man hat somit w = x oder w ist ein echter Vorfahre von x, und imzugeordneten Bin�arbaum B ist I(w) = I(x) oder I(w) ist ein echter Vorfahrevon I(x), siehe Lemma 5. I(w) hat eine 1 an der Stelle k und { nach derWahl von k { Nullen rechts davon. w ist ein Vorfahre von x, und damit istI(w) in den Bits links von k identisch zu I(x). Wir kennen also I(w), fehltnoch w. w ist { nach Wahl { Kopf eines Runs, und alle Knoten eines Runszeigen auf dem Kopf, insbesondere I(w). x0 ist nun der Vater von w.

Analog kann y0 bestimmt werden, und mit unserer Beobachtung erhalten wirdamit z. 2

Nachdem wir nun z aus h(I(z)) bestimmen k�onnen, fehlt uns noch h(I(z)).Dazu der folgende Satz. Wir vergeben vorher noch ein paar Bezeichnungen:Sei b = lca(I(x); I(y)) im Bin�arbaum B, und h(b) =: i.

Satz 8 Sei j � i die kleinste Position, so da� Ax und Ay in diesem Bit eine1 haben. Dann ist h(I(z)) = j.

Beweis. Sei h(I(z)) =: k. Wir werden nun zeigen k � j und k � j.

k � j: z ist Vorfahre von x und y, also haben Ax und Ay in Position k eine1. Damit ist I(z) Vorfahre von I(x) und I(y), also k � i, und nach Wahlvon j gilt k � j � i.

k � j: Ax hat ein 1{Bit in Position j � i. Also gibt es einen Vorfahren x0 vonx in T , so dass gilt I(x0) ist Vorfahre von I(x) in B und h(I(x0)) = j. Analogerhalten wir einen Vorfahren y0 von y mit h(I(y0)) = j. Nun sind I(x0) undI(y0) Vorfahren von b, und somit ist I(y0) = I(x0). Damit sind beide imgleichen Run, und ohne Einschr�ankung sei x0 Vorfahre von y0. D.h. x0 wirdmindestens auf die H�ohe von z in B abgebildet, also j � k. 2

Nachdem wir die S�atze beisammen haben, folgt nun die Zeit der Ernte. Wirk�onnen den Algorithmus angeben und uns im Anschlu� seinen Anwendungenzuwenden.

Algorithmus

1. Finde b = lca(I(x); I(y)) in B.2. Finde kleinstes j � h(b) mit: Ax; Ay haben eine 1 in Bit j.

3. Setze h(I(z)) = j.

4. Finde x0, y0.

5. x0 < y0 ) z = x0, sonst z = y0.

41

6.2 Anwendung

In Abschnitt 5.1.3 haben wir uns mit dem Longest{Common{Substring vonK Strings S1; S2; : : : ; SK,

Pi jSij = n, besch�aftigt und einen Algorithmus

mit Laufzeit O(K � n) angegeben. Dieses Problem wollen wir jetzt in ZeitO(n) l�osen, dabei verwenden wir nat�urlich unseren neuen Algorithmus.

Erinnerung: Wir suchen f�ur 2 � k � K den l�angsten Teilstring, der in � kStrings vorkommt, dessen L�ange sei lk.

In dem gemeinsamen SuÆxbaum von S1; S2; : : : ; SK hat jeder String seineigenes Endsymbol. Wir wollen wie in 5.1.3 die Abbildung

v 7! C(v) = # Bl�atter verschiedener Strings unter v

einf�uhren, um danach v mit maximaler Tiefe und C(v) = k zu bestimmen.

Wie bestimmen wir C(v)? Dazu f�uhren wir folgende Bezeichnungen ein:

S(v) = # Bl�atter unter v;

ui(v) = # Bl�atter mit Stringnummer i unter v:

Dann ist sicher C(v) � S(v). Nun setzen wir

U(v) =X

i:ui(v)>1

(ui(v)� 1);

das hei�t U ist ein Korrekturfaktor der angibt, wie viele"Duplikate\ von

SuÆxen unter v vorkommen. Dann gilt C(v) = S(v)�U(v), und S l�a�t sichin linearer Zeit bestimmen.

Wir berechnen nun noch U(v) bzw. die Werte ui(v)� 1. Dazu erstellen wirmit Hilfe einer Tiefensuche die Listen L1; L2; : : : ; LK , wobei in Li die durchdie Tiefensuche geordneten Bl�atter mit Label i stehen.

Lemma 6 Wenn man f�ur alle benachbarten Paare in Li die lca{Anfragenberechnet, so landet man f�ur jedes v genau (ui(v) � 1) Mal im Unterbaumvon v.

Nun halten wir f�ur jedes w 2 T einen Z�ahler h(w), der z�ahlt, wie oft w alsErgebnis einer solchen lca-Anfrage auftritt. Dann bestimmen wir U bottom{up in linearer Zeit durch:

U(v) =X

w2 Unterbaum von v

h(w):

42

7 Approximatives Matching

Das im Folgenden vorgestellte Verfahren zum approximativen Matching be-ruht im wesentlichen auf dem Prinzip des dynamischen Programmierens.

7.1 Editierabstand, globales & lokales Alignment

Wir ber�ucksichtigen folgende Operationen, um einen String S1 in einen an-deren String S2 zu transformieren:

� I Insert

� D Delete

� R Replace

� M Match (keine Operation)

Beispiel.S1 : V I N T N E RS2 : W R I T E R SS1 ! S2 : R I M D M D M M I

De�nition 20 Wir nennen die minimale Anzahl von Operationen I, D, R,um einen String S1 in einen anderen String S2 zu transformieren, den Edi-tierabstand (auch Lewenshtein{Abstand), und schreiben daf�ur D(S1; S2).

De�nition 21 Ein globales Alignment von S1 und S2 entsteht durch Einf�ugenvon L�ucken (auch Spaces) in S1 und S2, so dass jeder Buchstabe einem Buch-staben oder Space gegen�uberliegt.

Beobachtung. Ein globales Alignment ist somit das Ergebnis einer Editier-transformationsprozesses.

Wir wollen nun D(S1; S2) bestimmen und verwenden dabei dynamischesProgrammieren. Sei jS1j = n und jS2j = m. Bezeichnen wir D(i; j) :=D(S1[1; i]; S2[1; j]), dann suchen wir D(n;m). S[1; 0] bezeichnet dabei denleeren String. Dazu folgender Satz:

43

Satz 9 Es gilt:

8i : D(i; 0) = i8j : D(0; j) = j

D(i; j) = minfD(i� 1; j) + 1; D(i; j � 1) + 1; D(i� 1; j � 1) + t(i; j)g;

wobei t(i; j) =

�1 : S1(i) 6= S2(j)0 : S1(i) = S2(j)

:

Beweis. (! �Ubung.)

Korollar 5 Der Editierabstand zwischen zwei Strings S1 und S2 kann bottom{up in Zeit O(n �m) berechnet werden.

Diese Rechnung f�uhrt zu einer n � m{Tabelle. Daraus kann man durchBacktracing eine Editierfolge gewinnen. Hierf�ur gilt:

Satz 10 Jeder Weg von (n;m) nach (0; 0) bestimmt eine optimale Transfor-mation (und ein Alignment) mit D(S1; S2) Operationen.

Man kann den Editierabstand verallgemeinern, indemman Gewichte einf�uhrt.Einerseits durch Gewichte auf den Operationen, andererseits durch zeichen-abh�angige Gewichte. Bei den Gewichten f�ur verschiedene Operationen solltegelten, dass ein Mismatch weniger wiegt als eine Folge von Delete und Insert.

Man kann den Editierabstand auch als graphentheoretisches Problem au�as-sen. Wir haben einen Editiergraphen mit (n+1)�(m+1) Knoten. Der Knoten(i; j) entspricht dabei dem Paar (S1[1; i]; S2[1; j]), die Kanten entsprechen denEditieroperationen. Um den Editierabstand D(S1; S2) zu bestimmen, suchenwir nach der L�ange eines k�urzesten Weges von (0; 0) nach (n;m).

(i; j) (i; j + 1)

1

1

(i + 1; j + 1)

t(i+ 1; j + 1)

(i+ 1; j)

44

7.2 �Ahnlichkeit von Strings

Sei � ein Alphabet von Zeichen, j�j = n, und �( ) := � [ f g.Nun wollen f�ur dieses Alphabet den Begri� �Ahnlichkeit einf�uhren, dazu gebenwir Matches positives Gewicht und Mismatches negatives Gewicht. Konkret:wir f�uhren eine Score{Abbildung auf dem kartesischen Produkt ein.

De�nition 22 Score sei eine Abbildung

s : �( ) � �( ) ! R:

Beobachtung. Ein Score kann man durch eine (n + 1) � (n + 1){Matrixfestlegen.

De�nition 23 Sei eine Scoringmatrix gegeben, S1; S2 Strings. Dann nen-nen wir die �Ahnlichkeit v von S1 und S2:

v(S1; S2) = max. Wert eines Alignments.

v(i; j) bezeichne die �Ahnlichkeit zwischen S1[1; i] und und S2[1; j]. Falls i = 0oder j = 0, so ist damit der leere String gemeint. Zur Berechnung k�onnenwir nun wie im Fall des Editierabstandes vorgehen:

v(0; j) =

jXk=1

s( ; S2(k))

v(i; 0) =iX

k=1

s(S1(k); )

v(i; j) = maxfv(i� 1; j) + s(S1(i); ); v(i; j � 1) + s( ; S2(j));v(i� 1; j � 1) + s(S1(i); S2(j))g:

Man ben�otigt O(n �m) Zeit f�ur die Erstellung der Tabelle und O(n+m) Zeitf�ur die Ausgabe eines optimalen globalen Alignments. �Ahnlichkeit l�a�t sichauch graphentheoretisch modellieren. Wir betrachten den selben Graphenwie oben, wobei jetzt die Kantengewichte durch s bestimmt werden. Gesuchtist nun ein maximaler Weg von (0; 0) nach (n;m).

Beispiel. Wir wollen lcs(S1; S2), die l�angste gemeinsame Teilsequenz vonS1 und S2 , in unserer neu gelernten Sprache ausdr�ucken. Eine gemeinsameTeilsequenz wird durch je eine Teilfolge aus 1; : : : ; n bzw. 1; : : : ; m bestimmt.

45

WRITERS und VINTNER enthalten folgende gemeinsame Teilsequenzen:R, I, E, T, IT, IE, IR, TE, TR, ER, ITE, IER, TER, ITR, ITER.

Die l�angste gemeinsame Teilsequenz lcs(S1; S2) l�asst sich als optimales glo-bales Alignment bzgl. der Scoring{Matrix s in Zeit O(m � n) �nden. Dabeisei

s(Match) = 1 und s(Mismatch) = s(Space) = 0

Zum Vergleich: Das AuÆnden des l�angsten gemeinsamen Teilstrings ist inZeit O(m+ n) m�oglich.

Die end{space{free Variante berechnet nichts f�ur den Vergleich Buchsta-be gegen Space, wenn der Space vor oder nach dem String kommt. ZurModellierung werden einfach die Anfangsbedingungen beim Berechnen der�Ahnlichkeit angepasst. Sie lauten nun:

v(i; 0) = 0 = v(0; j) f�ur alle i; j:

Gesucht ist das Alignment, das den Wert in der letzten Zeile oder Spaltemaximiert.

7.3 Das local{Alignment{Problem

Seien 2 Strings S1; S2, mit jS1j = n; jS2j = m, gegeben. Gesucht sindTeilstrings �; �, die v(�; �) =: v� maximieren.

Das geht mit folgendem Verfahren: Wir de�nieren f�ur 1 � i � n, 1 � j � m

v(i; j) = maxfv(�; �) j � SuÆx von S1[1; i] und � SuÆx von S2[1; j]g:

�; � k�onnen dabei auch leer sein. Um v� zu bestimmen, haben wir denfolgenden Satz.

Satz 11 Mit der Notation von oben gilt:

v� = max fv(i; j) j 1 � i � n; 1 � j � mg:

Die v(i; j) lassen sich wie folgt bestimmen:

v(i; 0) = 0 = v(0; j) f�ur alle i; j:

v(i; j) = max f0; v(i; j � 1) + s( ; S2(j)); v(i� 1; j) + s(S1(i); );v(i� 1; j � 1) + s(S1(i); S2(j))g.

46

7.4 Gaps und Gap Weights

Unser Ziel ist es, die Verteilung an Spaces in einem Alignment beein ussenzu k�onnen. Dazu werden wir diese mit verschiedenen Gewichten ausstatten.

De�nition 24 Gegeben sei ein Alignment S 0 eines Strings S. Wir nenneneinen maximalen Teilstring, der nur aus Spaces besteht, Gap.

Je nach Zweckm�a�igkeit gibt es nun verschiedene M�oglichkeiten, Gaps zugewichten. Eine Auswahl:

� Konstantes Gap{Gewicht: Man w�ahle eine Konstante Wg > 0 alsGap{Strafe und maximiere den Ausdruck

Xi

s(S 01(i); S

02(i))�Wg � (#gaps);

wobei S 0i der String zu Si im Alignment ist, und 8x : s( ; x) = 0 =

s(x; ).

� AÆnes Gap{Gewicht ist wohl das am h�au�gsten benutzte. Man be-straft sowohl das Auftreten eines Gaps, als auch dessen L�ange, d.h. einGap wird mit Wg +Ws � jGapj bestraft. Zu maximieren ist jetzt also

Xi

s(S 01(i); S

02(i))�Wg � (#gaps)�Ws(#Spaces):

� Konvexes Gap{Gewicht: Wieder betraft man das Auftreten einesGaps mit Wg und dessen L�ange. Dabei wird im Unterschied zu vor-her die L�ange jetzt mit einer konvexen Funktion f (d.h. die zweiteAbleitung von f ist < 0) bestraft. Dadurch werden lange Gaps antei-lig weniger als kurze Gaps betraft. Insgesamt wird f�ur ein Gap alsoWg + f(jGapj) berechnet.

Laufzeiten: F�ur beliebige Gewichte O(nm2+n2m), f�ur aÆne bzw. konstanteGewichte O(nm) und f�ur konvexe Gewichte O(nm logm).

Beweis. Wir betrachten ein Alignment von S1[1; i] zu S2[1; j] mit dem WertV (i; j). Dann k�onnen 3 Typen von Alignments auftreten:

1. S1[1; i] endet im Alignment mit Gap, diesen Wert nennen wir E(i; j).

2. S2[1; j] endet im Alignment mit Gap, diesen Wert nennen wir F (i; j).

47

3. beide enden im Alignment ohne Gap, diesen Wert nennen wir G(i; j).

Es gilt nun: V (i; j) = maxfE(i; j); F (i; j); G(i; j)gG(i; j) = V (i� 1; j � 1) + s(S1(i); S2(j)),

E(i; j) = max0�k�j�1fV (i; k) + w(j � k)g,F (i; j) = max0�l�i�1fV (l; j) + w(i� l)g,wobei w ein beliebiges Gap{Gewicht ist. Dazu kommt die folgende Initiali-sierung:

V (i; 0) = F (i; 0) = �w(i), V (0; j) = E(0; j) = �w(j), V (0; 0) = G(0; 0) =w(0) = 0, G(i; j) ist nicht de�niert f�ur i = 0 und j 6= 0 oder i 6= 0 und j = 0.

F�ur allgemeine Gap{Gewichte erh�alt man damit Laufzeit O(nm2 + n2m).Das sieht man wie folgt: Betrachte V (i; j), man ben�otigt in einer Zeile � m2

mal Eintr�age f�ur die E{Werte und in einer Spalte � n2 mal Eintr�age f�ur dieF{Werte.

Zeitschranken f�ur die anderen Gewichte zur �Ubung. 2

7.5 Verbesserung der dynamischen Programmierung

7.5.1 Linearer Speicherbedarf

Sei S1 = n, S2 = m. Dann bekommen wir mit dem Ansatz aus Kapitel 7.1in O(n �m) Zeit und mit O(n �m) Speicher ein optimales Alignment von S1

und S2. In diesem Abschnitt wollen wir den Speicherbedarf auf O(n + m)beschr�anken, um ein optimales Alignment zu �nden. Bisher k�onnen wir denWert des Editierabstandes mit diesem Speicherplatz bestimmen, nicht jedochden Alignment{Weg | f�ur diesen haben wir die ganze Matrix gebraucht.

Idee: Teile und herrsche & Rekursion.

(n:m)

m

n2

48

Der Ansatz ist folgenderma�en: Wir berechnen, wo der Alignment{Weg dien=2{te Zeile kreuzt. Au�erdem benutzen wir, dass wir mit einem optimalenAlignment f�ur S1; S2 auch ein optimales Alignment f�ur die Strings Srev

1 ; Srev2

kennen. Wir lesen dazu das optimale Alignment von hinten.

Lemma 7 Sei V rev(n=2; m�k) die �Ahnlichkeit von Srev1 [1; n=2] und Srev

2 [1; k]bzw. die �Ahnlichkeit von S1[n=2+ 1; n] und S2[m� k+1; m]. Mit dieser No-tation gilt nun:

V (n;m) = max0�k�m

fV (n=2; k) + V rev(n=2; m� k)g

Es sei k� ein Spaltenindex, der den maximalen Wert f�ur V (n;m) liefert.Dieses Lemma erlaubt es dann, ein optimales Alignment in zwei Schrittenzu bestimmen: Zuerst ein optimales Alignment von S1[1; n=2] mit S2[1; k

�],dann ein optimales Alignment von S1[n=2 + 1; n] und S2[k

� + 1; m]. Dabeiwird letzteres �uber die

"umgedrehten\ Strings berechnet.

Es gibt nun einen optimalen Alignment{Weg L, der durch den Knoten (n=2; k�)im Alignment{Graphen geht. Ln=2 sei der Teil des Weges L, der durch Kno-ten in Zeile n=2 verl�auft, und der letzte Knoten vor sowie der erste Knotennach diesem St�uck. Die wichtige Beobachtung hier ist: Ln=2 ist Teil einesoptimalen Alignments.

n2

n

n2+ 1

k1 k�

k2

Ln=2

n2� 1

Fakt: Wir �nden k� und Ln=2 in O(n �m) Zeit und O(m) Speicher.

49

Damit kommen wir zu folgender Analyse:

F�ur Eingabe{Gr�o�en p und q wird zum f�ullen der Tabelle mit dynamischemProgrammieren c�p�q Zeit ben�otigt, c eine gewisse Konstante. Mit der Unter-teilung in zwei Mal n=2 Zeilen ergibt sich eine Zeit von c�n=2�m+c�n=2�m =c � n � m f�ur die ganze Tabelle, insbesondere also die Zeilen, die gebrauchtwerden. Jedoch wird dabei mehr gelernt als nur die Tabelle: Die Wertek�; k1; k2 sowie das Pfadst�uck Ln=2 sind nach dieser Zeit bekannt. In die-sem Schritt wird also nicht nur der Wert v(n;m) berechnet, sondern auchein Teilst�uck des optimalen Alignments, n�amlich Ln=2. Die Aufgabe ist jetztdarauf reduziert, optimale Alignments f�ur die in der Abbildung grau gekenn-zeichneten St�ucke zu �nden, d.h. optimale Alignments zwischen S1[1; n=2�1]und S2[1; k1] sowie S1[n=2 + 1] und S2[k2; m]. Damit wird das Problem inzwei disjunkte Teilprobleme der Gr�o�en n=2 � k� und n=2 � (m � k�) zer-legt, welche mit Rekursion gel�ost werden k�onnen. Die Laufzeit daf�ur istc � n=2 � k� + c � n=2 � (m� k�) = c � n �m=2.Insgesamt ergibt sich mit diesem Verfahren eine Laufzeit von

log nXi=1

cnm

2i�1� 2cnm:

Bemerkung. Auf analoge Weise l�a�t sich ein optimales lokales Alignmentmit linearem Speicher bestimmen, Details in der �Ubung.

7.5.2 k{di�erence Alignment/Matching

Wir wollen nun die Anzahl der Unterschiede im Alignment begrenzen.

Variante 1: k{di�erence global Alignment

Dazu sind zwei Strings S1, S2 der L�ange n bzw. m gegeben, gesucht ist dasbeste globale Alignment mit � k Mismatches und Spaces.

Idee: Gehen wir im Alignment{Graph nach rechts oder nach unten (nichtdiagonal), so entspricht dies einem Space in S1 bzw. S2. Um nun ein k{di�erence global Alignment zu �nden, m�ussen wir somit nur den Streifender Breite 2k um die Hauptdiagonale (i; i) betrachten. F�ur ein k{di�erenceglobal Alignment mu� insbesondere gelten: jm � nj � k. Es m�ussen alsonur O(km) Matrixeintr�age berechnet werden. Angenommen ein maxima-les globales Alignment macht k� � k Fehler, dann m�ussten nur O(k� � m)Matrixeintr�age f�ur die Bestimmung von k� berechnet werden. Dies erreichtman, indem man die Streifenbreite von 2 aus beginnend immer verdoppelt.

50

k

k

(0; 0)

(n;m)

m

Hauptdiagonale

Eintrag braucht man nicht,da schon > k Fehler

Nach dem Ausf�ullen eines Streifens wird jeweils getestet, ob der Eintrag in(n;m) h�ochstens die aktuelle Streifenbreite ist. Sei dies bei Breite k0 daserste Mal der Fall. Dann ist k0 � 2k�, und k� steht in (n;m). Insgesamt wirdO(m+ 2m+ 4m+ : : :+ k0m) = O(k� �m) Zeit ben�otigt.

Variante 2: k{di�erence inexact Matching (Landau,Vishkin)

Sei P ein Pattern und T ein Text mit L�ange n bzw. m. Nun suchen wir alleMatches von P in T mit � k Fehlern.

Mit einem Hybridalgorithmus bestehend aus dynamischen Programmierenund SuÆxb�aumen l�a�t sich eine Laufzeit von O(km) erreichen. Zur Erin-nerung: Insertions, Deletions und Mismatches werden mit 1 gewichtet, zurInitialisierung werden alle Eintr�age in Zeile 0 auf Null gesetzt.

De�nition 25 Wir nennen einen Weg �, der in Zeile O des Alignment-graphen beginnt und genau d Fehler macht, einen d{Weg. So einen d{Wegnennen wir i{tiefsten Weg, wenn er auf der Diagonalen i endet und unterallen d{Wegen, die auf dieser Diagonalen enden, den tiefsten Endpunkt hat.

Nummerierung der Diagonalen

�1�2

�n

m1 20

51

Beobachtung. Jeder d{Weg, der die Zeile n erreicht, entspricht einem Mat-ching mit d Fehlern.

Unser Ziel ist es somit, alle d{Wege mit d � k zu �nden, die die n{te Zeileerreichen.

Algorithmus:

1. Der SuÆxbaum f�ur T und P und die Vorverarbeitung f�ur lce{Anfragenwerden in Zeit O(n+m) berechnet.

2. Iteriere f�ur 0 � d � k.

F�ur �n � i � m konstruiere den i{tiefsten d{Weg aus gewissen schonbekannten (d� 1){Wegen in O(n+m) Zeit f�ur jedes d. Genauer:

d = 0: Man �ndet die i{tiefsten 0{Wege durch lce{Anfragen von einemBlatt mit Label P und Bl�attern mit Label T [i;m]; i = 0; : : : ; m.

Jede lce{Anfrage kann in konstanter Zeit beantwortet werden,d.h. die i{tiefsten 0{Wege werden in Zeit O(m) gefunden.

d > 0: F�ur den i{tiefsten Weg, �n � i � m, tritt einer der folgendendrei F�alle auf:

(a) Der Weg besteht aus einem (i+ 1){tiefsten (d� 1){Weg, ge-folgt von einer vertikalen Kante zur Diagonalen i und deml�angstm�oglichen St�uck entlang der Diagonalen i. In anderenWorten: Nach d � 1 Fehlern be�nden wir uns auf der Dia-gonalen (i + 1) und sind dort maximal tief. Dann geschiehtder d{te Fehler, und damit landen wir auf der Diagonalen i.Durch eine lce{Anfrage f�ur P [k; n] und T [l; m] im SuÆxbaumerhalten wir den Knoten vor dem n�achsten Mismatch.

i� 1 i i + 1

(d� 1) Fehler

(i+ 1) tiefst Mismatch

d{ter Fehler

(l; k)

52

(b) Der Weg besteht aus einem (i�1){tiefsten (d�1){Weg, einerhorizontalen Kante zur Diagonalen i und dem l�angstm�oglichenMatch entlang der Diagonalen i.

(c) Der Weg besteht aus einem i{tiefsten (d� 1){Weg, einer dia-gonalen Kante und dem l�angstm�oglichen Match entlang derDiagonalen i.

7.6 SuÆxb�aume und gewichtete Alignments

Sei wie immer P ein Pattern und T ein Text der L�ange n bzw. m, au�erdemsei eine Scoring{Matrix gegeben. Dann interessieren wir uns f�ur folgendezwei Probleme.

1. P{against{all: Berechne die gewichteten Editierabst�ande zu allen Teil-strings T 0 von T .

2. All-against{all: Finde zu einem Schwellwert d alle Teilstrings P 0 � Pund T 0 � T mit Editierabstand � d.

In den zwei folgenden Abschnitten wird die L�osung dieser beiden Problemeerl�autert.

7.6.1 P{against{all

Der naive Ansatz f�uhrt zu folgender �Uberlegung: Es gibt � m2 viele Sub-strings von T , d. h. wir m�ussen � m2 Editierabst�ande der Form D(P; T 0)berechnen. Wir haben somit eine Gesamtlaufzeit O(nm3).

Gl�ucklicher weise geht es besser: Wir betrachten die m SuÆzes von T undberechnen dann D(T [i;m]; P ), f�ur 1 � i � m. Dabei berechnen wir alleanderen Abst�ande mit, der Abstand von P und T [i; j] steht in Zelle (n; j �i+ 1). So wird eine Laufzeit von O(nm2) erreicht.

T [i;m]

O(nm)P

in der letzten Zeile stehendie Editierabst�ande zu

von T [i;m]allen Anfangsst�ucken

53

Das ist schon sehr sch�on, jedoch: Es geht sogar noch besser! Bisher berechnenwir Abst�ande immer noch mehrfach f�ur den Fall, da� in T Wiederholungenvorkommen. Der neue Ansatz ist: Wir sortieren die SuÆzes im SuÆxbaumvon T mit einer dfs{Suche, und f�ullen die Tabelle spaltenweise mit dynami-schem Programmieren bez�uglich der neuen SuÆx{Sortierung. Dadurch wirdMehrfachberechnung vermieden. Seien also T 0 und T 00 SuÆzes von T , undau�erdem T 0 = AB und T 00 = AC. Dann gibt es, wie im Bild, einen Knotenv mit Label A. In den Tabellen von P gegen T 0 und P gegen T 00 sind dieersten jAj Spalten identisch. Nun speichern wir im Knoten v einfach dieentsprechende letzte Zeile und Spalte der Tabelle, so dass wir f�ur die Berech-nung der Editierabst�ande zu weiteren SuÆzes, die mit A beginnen, an dieserStelle in der Tabelle ansetzen k�onnen.

A

BCv

A B

Dabei wird nun das Label jeder Kante von T nur ein Mal mit P verglichen,um alle Eintr�age zu bestimmen, wird also O(n � (L�ange von T )) Zeit ge-braucht. Au�erdem muss in jeden inneren Knoten von T als Zwischenergeb-niss eine Spalte der L�ange n und eine Zeile der L�ange � m geschrieben wer-den. Das f�uhrt zu einer Gesamtlaufzeit von O(n�(L�ange von T )+m(n+m)),der Speicherbedarf betr�agt O(m2).

Bemerkung. Durch verdoppeln der Rechenzeit kann der Speicherplatzbe-darf auf O(m+ n) reduziert werden, Details in der �Ubung.

7.6.2 All-against{all

Zuerst ein Mal ist zu bemerken, dass bei dieser Problemstellung allein dieAusgabe eine Gr�o�e von O(n2m2) hat. Um diese Zeitschranke einzuhalten,kann man es sich sehr leicht machen: F�ur jedes der mn Paare von Startpo-sitionen (i; j) in P bzw. T berechne die Tabelle f�ur den Abstand von P [i; n]und T [j;m] in O(mn) Zeit. In der Zelle (k; l) einer solchen Tabelle stehtwieder der Abstand von T [i; l] und P [j; k].

54

Oft braucht man jedoch gar nicht wirklich alle Abst�ande, sondern nur einengewissen Teil davon. Damit wird m�oglicherweise die Ausgabegr�o�e entschei-dend kleiner. In diesem Fall helfen wieder SuÆxb�aume, um die Rechenzeitverglichen mit der naiven Methode deutlich zu senken.

Es sei nun TP der SuÆxbaum von P und TT der SuÆxbaum von T . Weitersei u ein Knoten aus TP und v ein Knoten aus TT . Dem Paar (u; v) wird die(dynamische{Programmier{) Tabelle vom Vergleich zwischen Label(u) undLabel(v) zugeordnet. Mit u0; v0 werden die Elternknoten von u; v bezeichnet,und es seien � = Label(u0; u); � = Label(v0; v).

�

v0

Randbekannt

u0

u

� v

Wenn die Tabellen f�ur (u0; v0); (u; v0); (u0; v) bekannt sind, m�ussen f�ur dieTabelle (u; v) nur noch j�j � j�j Eintr�age berechnet werden.Nun sortieren wir die Paare (u; v) lexikographisch nach aufsteigenden String-l�angen, und berechnen in dieser Reihenfolge die Tabellen unter Ausnutzungdes eben beschriebenen Tricks. Damit kommen wir zu einem Gesamtaufwandvon O(( L�ange von TP ) � ( L�ange von TT ) + Ausgabegr�o�e ).

7.7 Ausschlu�verfahren

Wir wollen nun mit einem anderen Zugang die bisherigen Laufzeit von O(km)f�ur die Probleme k{Mismatch und k{Di�erence verbessern. Wir gehen dabeinach folgenden Ausschlu�prinzip vor: Das Pattern wird zerkleinert. Wenndie kleinen St�ucke im Text nicht vorkommen, kann auch das ganze Patternnicht erscheinen.

Das Ziel ist es dabei, eine erwartete sublineare Laufzeit zu erreichen. Der hiervorgestellte Ansatz folgt einer Idee von Baeza{Yates und Perleberg, 1992.

55

Gegeben sind P und T wie immer, gesucht sind Matches zwischen P und Tmit maximal k Fehlern. Dazu zerlegen wir P in St�ucke der L�ange b n

k+1c =: r.

Beobachtung. Falls P den Teilstring T 0 � T mit � k Fehlern matcht, dannenth�alt P ein St�uck der L�ange r, das ein St�uck der L�ange r in T ohne Fehlermatcht.

Algorithmus:

1. Sei P die Menge der ersten k + 1 St�ucke von P (i.A. (k + 1) 6 j m).

2. Finde alle exakten Matches in T von allen p 2 P, z.B. mit dem Algo-rithmus von Aho{Corasick.

3. F�ur alle diese Matches: Sei i die Position des Matches in T , dann sucheapproximatives Match von P in T [i� k � n; i+ k + n].

Analyse f�ur Schritt 3: Sei � ein Alphabet mit j�j = �, und seien T und Pbeliebige Strings �uber �. Sei p ein beliebiges, festes St�uck von P der L�angejpj = r. Dann gilt f�ur den Erwartungswert:

E(# exaktes Match von p) � m�r

,

E(# exaktes Match irgendeines St�uckes p) � (k + 1) � m�r

,

E(Zeit f�ur Schritt 3) � m � n2 � k+1�r

.

Das Ziel ist es, Schritt 3 in weniger als c �m Zeit durchzuf�uhren. Die Frageist nun also, wie die Konstante k gew�ahlt werden mu�, damit

m � n2 � k + 1

�r< cm

ist f�ur ein gewisses c. Zur Vereinfachung der Rechnung setze k = n� 1 undbestimme r, so dass gilt

mn3

�r= cm :

Das gilt f�ur r = log� n3 � log� c, gleichzeitig war jedoch auch r = b n

k+1c.

Damit ergibt sich f�ur k 2 O(n=(logn)) eine Laufzeit von O(m) f�ur den obigenAlgorithmus.

In anderen Worten: F�ur eine Fehlerrate kleiner als 1=(log� n) l�auft der Algo-rithmus mit in m linearer Laufzeit.

56

7.7.1 Verbesserung: Mehrfach�lter f�ur k{Mismatches

Die Idee zu folgendem Verfahren mit erwarteter sublinearer Laufzeit stammtvon G. Myers, 1994. Die Verbesserung gegen�uber der vorherigen Methodeberuht darauf, dass gr�o�ere St�ucke von T , in denen kein k{Mismatch mit Pauftreten kann, ausgeschlossen werden.

De�nition 26 Sei die Fehlerrate 0 � " < 1 vorgegeben. Dann nennen wirS einen "{Match von T , wenn h�ochstens "jSj Fehler vorkommen.

Algorithmus

1. Partitioniere P in St�ucke der L�ange log�m.

2. Finde alle "{Matches der St�ucke in T .

3. Iterativ: Versuche, die L�ange der "{Matches bis zum "{Match von Pzu verdoppeln. St�ucke, bei denen das nicht gelingt, scheiden aus. Esfallen O(log n

log�m) Iterationen an.

Den Schl�ussel f�ur die Laufzeitabsch�atzung des Algorithmus liefert das folgen-de Lemma.

Lemma 8 Es sei � ein String mit der Zerlegung � = �0�1; j�0j = j�1j, und� ein String. Dann gilt: Falls � "{matches �, dann kann � zerlegt werdenin � = �0�1 mit �0 "{matches �0 oder �1 "{matches �1.

Damit kann man zeigen, dass die erwartete Gesamtlaufzeit des AlgorithmusO(kmp(") logm) ist.

7.8 Ein kombinatorischer Algorithmus f�ur lcs

Nachdem wir die longest common Subsequence zweier Strings S1; S2 schoneinmal in Kapitel 7.2 mit Hilfe eines gewichteten Alignment{Problems inO(jS1j � jS2j) Zeit gel�ost haben, werden wir nun kombinatorische Methodenverwenden. Wir reduzieren das Problem auf ein anderes, n�amlich longestincreasing Subsequence (lis). Dabei haben wir eine Folge � von n Zahlengegeben, und suchen eine l�angste monoton steigende Teilfolge bzw. derenL�ange.

Bemerkung. Wir nennen eine Teilfolge aufsteigend bzw. fallend, wenn siestreng monoton wachsend bzw. schwach monoton fallend ist. Eine Menge

57

von fallenden Teilfolgen, in der jede Zahl von � vorkommt, nennen wir eine�Uberdeckung. Eine �Uberdeckung nennen wir minimal, wenn sie aus einerminimalen Anzahl von Teilfolgen besteht.

Es gilt: Ist U eine minimale �Uberdeckung, dann folgt jU j = lis.

Nun wollen wir einen Greedy{Algorithmus mit Laufzeit O(n logn) f�ur daslis{Problem angeben:

Fange beim Einf�ugen der Zahlen links an. F�uge die Zahl am unteren Endedes ersten Stapels ein, dessen unterste Zahl gr�o�er als die Zahl selber ist.Falls es keinen solchen Stapel gibt, beginne mit einem neuen Stapel.

Beispiel. Sei � = f5; 3; 4; 9; 6; 2; 1; 8; 7; 10g

5321

4 9 8 106 7

eingef�ugt werden.die Folge 1, 4, 6, 7, 10Ein neues Element m�usste in

Da die kleinsten Elemente der fallenden Folgen aufsteigend angeordnet sind,geht das Einf�ugen mittels bin�arer Suche in O(n logn) Zeit.

Beobachtung. Es existiert eine lis mit je einem Element aus jeder fallendenFolge der �Uberdeckung, diese �nden wir in O(n) Zeit.

Wenn man alle Stapel"nebeneinanderstellt\ sieht man, dass es eine aufstei-

gende oder fallende Folge der L�ange mindestenspn in � gibt.

Die Reduktion geht nun folgenderma�en: Sei jS1j = m; jS2j = n; n � m,und � ein Alphabet. Dann de�nieren wir:

r(i) = # Vorkommen des i{ten Zeichens von S1 in S2;

und r =P

i r(i), 0 � r � mn.

Damit bekommen wir lcs in O(r logn) Zeit wie folgt:

1. F�ur jedes x in S1 bestimme die fallende Liste der Positionen von x inS2.

2. Es sei �(S1; S2) := S1, wobei jedes Zeichen durch die entsprechendeListe aus dem ersten Schritt ersetzt ist.

58

Beobachtung. Jede aufsteigende Folge in �(S1; S2) de�niert eine gemein-same Teilsequenz und umgekehrt.

Beispiel. S1 = abacx, S2 = baabca.

Schritt 1: a 7! 6; 3; 2, b 7! 4; 1, c 7! 5Schritt 2: �(S1; S2) = 6; 3; 2; 4; 1; 6; 3; 2; 5

Die Folge 2,3,5 in �(S1; S2) entspricht der gemeinsamen Teilsequenz aac, 3,4,6geh�ort zu abc.

59

Date post:	14-Aug-2019
Category:	Documents
Upload:	ngokien
View:	217 times
Download:	0 times

String - inf.fu-berlin.de · String Matc hing Algorithmen Skript v on Stephan Hell zur V orlesung F...

Documents