Das LCA – Problem in Suffixbäumen

K. Swist 2

Überblick

Definitionen Anwendungen Voraussetzungen Preprocessing Beantworten von LCA – Anfragen in

konstanter Zeit

K. Swist 3

Definitionen Ein Suffixbaum T für einen String S (|S| = n) ist ein Baum mit

n Blättern, markiert mit 1, …, n Kanten, beschriftet mit

nichtleeren Substrings von S innere Knoten haben

mind. 2 Kinder Alle Label der Kanten von

einem Knoten aus beginnenmit unterschiedlichen Zeichen.

Konkatenation der Label der Kanten auf einem Pfad von derWurzel zu einem Blatt i ist gleich S[i... n] (also das Suffix von S,das an Position i startet.).

1

banane

2 4

3

5

6

an

ane e

n

ane

e

e

K. Swist 4

Definitionen Ein Knoten u ist Vorfahre eines Knotens v, wenn u sich auf

dem Pfad von der Wurzel zu v befindet. Insbesondere ist jeder Knoten Vorfahre von sich selbst.

Ein echter Vorfahre von v ist ein Vorfahre, der nicht v selbst ist.

u

v

K. Swist 5

Definitionen

Der tiefste gemeinsame Vorfahre (lowest common ancestor, lca) zweier Knoten x und y ist der tiefste Knoten in T, der sowohl Vorfahre von x, als auch von y ist.

lca(x, y)

x y

K. Swist 6

Definitionen

Ein vollständiger binärer Baum B ist ein Baum, in dem jeder innere Knoten genau zwei Kinder hat.

K. Swist 7

Überblick

Definitionen Anwendungen Voraussetzungen Preprocessing Beantworten von lca – Anfragen in

konstanter Zeit

K. Swist 8

Anwendungen Longest common extension

gegeben zwei Strings S1 und S2finde zu beliebigen Indexpaaren (i, j) den längsten

Match von S1[i..] und S2[j..] Palindrome

gegeben ein String Sfinde alle maximalen Palindrome in S

Komplementäre Palindrome

K. Swist 9

Überblick

Definitionen

Anwendungen Voraussetzungen Preprocessing Beantworten von lca – Anfragen in

konstanter Zeit

K. Swist 10

Voraussetzungen für den Algorithmus Operationen in O(1) Zeit auf Zahlen der Länge

O(log n): lesen, schreiben, adressieren von Zahlenvergleichen, addieren, subtrahieren, multiplizieren,

dividieren von zwei ZahlenBitoperationen: AND, OR, XOR shift rechts, linksErzeugen einer Maske von aufeinander folgenden

EinsenFinden der am weitesten rechts oder links liegenden

Eins in einer Binärzahl

K. Swist 11

Überblick

Definitionen

Anwendungen

Voraussetzungen Preprocessing Beantworten von lca – Anfragen in

konstanter Zeit

K. Swist 12

Preprocessing – Umwandeln von T in einen vollständigen Binärbaum B Depth – first search numbers: Nummerieren

der Knoten eines Baumes T nach ihrem Auftreten bei der Tiefensuche:

5 6

4

3

2

1001

100

110101011

010

K. Swist 13

Preprocessing – h(v) Für jede Nummer v bezeichnet h(v) die

Position (von rechts) des ersten 1 – Bits in der Binärdarstellung von v.

5 6

4

3

2

1001

100

110101011

010

h(1) = 1

h(2) = 2

h(3) = 1

h(4) = 3

h(5) = 1

h(6) = 2

K. Swist 14

Preprocessing – I(v) Für einen Knoten v in T bezeichnet I(v) den

Knoten w in T, sodass h(w) maximal über alle Knoten im Unterbaum unter v ist.

5 6

4

3

2

1001

100

110101011

010

h(1) = 1 I(1) = 4

h(2) = 2 I(2) = 2

h(3) = 1 I(3) = 3

h(4) = 3 I(4) = 4

h(5) = 1 I(5) = 5

h(6) = 2 I(6) = 6

K. Swist 15

Preprocessing - Gruppen Eine Gruppe besteht jeweils aus allen Knoten, die den

gleichen I – Wert haben. Der Kopf einer Gruppe ist der Knoten, der am nächsten zur Wurzel liegt.

I(1) = 4

I(2) = 2

I(3) = 3

I(4) = 4

I(5) = 5

I(6) = 6

5 6

4

3

2

1001

100

110101011

010

K. Swist 16

Preprocessing

Sei B ein vollständiger binärer Baum mit Knotentiefe d = log2n – 1. (n = Anzahl der Knoten im Suffixbaum T)

Sei p die Anzahl der Blätter von B. Jeder Knoten v bekommt eine (log2p)+1 Bit

lange Pfadnummer, die eindeutig den Pfad von der Wurzel zu v angibt.

K. Swist 17

Preprocessing - Pfadnummern Von links gezählt bezieht sich das i – te Bit auf den

i – ten Knoten auf dem Pfad von der Wurzel zu v:

0 bedeutet Verzweigung nach links, 1 nach rechts

Jede Pfadnummer wirddann zu (log2p)+1 Bitsaufgefüllt, indem rechtseine Eins angehängt wirdund entsprechend viele Nullen.

1 7 5

6

4

2

3001

101

111

110

011

100

010

K. Swist 18

Preprocessing - Pfadnummern Pfadnummern können

auch rekursiv vergebenwerden: nummerierezuerst rekursiv das linkeKind, dann die Wurzel,dann rekursiv dasrechte Kind.

Bei der Konstruktion vonB werden nur die Knotenbezeichnet, auf die einKnoten aus T abgebildetwird (also nur die Nummern,die als I – Wert inT vorkommen).

1 7 5

6

4

2

3001

101

111

110

011

100

010

K. Swist 19

Preprocessing - Av Av ist eine O(log n) Bit lange Zahl, wobei

Bit Av(i) = 1 gdw. Knoten v hat einen Vorfahren in T, der auf Tiefe i in B abgebildet wird

d. h. v hat einen Vorfahren u, sodass h(I(u)) = i.

I(1) = 4 h(1) = 1 A1 = 001

I(2) = 2 h(2) = 2 A2 = 011

I(3) = 3 h(3) = 1 A3 = 111

I(4) = 4 h(4) = 3 A4 = 001

I(5) = 5 h(5) = 1 A5 = 101

I(6) = 6 h(6) = 2 A6 = 011

K. Swist 20

Preprocessing - AlgorithmusEingabe: ein Baum T mit n Knoten

1. Tiefensuche in T: Vergeben der depth – first search numbers Berechnen von h(v) für jeden Knoten v Setze für jeden Knoten einen Pointer auf seinen Vater

2. Bottom – up Algorithmus Berechne I(v) für jeden Knoten v Für jede Nummer k, sodass ein v existiert mit I(v) = k, setze L(k) als

Pointer auf den Kopf der Gruppe, die Knoten k enthält

3. Erzeuge den kompletten binären Baum B und bilde jeden Knoten v aus T auf den Knoten I(v) in B ab

4. Berechne Av für jeden Knoten v in T.

K. Swist 21

Preprocessing - Beispiel

h(1) = 1; I(1) = 4

h(2) = 2; I(2) = 2

h(3) = 1; I(3) = 3

h(4) = 3; I(4) = 4

h(5) = 1; I(5) = 5

h(6) = 2; I(6) = 6

001

5 6

4

3

2

1

100

110

101

011

010

5

6

4

2

3

101

110

011

100

010

Pointer auf den Vater

v I(v)

K. Swist 22

Überblick

Definitionen

Anwendungen

Voraussetzungen

Preprocessing Beantworten von lca – Anfragen in

konstanter Zeit

K. Swist 23

Beantworten von LCA - Anfragen

lca(i, j) in B: i und j sind Pfadnummern (binäre Darstellung; Länge d) Prüfen, ob i Vorfahre von j oder umgekehrt Sei xij = XOR(i, j). Finde Position k (von links gezählt) des

am weitesten links liegenden 1 – Bits in xij. Links von k stehen Nullen, also sind die Pfade von der

Wurzel bis zur k – ten Verzweigung gleich. Folglich besteht die Pfadnummer von lca(i, j) aus den

ersten (k – 1) Zeichen von i (oder j), einer Eins und dann d – k – 1 Nullen.

K. Swist 24

Beantworten von LCA - Anfragen

z.B. lca(5, 3): XOR(101, 011) = 110 k = 1 lca = 100

5

6

4

2

3

101

110

011

100

010

K. Swist 25

Beantworten von LCA – Anfragen - AlgorithmusEingabe: zwei Knoten x und y in T1. Finde b = lca(I(x), I(y)) in B.2. Finde die kleinste Position j h(b), sodass sowohl

Ax, als auch Ay an Position j eine Eins haben. j ist dann h(I(lca(x, y))).

3. Finde Knoten x‘, den am nächsten zu x gelegenen Knoten, der in der gleichen Gruppe wie lca(x, y) liegt wie folgt:

i. Finde Position l des am weitesten links liegenden Eins – Bits in Ax. (l = h(I(x)))

K. Swist 26

Beantworten von LCA – Anfragen - Algorithmus

ii. Wenn l = j, setze x‘ = x (x und lca(x, y) liegen in der gleichen Gruppe) und gehe zu Schritt 4.

iii. Sonst (l < j): Finde Position k des am weitesten links liegenden 1 – Bits in Ax, das noch rechts von j liegt.Entwickle eine Zahl w bestehend aus den Bits von I(x) links von Position k gefolgt von einer Eins, aufgefüllt mit Nullen. Suche Knoten L(w) und setze Knoten x‘ als Vater von L(w) in T.

4. Finde Knoten y‘, den am nächsten zu y liegenden Knoten aus der Gruppe von lca(x, y) wie in Schritt 3.

5. Wenn x‘ < y‘, setze lca(x, y) = x‘; sonst lca(x, y) = y‘.

Ausgabe: lca(x, y)