Con la compensación amortizada de la construcción inicial del árbol de sufijos, tiene la ventaja de permitir el recorrido en tiempo lineal proporcional al patrón de búsqueda en lugar de todo el espacio de búsqueda, así como almacenar los sufijos en orden lexicográfico. Esta es la razón por la que son populares en genómica, donde el espacio de búsqueda a menudo está en miles de millones de caracteres, pero los investigadores generalmente solo se preocupan por secuencias relativamente pequeñas en el rango de unos cientos de caracteres como máximo. Un caso de uso común para esto es encontrar subcadenas comunes más largas utilizando el recorrido de profundidad primero (ya que todas las subcadenas comunes tienen prefijos comunes).
Imagen cortesía de Dan Gusfield, quien dio una gran conferencia sobre árboles y matrices de sufijos en el campo de entrenamiento de desafíos genómicos del Instituto Simons.
- ¿Cómo se puede resolver el coeficiente binomial usando programación dinámica y tabla hash?
- ¿Debería un ingeniero que no sea CS aprender programación, algoritmos y estructuras de datos?
- ¿Cuál es mi concepto erróneo con respecto al algoritmo de clasificación de fusión aquí?
- ¿Pueden los algoritmos de aprendizaje automático reforzar los estereotipos?
- ¿Cuál es el problema de algoritmo más difícil en LeetCode?
Un gran avance fue la capacidad de construir árboles de sufijos en tiempo lineal en lugar de cuadrático a través de varios algoritmos, todos los cuales usan matrices de sufijos. Las matrices en sí están construidas usando la compresión de cadena Ziv-Lempel, que se ha demostrado que se acerca mucho al límite de Shannon y también es el primer paso en el algoritmo DEFLATE utilizado por los formatos gzip, PNG y ZIP, así como LZW utilizado por GIF
La compresión LZ esencialmente solo construye una matriz de todas las subcadenas que no han aparecido previamente junto con una referencia al índice en la misma matriz de la subcadena que constituye su prefijo. Esto facilita la consulta de prefijos comunes en tiempo lineal y, por lo tanto, trivial para construir árboles de sufijos, ya que el número de prefijos comunes determina la distancia de una subcadena desde la raíz y la ramificación se puede determinar en tiempo constante.
Volviendo a la pregunta, los árboles de sufijos proporcionan una búsqueda de tiempo lineal, mientras que las matrices de sufijos proporcionan almacenamiento de espacio lineal con ambas propiedades determinadas por cómo representan prefijos comunes.
Sin embargo, vale la pena señalar que la mayoría de los algoritmos utilizados en árboles de sufijos se pueden usar en matrices de sufijos con la misma complejidad de tiempo si se agrega otra matriz de prefijos menos comunes. Esto es importante porque tener que convertir un árbol de sufijos en una matriz de sufijos obviamente hace que la agradable complejidad espacial de este último sea inútil. No describiré cómo construir tanto matrices de sufijos como matrices de prefijos menos comunes en tiempo lineal, pero para aquellos que estén interesados, un método común es un algoritmo recursivo introducido en 2003 por Kärkkäinen & Sanders.
