Post on 05-Apr-2015
transcript
Konstruktion von Suffixarrays inlinearer ZeitVortrag im Seminar
„Mehr Algorithmische Bioinformatik“
von Marek Karadžić
SS 2005
Leiter: Prof. Dr. Ulf Leser und Dipl.-Inf. Jörg Hakenberg
Suffixarrays in linearer Zeit 206.07.2005
Überblick
Kurze Wiederholung Suffixtrees und –arrays Algorithmus von Manber und Myers
Beispiel Komplexität
Skew-Algorithmus Beispiel Komplexität
Suffixarrays in linearer Zeit 306.07.2005
Zur Erinnerung.. Suffixtrees
Exaktes Stringmatching für ein Template und viele Pattern T möglichst clever vorverarbeiten Gut für Datenbankanfragen
Naive Konstruktion von Suffixtrees in O(m²); mit Ukkonen in O(m) Schwierigkeiten:
Konstruktion schlecht auf Sekundärspeichern (Lokalität) Naive Konstruktion zu langsam Ukkonen ist speicherintensiv; aber typische Anwendungen
arbeiten im Hauptspeicher Abhilfe: Suffixarrays
Suffixarrays in linearer Zeit 406.07.2005
Suffixarrays
Für einen String s ist A ein Integerarray der Länge |s|,wobei A[i] die Startposition des i-ten, lexikographischsortierten Suffix von s enthält.
Konstruktion aus Suffixtrees in O(m) mit Depth-First-Search
Beispiel:A[1] = 9 $A[2] = 4 AKIRI$A[3] = 2 ARAKIRI$A[4] = 1 HARAKIRI$A[5] = 8 I$A[6] = 6 IRI$A[7] = 5 KIRI$A[8] = 3 RAKIRI$A[9] = 7 RI$
123456789s = HARAKIRI$
Suffixarrays in linearer Zeit 506.07.2005
Algorithmus von Manber und Myers
Suffixarrays in linearer Zeit 606.07.2005
Der Algorithmus
Gegeben ein String s und leeres Array A Array mit allen Suffixen von s, der Länge nach
absteigend, initialisieren: A[i] = n +1 – i für i = 0..n Mit Bucket-Sort nach dem ersten Zeichen sortieren Sortieren nach den nächsten Zeichen:
si = si … sn$ und sj = sj … sn$ sind zwei Wörter eines Buckets Für das zweite Zeichen: si+1 mit sj+1 vergleichen Danach werden das dritte und vierte Zeichen verglichen, also
si+2si+3 mit sj+2sj+3 Die Anzahl der Zeichen, nach denen „verglichen wird“,
verdoppelt sich in jedem Schritt: 1, 2, 4, 8, 16, … Folgen Suffixe aufeinander, aufgrund von Suffixen aus
verschiedenen Buckets, entsteht eine neue Bucketgrenze Wir sind fertig, wenn jedes Suffix in einem eigenen
Bucket ist
Suffixarrays in linearer Zeit 706.07.2005
Der Trick
Der Vergleich wurde schon implizit im vorherigen Schritt gemacht Für das zweite Zeichen ist es dasselbe Ergebnis wie das beim
Vergleich von si+1 = si+1 … sn$ mit sj+1 = sj+1 … sn$, also: In jedem Bucket wird si, nach der Sortierung von si+1 nach dem ersten
Zeichen, angeordnet Dafür gehen wir durch das mit Bucket-Sort sortierte Array und schieben
den Index j -1, wenn A[i] = j ist, an den Anfang in seinem Bucket Für das dritte und vierte Zeichen ist es dasselbe Ergebnis wie das
beim Vergleich von si+2 = si+2 … sn$ mit sj+2 = sj+2 … sn$, also: In jedem Bucket wird si, nach der Sortierung von si+2 nach den ersten
beiden Zeichen, angeordnet Dafür gehen wir durch das im vorherigen Schritt sortierte Array und
schieben den Index j -2, wenn A[i] = j ist, an den Anfang in seinem Bucket
Suffixarrays in linearer Zeit 806.07.2005
Beispiel
Array mit allen Suffixen von s in absteigender Reihenfolge initialisieren: A[i] = n +1 – i für i = 0..n
s = MISSISSIPPI$ A[0] = 1 MISSISSIPPI$A[1] = 2 ISSISSIPPI$ A[2] = 3 SSISSIPPI$ A[3] = 4 SISSIPPI$ A[4] = 5 ISSIPPI$ A[5] = 6 SSIPPI$ A[6] = 7 SIPPI$ A[7] = 8 IPPI$ A[8] = 9 PPI$A[9] = 10 PI$A[10] = 11 I$A[11] = 12 $
Suffixarrays in linearer Zeit 906.07.2005
Beispiel II
Mit Bucket-Sort nach dem ersten Zeichen sortieren
$ I M P S
A 12 2 5 8 11 1 9 10 3 4 6 7
123456789012MISSISSIPPI$$ $
I
ISSISSIPPI$ISSIPPI$IPPI$I$
M MISSISSIPPI$
PPPI$PI$
S
SSISSIPPI$SISSIPPI$SSIPPI$SIPPI$
Suffixarrays in linearer Zeit 1006.07.2005
Beispiel III A 012
1 2 3 4 2 5 8 11
51
6 79 10
8 9 10 113 4 6 7
122581119103467
11
11 8
11 8 2
11 8 2 5
1
10
10 9
44 7
4 7 3
4 7 3 6
12 11 8 2 5 1 10 9 4 7 3 6
$ I I I I$ P S S P S S
MIS
P PI P$ I
S S S SI I S SS P I I
In jedem Bucket wird si, nach der Sortierung von si+1 nach dem ersten Zeichen, angeordnet.
Dafür gehen wir durch das mit Bucket-Sort sortierte Array und schieben den Index j -1, wenn A[i] = j ist, an den Anfang in seinem Bucket.
Folgen Suffixe aufeinander, aufgrund von Suffixen aus verschiedenen Buckets, entsteht eine neue Bucketgrenze.
Suffixarrays in linearer Zeit 1106.07.2005
Beispiel IV
In jedem Bucket wird si, nachder Sortierung von si+2 nachden ersten beiden Zeichen,Angeordnet.
Dafür gehen wir durch das imvorherigen Schritt sortierteArray und schieben den Index j -2, wenn A[i] = j ist, anden Anfang in seinem Bucket
A 012
111
28
3 42 5
51
610
79
8 94 7
10 113 6
121182511094736
8
22 5
1
109
7
7 4
6
6 3
12 11 8 2 5 1 10 9 7 4 6 3
$ I$
IPPI$
I IS SS SI IS P
MISSI
PI$
PPI$
S SI IP SP SI I
S SS SI IP SP S
Suffixarrays in linearer Zeit 1206.07.2005
Komplexität
Die Größe des Alphabets ist n, also gibt es höchstens n Buckets
Die Verdopplung der Anzahl der Zeichen nach denen sortiert wird, führt zu log(n)
Also hat der Algorithmus im schlimmsten Fall eine Laufzeit von O(n · log(n)) Im besten Fall nur O(n)! Worst case kann auf O(n · loglog(n)) reduziert werden
Suffixarrays in linearer Zeit 1306.07.2005
Skew-Algorithmus
Suffixarrays in linearer Zeit 1406.07.2005
Gut zu wissen
2003 von J. Kärkkäinen und P. Sanders vorgestellt
Erster Algorithmus der nur O(n) braucht Im selben Jahr wurden noch zwei weitere
Algorithmen zur linearen Konstruktion veröffentlicht P. Ko und A. Aluru D.K. Kim, J.S. Sim, H. Park, K. Park (?)
Suffixarrays in linearer Zeit 1506.07.2005
Der Algorithmus
0) String s = s0 · · · sn-1
1) s[n] = s[n + 1] = s[n + 2] = $; $ kommt in s nicht vor und ist kleinstes Zeichen im Alphabet
2) Tripel von s bilden (si · si+1 · si+2) mit Startposition i mod 3 ≠ 0
3) Tripel werden mit Radix Sort (lexikographisch) sortiert, Ergebnis in einem Array A12 speichern
4) Jedes Tripel erhält einen lexikographischen Namen. Dazu werden die sortierten Tripel in aufsteigender Reihenfolge durchnummeriert, wobei gleiche Tripel auch gleiche Nummern bekommen.
Suffixarrays in linearer Zeit 1606.07.2005
Der Algorithmus II
5) Wir erhalten eine neue Zeichenreihe s(1) bzw. s(2), indem wir für das Teilwort bzw. alle Tripel mit i mod 3 = 1 bzw. i mod 3 = 2 durch ihre Nummer ersetzen. Mit s(1) · s(2) erzeugen wir die Zeichenreihe s12.
6) Schritte 2 - 5 solange mit s12 · 0 rekursiv aufrufen, bis jedes Tripel einen eindeutigen lexikographischen Namen hat
7) Tripel mit i mod 3 = 0 mittels A12 anordnen (denn si+1 mit (i + 1) mod 3 = 1 ist uns bekannt) und mit Radix Sort nach s[i] sortieren; Ergebnis in A0 speichern
s1 s3 n 3
s2 s3 n 3 1
Suffixarrays in linearer Zeit 1706.07.2005
Der Algorithmus III
8) Mische A0 und A12, dabei gilt, wenn wir si mit sj mit i mod 3 = 0 undj mod 3 = [1, 2] vergleichen:
Fall 1: Ist j mod 3 = 1, dann gilt:
si = si · si+1, wobei (i + 1) mod 3 = 1sj = sj · sj+1, wobei (j + 1) mod 3 = 2Wir vergleichen si mit sj, bei Gleichheit Ergebnis aus A12 ablesen
Fall 2: Ist j mod 3 = 2, dann gilt:
si = si · si+1 · si+2, wobei (i + 2) mod 3 = 2sj = sj · sj+1 · sj+2, wobei (j + 2) mod 3 = 1Wir vergleichen si mit sj, bei Gleichheit auch si+1 mit sj+1. Sind beidegleich, lesen wir das Ergebnis wieder aus A12 ab
Suffixarrays in linearer Zeit 1806.07.2005
Beispiel
s = MISSISSIPPI
1) Dummy-Tripel dranhängen
s = MISSISSIPPI$$$
2) Tripel von s mit i mod 3 ≠ 0 bilden
11012345678901MISSISSIPPI$$$
i mod 3 = 1 i mod 3 = 2
ISS ISS IPP I$$ SSI SSI PPI $$$
POS 1 4 7 10 2 5 8 11
Suffixarrays in linearer Zeit 1906.07.2005
Beispiel II
3) Radix Sort
$ I P S
I$$$$$
PPIIPP
SSISSIISSISS
$ I P S
I$$$$$
SSISSIPPI
IPP ISSISS
Von: ISS ISS IPP I$$ SSI SSI PPI $$$
Ergebnis nach r.Z.:I$$, $$$, SSI, SSI,PPI, IPP, ISS, ISS
Ergebnis nach m.Z.:I$$, $$$, PPI, IPP,SSI, SSI, ISS, ISS
Sortieren nach r.Z.: Sortieren nach m.Z.:
Suffixarrays in linearer Zeit 2006.07.2005
Beispiel III
4) Lexikographische Namen (ψ)
$ I P S
$$$ I$$IPPISSISS
PPI SSISSI
Ergebnis nach l.Z.:$$$, I$$, IPP, ISS,ISS, PPI, SSI, SSI
i mod 3 = 1 i mod 3 = 2
ψ 1 2 3 4 4 5 6 6
$$$ I$$ IPP ISS ISS PPI SSI SSI
POS 11 10 7 1 4 8 2 5
Sortieren nach l.Z.:
Suffixarrays in linearer Zeit 2106.07.2005
Beispiel IV
5) s12 := s(1) · s(2)
6) Rekursiver Aufruf von s12 · 0 bis ψ eindeutig ist
Tripel i mod 3 ≠ 0 bilden:
44326651
POS = 012345678s12 = 443266510
i mod 3 = 1 i mod 3 = 2
432 665 100 326 651 000
POS 1 4 7 2 5 8
Suffixarrays in linearer Zeit 2206.07.2005
Beispiel V
6.1) Radix Sort..
7) Tripel mit i mod 3 = 0 sortieren
si+1 mit (i + 1) mod 3 = 1 ist uns durch A12 bekannt, s[i] mit Radix Sort
Ergebnis: 000, 100, 326, 432, 651, 665 (= A12)
POS = 012345678s12 = 443266510
Also: 443, 266, 510
Ergebnis: 266, 443, 510 (= A0)
Suffixarrays in linearer Zeit 2306.07.2005
Beispiel VI
8) Mischen von A0 und A12 mit Hilfe von A12
POS 10 1 8
266 443 510
11012345678901MISSISSIPPI$$$
POS 14 11 7 4 5 2
000 100 326 432 651 665
Ergebnis: 000,100,266,326,432,443,510,651,665(= A12)
Fall 1: Ist j mod 3 = 1, dann gilt:
si = si · si+1, wobei (i + 1) mod 3 = 1sj = sj · sj+1, wobei (j + 1) mod 3 = 2Wir vergleichen si mit sj, bei Gleichheit Ergebnis aus A12 ablesen
Fall 2: Ist j mod 3 = 2, dann gilt:
si = si · si+1 · si+2, wobei (i + 2) mod 3 = 2sj = sj · sj+1 · sj+2, wobei (j + 2) mod 3 = 1Wir vergleichen si mit sj, bei Gleichheit auch si+1 mit sj+1. Sind beide gleich, lesen wir das Ergebnis wieder aus A12 ab
Suffixarrays in linearer Zeit 2406.07.2005
Beispiel VII
8.1) Das Gleiche nochmal mit den Tripeln i mod 3 = 0 aus dem allerersten Schritt Sortieren mit Radix Sort und A12:
Mischen von A0 und A12:
11012345678901MISSISSIPPI$$$
Von: MIS, SIS, SIP, PI$Ergebnis: MIS, PI$, SIP, SIS (= A0)
100,266,326,432,443,510,651,665$$$ I$$ IPP ISS ISS PPI SSI SSI 11 10 7 4 1 8 5 2
MIS PI$ SIP SIS 0 9 6 3
Suffixarrays in linearer Zeit 2506.07.2005
Beispiel VIII
Resultat Suffixarray A:
A[0] = 11 $$$A[1] = 10 I$$A[2] = 7 IPP I$$A[3] = 4 ISS IPP I$$A[4] = 1 ISS ISS IPP I$$A[5] = 0 MIS SIS SIP PI$A[6] = 9 PI$A[7] = 8 PPI $$$A[8] = 6 SIP PI$A[9] = 3 SIS SIP PI$A[10] = 5 SSI PPI $$$A[11] = 2 SSI SSI PPI $$$
Suffixarrays in linearer Zeit 2606.07.2005
Komplexität
Für einen String der Länge n ruft sich der Algorithmus rekursiv mit 2/3 * n (Startpositionen mit i mod 3 ≠ 0) auf
Danach werden diese 2/3 * n mit den übrigen 1/3 * n Zeichen gemischt, das kostet O(n)
Dadurch ergibt sich die Rekursionsgleichung:
Da sich der erste Teil zu einer Konstante entwickelt, bleibt der Algorithmus letztendlich linear:T(n) = O(n)
T n T 2n3
O n
Suffixarrays in linearer Zeit 2706.07.2005
Quellen
Heun, Volker: Skript zur Vorlesung Algorithmen auf Sequenzen. Version 0.70 (03/2005)
Weese, David: Studienarbeit zur Implementierung des Skew-Algorithmus. (05/2005)
J. Kärkkäinen, P. Sanders: Simple Linear Work Suffix Array Construction. ICALP'03, Lecture Notes in Computer Science, Vol. 2719, 943-955. (2003)
Vielen Dank für die Aufmerksamkeit!