Algorithmus zum Erstellen eines Suffix-Arrays in der Zeit

7

Ich habe in letzter Zeit mit Suffix-Arrays gearbeitet und kann keinen effizienten Algorithmus zum Erstellen eines Suffix-Arrays finden, der leicht zu verstehen ist. Ich habe an vielen Stellen gesehen, dass es einen -Algorithmus gibt, aber ich kann ihn nicht verstehen, da viele wichtige Details weggelassen werden. Es gibt ein Beispiel bei Top Coder .O(nlog2n)

Könnte mir jemand einen effizienten Algorithmus für die Suffix-Array-Konstruktion vorstellen, der leicht zu verstehen ist?

Rontogiannis Aristofanis
quelle

Antworten:

15

Mit dem DC-3-Algorithmus können Sie das Suffix-Array in linearer Zeit berechnen . Dies ist ein super cooler ausgefallener Algorithmus, der in 50 Zeilen lesbaren C ++ - Codes implementiert werden kann - einer meiner Favoriten aller Zeiten. Der Quellcode ist im Originalpapier enthalten. Wenn Sie zwei Zeichen in konstanter Zeit vergleichen können und die Alphabetgröße , wird der DC3-Algorithmus in -Zeit ausgeführt.nO(1)O(n)

Beachten Sie, dass Sie den Suffix-Baum auch in linearer Zeit abrufen können, wenn Sie Zugriff auf das Suffix-Array und das LCP-Array haben. Das LCP-Array kann auch mit dem DC3-Algorithmus aufgebaut werden.

A.Schulz
quelle
4

Hier ist eine gute Erklärung für den -Algorithmus: http://www.stanford.edu/class/cs97si/suffix-array.pdf . Tatsächlich ergibt der gleiche Ansatz unter Verwendung der linearen Zeitsortierung eine -Zeitkomplexität.O(nlog2n)O(nlogn)

Wenn Sie spezielle Fragen dazu haben, können Sie diese gerne stellen.

Ich stimme A. Schultz zu, dass DC-3 super cool ist. Es ist auch nicht sehr kompliziert, aber das ist noch einfacher.O(nlog2n)

user302099
quelle