suffix-array - arboles - suffix array geeksforgeeks
¿Cuál es el algoritmo de construcción de matriz de sufijo de última generación? (3)
Estoy buscando un algoritmo de construcción de suffix-array rápido. Estoy más interesado en la facilidad de implementación y la velocidad cruda que en la complejidad asintótica (sé que una matriz de sufijo puede construirse mediante un árbol de sufijos en el tiempo O (n), pero eso ocupa mucho espacio, aparentemente otros algoritmos tienen peor de los peores de la complejidad de la gran O, pero se ejecuta bastante rápido en la práctica). No me molestan los algoritmos que generan una matriz LCP como subproducto, ya que, de todos modos, necesito uno para mis propios fines.
Encontré una taxonomía de varios algoritmos de construcción de matriz de sufijos , pero está desactualizada. He oído hablar de SA-IS , qsufsort y BPR , pero realmente no sé cómo se comparan entre sí, ni si hay algoritmos mejores. Teniendo en cuenta qué tan caliente parece ser el campo de matriz de sufijos en este momento, espero que algunos otros algoritmos hayan reemplazado a aquellos desde que se publicaron. Me parece recordar encontrar un documento que describa un algoritmo rápido llamado "división", pero no lo puedo encontrar ahora.
Entonces, ¿cuál es el estado actual del arte? Idealmente, me gustaría obtener una breve lista de los mejores algoritmos actuales (con enlaces, si es posible) y una descripción general rápida de sus fortalezas y debilidades relativas.
Actualmente, el mejor constructor de Suffix-Array conocido es LibDivSufSort, por Yuta Mori: http://code.google.com/p/libdivsufsort/
Utiliza la metodología de clasificación inducida (Básicamente, después de ordenar todas las cadenas que comienzan con "A *", puede inducir clasificaciones de cadenas "BA *" "CA *" "DA *", etc.)
Se elogia en todas partes por su eficacia y buen manejo de los casos degenerados. También es el más rápido y usa la cantidad óptima de memoria (5N). La licencia no es molesta, por lo que este algoritmo está integrado en varios otros programas, como por ejemplo la biblioteca de compresión libbsc, de Ilya Grebnov. http://libbsc.com/default.aspx
Para fines de comparación, encontrará un Suffix Array Compression benchmarks vinculado en esta página: http://code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks y esta página http://homepage3.nifty.com/wpage/benchmark/index.html
El punto de referencia también enumera muchas otras implementaciones dignas de SACA. Sin embargo, por razones tanto de licencia como de eficiencia, recomendaría libdivsufsort entre ellos.
Editar: Aparentemente, se dice que MSufsort se dirigirá hacia la versión 4 próximamente, y se supone que llegará a ser bastante más rápido que Divsufsort. Si eso es correcto, se convertiría en un nuevo campeón de SACA. Pero aún no tenemos fecha de lanzamiento, y esto será material alfa. Entonces, si necesita una implementación probada ahora, libdivsufsort sigue siendo la mejor opción.
Tenga en cuenta también que estas "mejores implementaciones de SACA" no utilizan "un algoritmo de construcción", sino que combinan varios trucos de optimización, lo que los hace difíciles de resumir.
Podrías mirar:
Un recorrido rápido por matrices de sufijos y matrices de sufijos comprimidos R Grossi - Theoretical Computer Science, 2011
Probablemente los nuevos algoritmos de matriz de sufijos ya no se desarrollen al ritmo que imagina. Para estar a la vanguardia, sugeriría Mirar las estructuras de datos que se usan junto con las matrices de sufijo y mirar los documentos sobre las matemáticas relacionadas con matrices de sufijos: Schürmann, Munro, He, etc.
http://code.google.com/p/libdivsufsort/source/browse/wiki/SACA_Benchmarks.wiki proporciona la lista de los algoritmos más rápidos que desea.
La implementación de kvark es la más rápida en la mayoría de los casos en el punto de referencia anterior. Puede encontrar el código en http://www.kvatom.com/archon .
libdivsufsort es una combinación del algoritmo de TI y el proceso posterior de Ordenación Inducida. Se selecciona un subconjunto de sufijos igual que el algoritmo de clasificación inducido, pero en lugar de resolverlo recursivamente mediante clasificación inducida, se ordenan por el algoritmo de TI.
libdivsufsort y la implementación de kvark se basan en el algoritmo de TI.
El algoritmo de KA es similar al algoritmo de TI, que aparece en 99. Ambos dividen los sufijos en 2 categorías: escriba S o escriba L. Si el sufijo i-ésimo es más pequeño que el sufijo (i + 1) -th, es tipo S; de lo contrario, es tipo L. Después de ordenar todos los sufijos de tipo S, podemos deducir el orden de todos los sufijos de tipo L, y luego terminamos.
La diferencia entre el algoritmo de KA y el algoritmo de TI es que: KA utiliza recursividad para ordenar las subcadenas, mientras que el algoritmo de TI se apega a Multikey Quicksort / MSD / sorting de inserción.