SuffixArray => SuffixBaum |
akvarel
Grünschnabel
Dabei seit: 11.02.2012
Beiträge: 1
|
|
SuffixArray => SuffixBaum |
|
Meine Frage:
Hallo!
Um einen Suffixbaum in einen Suffixarray umzuwandeln, muss man ja die Tiefen-Suche anwenden. Tiefen-Suche braucht O(|E|+|V|) Zeit. E-Kanten,V-Knoten.
Warum dann finde ich immer im Internet, dass die Laufzeit um einen SB in einen SA umzuwandeln mittels DFS nur O(|V|) beträgt? Übrigens, das hat auch mein Tutor gesagt.
Meine Ideen:
Darf man Kanten also einfach weglassen?
|
|
11.02.2012 23:05 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
RE: SuffixArray => SuffixBaum |
|
Hi,
die Laufzeitabschätzung, dass die Tierfensuche durch begrenzt ist, gilt für allgemeine Graphen. Hier Können Mehrfachkanten auftreten und diese müssen auch untersucht werden. Weiterhin gilt es wohl auch noch Hypergraphen zu betrachten. S. http://de.wikipedia.org/wiki/Diskussion:...BCr_Tiefensuche
Da es sich bereits um einen Baum Handelt, führt jeder Knoten nur zu einem Nachfolgeknoten.Wahrscheinlich wäre hier genauer, im allgemeinen lässt man jedoch dann die Faktoren und Konstanten weg, da diese unerheblich für die Laufzeitbetrachtung sind.
VG,
Karlito
|
|
12.02.2012 12:53 |
|
|
|