¿Cuál es el algoritmo de construcción de matriz de sufijo de última generación actual?

Question

Estoy buscando un algoritmo de construcción rápido suffix-array. 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é taxonomy of various suffix array construction algorithms, pero está desactualizado. 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 de la técnica? 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.

Answer 1

Actualmente, el mejor constructor de Suffix-Array conocido es LibDivSufSort, por Yuta Mori: http://code.google.com/p/libdivsufsort/

se utiliza la metodología inducido Seleccionador (Básicamente, después de la clasificación de todas las cadenas que comienzan con "A *", puede inducir granulometrías de cuerdas "BA *" "CA *" "DA * "etc.)

Se elogia en todas partes por su effi ciencia y buen manejo de 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, se encuentra un sufijo puntos de referencia de compresión de matriz vinculados a 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 muchos otros aplicación digna 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 usan "un algoritmo de construcción", sino que combinan varios trucos de optimización, lo que los hace difíciles de resumir.

Answer 2

Se podría buscar en:

Un rápido recorrido por el sufijo arrays y matrices sufijo comprimidos R Grossi - Ciencias de la Computación Teórica de 2011

Probablemente nuevos algoritmos sufijo matriz se ya no se están desarrollando al ritmo Imagina. Para estar al borde de la hemorragia, sugeriría Ver estructuras de datos que se usan junto con matrices de sufijo y ver documentos sobre matemáticas relacionadas con matrices de sufijos: Schürmann, Munro, Él etc.

Answer 3

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 índice 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 de publicación de la Clasificació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 i-ésimo sufijo es menor que (i + 1) -th sufijo, 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.