Kurz, die Java-Implementierung von einem suffix-Baum und-Nutzung?
Ich bin auf der Suche nach einem kurzen, einfachen suffix-Baum-Gebäude/Nutzung-Algorithmus in Java. Die beste, die ich bisher gefunden habe, liegt innerhalb der Semantischen Discovery Toolkit, aber die Umsetzung ist mehrere tausend Zeilen lang und erstreckt sich über mehrere Klassen. Im Idealfall wäre die Implementierung so kurz wie möglich und Spanne nicht mehr als ein paar hundert Zeilen.
Hat jemand eine solche Umsetzung?
- Nein, aber ich schrieb man in ruby eine Weile zurück. Sie sollten wahrscheinlich nur Sie selbst schreiben, wenn Sie wollen, eine kurze Einführung... char[] c = string.toCharArray(); for(int i=c.length-1; i>=0; i++) recurse(c[i])...
- Poste es als Antwort, so kann ich upvote es. Ich brauche nur etwas, das passt auf ein Blatt Papier, auf dem ich verweisen kann leicht. In Kürze werde ich brauchen, um in der Lage zu produzieren eine Reihe von algorithmen, mit minimal-Dokumentation, so kurz Implementierungen sind gute Implementierungen.
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ich habe gerade eine Java-Implementierung eines suffix-Baumes. In meinem blog-Eintrag Sie können herausfinden, mehr über das suffix-Bäume, sehen, wie meine Bibliothek, als auch die download-und aufbauen der Bibliothek mit Subversion und Maven. Ja, es ist mehr als nur ein paar Zeilen in einer Klasse-Datei, aber es wird dringend dokumentiert und ist für den Einsatz in der realen Welt ist für praktische Zwecke. Außerdem verwendet es die Ukkonen-Ansatz für linear-Zeit-Konstruktion. (Die meisten Implementierungen hier angemerkt haben mindestens O(n^2) Laufzeit.)
Den Artikel "Simple Linear Work Suffix Array Construction", von Karkkainen und Sanders, beendet mit 50 Zeilen C++. Sie werden wahrscheinlich auch wollen, etwas zu produzieren, das LCP-array. Sie googeln für "Berechnung des LCP-Arrays in linearzeit, da S-und dem suffix-array POS." sollten finden Sie, dass.
Können Sie auch mir aber das ist nicht Ukkonen ' s Algorithmus - wie alle anderen einfachen Ansätze, es läuft in quadratischer Zeit. Ich bin damit einverstanden, dass ein naiver Algorithmus (das ok für die kürzere Sequenzen) ist einfach zu schreiben in einem halben Tag am meisten.