Ich bin auf der Suche nach einem kurzen, einfachen Suffixbaum, der in Java verwendet wird. Das Beste, was ich bisher gefunden habe, liegt im Semantic Discovery Toolkit, aber die Implementierung ist mehrere tausend Zeilen lang und umfasst mehrere Klassen. Idealerweise sollte die Implementierung so kurz wie möglich sein und nicht mehr als ein paar hundert Zeilen umfassen.
Hat jemand eine solche Implementierung?
Ich habe gerade eine Java-Implementierung eines Suffixbaums abgeschlossen. In meinem Blog-Eintrag können Sie mehr über Suffix-Bäume erfahren Wie benutze ich meine Bibliothek, und lade und baue die Bibliothek mit Subversion und Maven. Ja, es ist länger als nur ein paar Zeilen in einer einzelnen Klassendatei, aber es ist sehr gut dokumentiert und wurde für den Gebrauch in der realen Welt für praktische Zwecke erstellt. Darüber hinaus verwendet es den Ukkonen-Ansatz für die lineare Zeitkonstruktion. (Die meisten hier aufgeführten Implementierungen haben mindestens eine Laufzeit von 0 (n ^ 2).)
Der Artikel "Simple Linear Work Suffix Array Construction" von Karkkainen und Sanders endet mit 50 Zeilen C ++. Sie werden wahrscheinlich auch etwas wollen, um das LCP-Array zu produzieren. Googeln nach "Berechnen des LCP-Arrays in linearer Zeit, gegeben S und dem Suffix-Array POS." Ich sollte dich finden.
Sie können auch meins , aber das ist kein Algorithmus von Ukkonen - wie alle anderen einfachen Ansätze läuft er in quadratischer Zeit. Ich stimme zu, dass ein naive Algorithmus (der für die kürzeren Sequenzen in Ordnung sein kann) leicht in höchstens einem halben Tag zu schreiben ist.
Tags und Links algorithm string java suffix-tree