Suffix Arrays vs Suffix Bäume

Question

Ich möchte nur wissen, wenn eine Suffix-Struktur ist besser als ein Suffix-Array.

Nach dem Lesen Replacing suffix trees with enhanced suffix arrays sehe ich keinen Grund mehr, Suffixbäume zu verwenden. Einige Methoden können kompliziert werden, aber Sie können alles mit einem Suffix-Array tun, was Sie mit einer Suffix-Struktur tun können und Sie benötigen die gleiche Zeitkomplexität, aber weniger Speicher.

Ein survey zeigte sogar, dass Suffix-Arrays schneller sind, weil sie Cachefreundlicher sind und nicht so viele Cache-Misses erzeugen, als Suffix-Bäume (so kann der Cache die Array-Nutzung viel besser vorhersagen, als auf dem Rekursiven Baumstruktur).

Also, weiß jemand einen Grund, einen Suffixbaum über ein Suffix-Array zu wählen?

bearbeiten Ok, wenn Sie wissen, mehr mir sagen, so weit sein:

• Suffixarrays on-line nicht erlaubt Bau
• Einige Muster Algorithmen schneller laufen auf Suffixtrees passenden
• (hinzugefügt) wegen der Online-Konstruktion können Sie es auf HD a speichern und ein vorhandenes Suffix vergrößern. Wenn Sie eine SSD verwenden, sollte es auch schnell ruhig sein.

Answer 1

Es gibt einige interesting thoughts zum Thema in SO selbst. Sie können auch more technical material online verfügbar finden. Es gibt another paper, die Ihnen bei Ihren Problemen behilflich sein könnten und behaupten, eine weitere effiziente Möglichkeit zu sein, diese Strukturen zu implementieren.

Ich bin kein Experte in diesem Problem, aber es scheint mir, dass Suffix-Arrays etwas langsamer sein können, obwohl sie platzsparender sind. Dennoch fehlt mir die praktische Erfahrung, um beide genauer zu beschreiben.

Answer 2

Ein weiteres Beispiel dafür, dass ein Suffix-Baum überlegen ist:

Sie leicht ein Suffix Array konstruieren kann, wenn Sie einen Suffix-Baum bereits haben.

Aber es ist viel komplizierter, einen Suffixbaum aus einem Suffix-Array zu konstruieren.