algorithm - Suffix Arrays vs Suffix Trees
time-complexity suffix-tree (2)
Hay algunos pensamientos interesantes sobre el tema en el mismo SO. También puede encontrar más material técnico disponible en línea. Hay otro documento que podría 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, aunque sean más eficientes en cuanto al espacio. Sin embargo, me falta la experiencia práctica para ser más detallado sobre ambos.
Solo quiero saber, cuando un árbol de sufijos es superior a una matriz de sufijos mejorada.
Después de leer Reemplazar árboles de sufijos con arreglos de sufijos mejorados, ya no veo una razón para usar árboles de sufijos. 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.
Una survey incluso mostró que los arreglos de sufijos son más rápidos porque son más amigables con el caché y no producen tantos fallos de caché, luego los árboles de sufijo (de modo que el caché puede predecir el uso del arreglo mucho mejor, luego en la estructura de árbol recursiva)
Entonces, ¿alguien sabe una razón para elegir un árbol de sufijos sobre una matriz de sufijos?
Ok, si sabes más dime, hasta ahora es:
- Los sufijos no permiten la construcción en línea
- Algunos algoritmos de coincidencia de patrones se ejecutan más rápido en Suffixtrees
- (agregado) debido a la construcción en línea, puede guardarlo en hd a y ampliar un sufijo existente. Si usa un SSD, debe ser silencioso y rápido.
Otro ejemplo para mostrar que un árbol de sufijos es superior:
Puede construir fácilmente una matriz de sufijos si ya tiene un árbol de sufijos.
Pero es mucho más complicado construir un árbol de sufijos a partir de una matriz de sufijos.