Estoy buscando un algoritmo de uso/construcción de árbol de sufijos corto y simple en Java. Lo mejor que he encontrado hasta ahora está en el Semantic Discovery Toolkit, pero la implementación abarca varios miles de líneas y abarca varias clases. Idealmente, la implementación sería lo más corta posible y abarcaría no más de unos cientos de líneas.Corto, implementación de Java de un árbol de sufijos y uso?
¿Alguien tiene tal implementación?
El artículo "Simple Linear Work Suffix Array Construction", de Karkkainen y Sanders, termina con 50 líneas de C++. Probablemente también quiera algo para producir el arreglo LCP. Búsqueda de Google para "Calcular la matriz LCP en tiempo lineal, con S y la matriz de sufijo POS". debería encontrarte eso.
También puede tomar mine, pero este no es el algoritmo de Ukkonen, como todos los demás enfoques simples, se ejecuta en tiempo cuadrático. Estoy de acuerdo en que un algoritmo ingenuo (que puede funcionar bien para las secuencias más cortas) es fácil de escribir en medio día como máximo.
Acabo de terminar una implementación de Java de un árbol de sufijos. En mi blog entry puede encontrar más información sobre los árboles de sufijos, ver cómo usar mi biblioteca, así como descargar y compilar la biblioteca usando Subversion y Maven. Sí, es más que unas pocas líneas en un solo archivo de clase, pero está muy documentado y se ha creado para su uso en el mundo real con fines prácticos. Además, utiliza el enfoque de Ukkonen para la construcción del tiempo lineal. (La mayoría de las implementaciones indicadas aquí tienen al menos O (n^2) tiempo de ejecución).
+1 Aunque OP no especificó la escalabilidad/rendimiento como criterios, esos son casi siempre para mí; por lo tanto, es importante obtener el tiempo lineal, y por lo tanto el enfoque de Uknonnen. Al incluir esos criterios, esta es una respuesta de calidad. – javadba
no, pero escribí una en ruby hace un tiempo. probablemente debas escribirlo tú mismo si quieres una implementación corta ... char [] c = string.toCharArray(); for (int i = c.length-1; i> = 0; i ++) recurse (c [i]) ... – twolfe18
Póngalo como respuesta para que pueda votarlo. Solo necesito algo que se ajuste a una hoja de papel a la que pueda hacer referencia fácilmente. En breve, necesitaré ser capaz de producir una cantidad de algoritmos con documentación mínima, por lo que las implementaciones cortas son buenas implementaciones. –