Wie hängt die Laufzeit des Ukkonen-Algorithmus von der Alphabetgröße ab?

19

Ich beschäftige mich mit der Frage nach der asymptotischen Laufzeit des Ukkonen-Algorithmus , dem vielleicht beliebtesten Algorithmus zur Konstruktion von Suffix-Bäumen in linearer (?) Zeit.

Hier ist ein Zitat aus dem Buch "Algorithmen für Strings, Bäume und Sequenzen" von Dan Gusfield (Abschnitt 6.5.1):

"... die Algorithmen Aho-Corasick, Weiner, Ukkonen und McCreight benötigen entweder alle Platz, oder die O ( m ) -Zeitgrenze sollte durch das Minimum von O ( m log m ) und O ersetzt werden ( m log | Σ | ) ".Θ(m|Σ|)O(m)O(mLog⁡m)O(mLog⁡|Σ|)

[ ist die Länge der Zeichenkette und Σ ist die Größe des Alphabets]mΣ

Ich verstehe nicht, warum das so ist.

  • Raum: Nun, falls wir Zweige aus den Knoten mit Arrays der Größe , erhalten wir tatsächlich eine Raumnutzung von Θ ( m | Σ | ) . Soweit ich sehen kann, ist es jedoch auch möglich, die Zweige mithilfe von Hash-Tabellen zu speichern (z. B. Wörterbücher in Python). Wir würden dann nur Θ ( m ) Zeiger in allen Hash - Tabellen zusammen gespeichert (da es Θ ( m ) Kanten im Baum), während noch in der Lage zu sein , die Kinder - Knoten in dem Zugriff auf O ( 1 )Θ(|Σ|)Θ(m|Σ|)Θ(m)Θ(m)O(1) Zeit, so schnell wie bei der Verwendung von Arrays.
  • Zeit : Wie oben erwähnt, können wir mithilfe von Hash-Tabellen in -Zeit auf die ausgehenden Zweige eines beliebigen Knotens zugreifen . Da der Ukkonen-Algorithmus O ( m ) -Operationen erfordert (einschließlich des Zugriffs auf untergeordnete Knoten), wäre die Gesamtlaufzeit dann auch O ( m ) .O(1)O(m)O(m)

Ich wäre Ihnen sehr dankbar für Hinweise, warum ich in meinen Schlussfolgerungen falsch liege und warum Gusfield in Bezug auf die Abhängigkeit des Ukkonen-Algorithmus vom Alphabet Recht hat.

algorithms data-structures algorithm-analysis strings Mikhail Dubov
quelle
3
Ich glaube nicht, dass es Beweise dafür gibt, dass eine alphabetisch unabhängige zeitliche / räumliche Begrenzung unmöglich ist. Ich glaube, Gusfield gab die Erklärung ab, weil es keine bekannte Methode gibt, um die Zeit vollständig loszuwerden. Um eine einzurichten, müssten Sie Ihre Hash-Funktionen genauer erläutern. Eine echte Worst-Case-O (1) -Zeit für die Hash-Suche erfordert einen perfekten Hash. Mir ist nicht klar, wie das während des Algorithmus gemacht wird (da die Hash-Einträge zu diesem Zeitpunkt nicht statisch sind).
Jogojapan
(Fortsetzung) Sie können dies tun, wenn der Baum vollständig ist, aber die für den Algorithmus selbst festgelegte Zeit bleibt unverändert. (+1 für die Frage.)
Jogojapan
1
Nützlicher Kontext: Erläuterung des Ukkonen-Algorithmus
FrankW

Antworten:

2

Wie @jogojapan in den Kommentaren erwähnt, wird hasing im Allgemeinen nur mit amortisiert , sodass Sie nur amortisierte Grenzen für den Algorithmus erhalten. Ich denke jedoch, dass Sie diese nicht einmal erhalten: Um amortisiertes O ( 1 ) -Hashing zu erhalten, müssen die Hash-Tabellen die Größe Ω ( Σ ) haben , sodass Sie immer noch Θ ( m Σ ) Speicherplatz (und gleichzeitig) haben Voraussetzung für die Initialisierung).O(1)O(1)Ω(Σ)Θ(mΣ)

Darüber hinaus ist in der Praxis die Zeit zum Einrichten all dieser Hash-Tabellen viel länger als die Zeit zum Einrichten von Arrays.

Mit einer globalen Hash-Tabelle, die mit (Knoten-, Zeichen-) Paaren indiziert ist, könnten Sie besser abschneiden, aber mindestens das Argument "nur amortisiert" bleibt erhalten.

FrankW
quelle