Arreglos de sufijos vs Arboles de sufijo

Question

Solo quiero saber, cuando un arbol de sufijo es superior a un arreglo de sufijo mejorado.

Después de leer Replacing suffix trees with enhanced suffix arrays ya no veo una razón para usar árboles de sufijo. Algunos métodos pueden complicarse, pero puede hacer todo con una matriz de sufijos, lo que puede hacer con un árbol de sufijos y necesita la misma complejidad de tiempo pero menos memoria.

A survey incluso mostró, que los arreglos de sufijo son más rápidos, porque son más amigables con la caché, y no producen tanta falta de memoria caché, luego árboles de sufijos (para que la memoria caché pueda predecir el uso de la matriz mucho mejor, luego en el recursivo estructura de árbol).

Entonces, ¿alguien sabe una razón para elegir un árbol de sufijos sobre una matriz de sufijos?

edición Ok, si usted sabe más dime, hasta ahora su:

• Suffixarrays no permitimos la construcción en línea
• Algunos de coincidencia de patrones algoritmos de correr más rápido en Suffixtrees
• (añadido) debido a la construcción en línea, puede guardarlo en hd a y agrandar un sufijo original existente. Si usa un SSD, también debe ser silencioso.

Answer 1

Hay algunos interesting thoughts sobre el tema en SO en sí. También puede encontrar more technical material disponible en línea. Hay another paper que pueden ayudarlo con sus problemas, afirmando ser otra forma eficiente de implementar estas estructuras.

No soy un experto en el tema, pero me parece que los arreglos de sufijos pueden ser algo más lentos, a pesar de que son más eficientes en el uso del espacio. Sin embargo, carezco de la experiencia práctica para ser más detallados sobre ambos.

Answer 2

Otro ejemplo para mostrar que un árbol de sufijos es superior:

Usted puede construir fácilmente un arreglo de sufijos si tiene un árbol de sufijos ya.

Pero es mucho más complicado construir un árbol de sufijos a partir de una matriz de sufijos.