árbol de sufijos

Árbol que contiene todos los sufijos de un texto determinado.

Árbol de sufijos para el texto BANANA. Cada subcadena termina con un carácter especial $. Los seis caminos desde la raíz hasta las hojas (que se muestran como cuadros) corresponden a los seis sufijos A$,,,, y . Los números en las hojas dan la posición inicial del sufijo correspondiente. Los enlaces de sufijos, dibujados con puntos, se utilizan durante la construcción.NA$ANA$NANA$ANANA$BANANA$

En informática , un árbol de sufijos (también llamado árbol PAT o, en una forma anterior, árbol de posiciones ) es un trie comprimido que contiene todos los sufijos del texto dado como sus claves y las posiciones en el texto como sus valores. Los árboles de sufijos permiten implementaciones particularmente rápidas de muchas operaciones de cadenas importantes.

La construcción de tal árbol para la cuerda toma tiempo y espacio lineal en la longitud de . Una vez construida, se pueden realizar varias operaciones rápidamente, como ubicar una subcadena en , ubicar una subcadena si se permite una cierta cantidad de errores y ubicar coincidencias para un patrón de expresión regular . Los árboles de sufijos también proporcionaron una de las primeras soluciones de tiempo lineal para el problema de subcadena común más larga . ^[2] Estas aceleraciones tienen un costo: almacenar el árbol de sufijos de una cadena normalmente requiere mucho más espacio que almacenar la cadena misma. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

Historia

El concepto fue introducido por primera vez por Weiner (1973). En lugar del sufijo , Weiner almacenó en su trie ^[3] el identificador de prefijo para cada posición, es decir, la cadena más corta que comienza en y ocurre solo una vez en . Su algoritmo D toma un intento ^[4] sin comprimir y lo extiende a un intento por . De esta manera, a partir del trivial trie for , se puede construir un trie for mediante llamadas sucesivas al Algoritmo D; sin embargo, el tiempo de ejecución general es . El algoritmo B de Weiner mantiene varias estructuras de datos auxiliares para lograr un tiempo de ejecución lineal en el tamaño del trie construido. Estos últimos todavía pueden ser nodos, por ejemplo, el algoritmo C de Weiner finalmente utiliza intentos comprimidos para lograr un tamaño de almacenamiento general lineal y un tiempo de ejecución. ^[5] Donald Knuth caracterizó posteriormente este último como "Algoritmo del año 1973", según su alumno Vaughan Pratt . ^{[ ¿investigacion original? ] [6]} El libro de texto Aho, Hopcroft & Ullman (1974, Sect.9.5) reprodujo los resultados de Weiner en una forma simplificada y más elegante, introduciendo el término árbol de posición . ${\displaystyle S[i..n]}$ ${\displaystyle i}$ ${\displaystyle S}$ ${\displaystyle S[k+1..n]}$ ${\displaystyle S[k..n]}$ ${\displaystyle S[n..n]}$ ${\displaystyle S[1..n]}$ ${\displaystyle n-1}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{2})}$ ${\displaystyle S=a^{n}b^{n}a^{n}b^{n}\$.}$

McCreight (1976) fue el primero en construir un trie (comprimido) de todos los sufijos de . Aunque el sufijo que comienza en suele ser más largo que el identificador de prefijo, sus representaciones de ruta en un trie comprimido no difieren en tamaño. Por otro lado, McCreight podría prescindir de la mayoría de las estructuras de datos auxiliares de Weiner; sólo quedaron enlaces de sufijo. ${\displaystyle S}$ ${\displaystyle i}$

Ukkonen (1995) simplificó aún más la construcción. ^[6] Proporcionó la primera construcción en línea de árboles de sufijos, ahora conocido como algoritmo de Ukkonen , con un tiempo de ejecución que coincidía con los algoritmos más rápidos de entonces. Todos estos algoritmos son de tiempo lineal para un alfabeto de tamaño constante y, en general, tienen un tiempo de ejecución en el peor de los casos. ${\displaystyle O(n\log n)}$

Farach (1997) presentó el primer algoritmo de construcción de árbol de sufijos que es óptimo para todos los alfabetos. En particular, este es el primer algoritmo de tiempo lineal para cadenas extraídas de un alfabeto de números enteros en un rango polinómico. El algoritmo de Farach se ha convertido en la base de nuevos algoritmos para construir árboles y matrices de sufijos , por ejemplo, en memoria externa, comprimido, sucinto, etc.

Definición

El árbol de sufijos para la cadena de longitud se define como un árbol tal que: ^[7] ${\displaystyle S}$ ${\displaystyle n}$

1. El árbol tiene exactamente n hojas numeradas del hasta . ${\displaystyle 1}$ ${\displaystyle n}$
2. Excepto la raíz, cada nodo interno tiene al menos dos hijos.
3. Cada borde está etiquetado con una subcadena no vacía de . ${\displaystyle S}$
4. No hay dos bordes que comiencen en un nodo que puedan tener etiquetas de cadena que comiencen con el mismo carácter.
5. La cadena obtenida al concatenar todas las etiquetas de cadena que se encuentran en el camino desde la raíz hasta la hoja deletrea el sufijo , de hasta . ${\displaystyle i}$ ${\displaystyle S[i..n]}$ ${\displaystyle i}$ ${\displaystyle 1}$ ${\displaystyle n}$

Si un sufijo de es también el prefijo de otro sufijo, dicho árbol no existe para la cadena. Por ejemplo, en la cadena abcbc , el sufijo bc también es un prefijo del sufijo bbcc . En tal caso, el camino que detalla bc no terminará en una hoja, violando la quinta regla. Para solucionar este problema, se rellena con un símbolo de terminal que no se ve en la cadena (normalmente denominado ). Esto asegura que ningún sufijo sea un prefijo de otro, y que habrá nodos hoja, uno para cada uno de los sufijos de . ^[8] Dado que todos los nodos internos no raíz se están ramificando, puede haber como máximo dichos nodos y nodos en total ( hojas, nodos internos no raíz, 1 raíz). ${\displaystyle S}$ ${\displaystyle S}$$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle n-1}$ ${\displaystyle n+(n-1)+1=2n}$ ${\displaystyle n}$ ${\displaystyle n-1}$

Los enlaces de sufijos son una característica clave para los algoritmos de construcción de tiempo lineal más antiguos, aunque la mayoría de los algoritmos más nuevos, que se basan en el algoritmo de Farach, prescinden de los enlaces de sufijos. En un árbol de sufijos completo, todos los nodos internos que no son raíz tienen un enlace de sufijo a otro nodo interno. Si la ruta desde la raíz a un nodo deletrea la cadena , donde es un solo carácter y es una cadena (posiblemente vacía), tiene un enlace de sufijo al nodo interno que representa . Vea, por ejemplo, el enlace de sufijo del nodo for al nodo for en la figura anterior. Los enlaces de sufijo también se utilizan en algunos algoritmos que se ejecutan en el árbol. ${\displaystyle \chi \alpha }$ ${\displaystyle \chi }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ANANA

Un árbol de sufijos generalizado es un árbol de sufijos creado para un conjunto de cadenas en lugar de una sola cadena. Representa todos los sufijos de este conjunto de cadenas. Cada cadena debe terminar con un símbolo de terminación diferente.

Funcionalidad

Se puede construir un árbol de sufijos para una cadena de longitud en el tiempo, si las letras provienen de un alfabeto de números enteros en un rango polinómico (en particular, esto es cierto para alfabetos de tamaño constante). ^[9] Para alfabetos más grandes, el tiempo de ejecución está dominado por ordenar primero las letras para colocarlas en un rango de tamaño ; en general, esto lleva tiempo. Los costos a continuación se dan bajo el supuesto de que el alfabeto es constante. ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle \Theta (n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n\log n)}$

Supongamos que se ha construido un árbol de sufijos para la cadena de longitud , o que se ha construido un árbol de sufijos generalizado para el conjunto de cadenas de longitud total . Puede: ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle D=\{S_{1},S_{2},\dots ,S_{K}\}}$ ${\displaystyle n=n_{1}+n_{2}+\cdots +n_{K}}$

• Buscar cadenas:
  • Compruebe si una cadena de longitud es una subcadena en el tiempo. ^[10] ${\displaystyle P}$ ${\displaystyle m}$ ${\displaystyle O(m)}$
  • Encuentre la primera aparición de los patrones de longitud total como subcadenas en el tiempo. ${\displaystyle P_{1},\dots ,P_{q}}$ ${\displaystyle m}$ ${\displaystyle O(m)}$
  • Encuentre todas las apariciones de los patrones de longitud total como subcadenas en el tiempo. ^[11] ${\displaystyle z}$ ${\displaystyle P_{1},\dots ,P_{q}}$ ${\displaystyle m}$ ${\displaystyle O(m+z)}$
  • Busque una expresión regular P en el tiempo esperado sublineal en . ^[12] ${\displaystyle n}$
  • Encuentre para cada sufijo de un patrón , la longitud de la coincidencia más larga entre un prefijo de y una subcadena en el tiempo. ^[13] Esto se denomina estadística coincidente para . ${\displaystyle P}$ ${\displaystyle P[i\dots m]}$ ${\displaystyle D}$ ${\displaystyle \Theta (m)}$ ${\displaystyle P}$
• Encuentra las propiedades de las cuerdas:
  • Encuentre las subcadenas comunes más largas de la cadena y en el tiempo. ^[14] ${\displaystyle S_{i}}$ ${\displaystyle S_{j}}$ ${\displaystyle \Theta (n_{i}+n_{j})}$
  • Encuentre todos los pares máximos , repeticiones máximas o repeticiones supermáximas en el tiempo. ^[15] ${\displaystyle \Theta (n+z)}$
  • Encuentre la descomposición de Lempel-Ziv en el tiempo. ^[dieciséis] ${\displaystyle \Theta (n)}$
  • Encuentra las subcadenas repetidas más largas en el tiempo. ${\displaystyle \Theta (n)}$
  • Encuentre las subcadenas que ocurren con más frecuencia y que tengan una duración mínima en el tiempo. ${\displaystyle \Theta (n)}$
  • Encuentre las cadenas más cortas que no aparecen en el tiempo, si existen . ${\displaystyle \Sigma }$ ${\displaystyle D}$ ${\displaystyle O(n+z)}$ ${\displaystyle z}$
  • Encuentre las subcadenas más cortas que aparecen solo una vez en el tiempo. ${\displaystyle \Theta (n)}$
  • Encuentre, para cada uno , las subcadenas más cortas que no ocurran en ningún otro lugar en el tiempo. ${\displaystyle i}$ ${\displaystyle S_{i}}$ ${\displaystyle D}$ ${\displaystyle \Theta (n)}$

El árbol de sufijos se puede preparar para la recuperación del ancestro común más bajo en tiempo constante entre nodos en el tiempo. ^[17] Entonces también se puede: ${\displaystyle \Theta (n)}$

• Encuentre el prefijo común más largo entre los sufijos y en . ^[18] ${\displaystyle S_{i}[p..n_{i}]}$ ${\displaystyle S_{j}[q..n_{j}]}$ ${\displaystyle \Theta (1)}$
• Busque un patrón P de longitud m con como máximo k desajustes en el tiempo, donde z es el número de aciertos. ^[19] ${\displaystyle O(kn+z)}$
• Encuentre todos los palíndromos máximos en , ^[20] o en el tiempo si se permiten espacios de longitud o si se permiten discrepancias. ^[21] ${\displaystyle z}$ ${\displaystyle \Theta (n)}$ ${\displaystyle \Theta (gn)}$ ${\displaystyle g}$ ${\displaystyle \Theta (kn)}$ ${\displaystyle k}$
• Encuentre todas las repeticiones en tándem en y k -repeticiones en tándem no coincidentes en . ^[22] ${\displaystyle z}$ ${\displaystyle O(n\log n+z)}$ ${\displaystyle O(kn\log(n/k)+z)}$
• Encuentre las subcadenas comunes más largas para al menos cadenas en el tiempo . ^[23] ${\displaystyle k}$ ${\displaystyle D}$ ${\displaystyle k=2,\dots ,K}$ ${\displaystyle \Theta (n)}$
• Encuentre la subcadena palindrómica más larga de una cadena determinada (usando el árbol de sufijos generalizado de la cadena y su reverso) en tiempo lineal. ^[24]

Aplicaciones

Los árboles de sufijos se pueden utilizar para resolver una gran cantidad de problemas de cadenas que ocurren en la edición de texto, la búsqueda de texto libre, la biología computacional y otras áreas de aplicación. ^[25] Las aplicaciones principales incluyen: ^[25]

• Búsqueda de cadenas , en complejidad O ( m ), donde m es la longitud de la subcadena (pero con el tiempo O ( n ) inicial necesario para construir el árbol de sufijos para la cadena)
• Encontrar la subcadena repetida más larga
• Encontrar la subcadena común más larga
• Encontrar el palíndromo más largo de una cuerda

Los árboles de sufijos se utilizan a menudo en aplicaciones bioinformáticas para buscar patrones en secuencias de ADN o proteínas (que pueden verse como largas cadenas de caracteres). La capacidad de buscar eficientemente con discrepancias podría considerarse su mayor fortaleza. Los árboles de sufijos también se utilizan en la compresión de datos ; se pueden usar para encontrar datos repetidos y para la etapa de clasificación de la transformada de Burrows-Wheeler . Las variantes de los esquemas de compresión LZW utilizan árboles de sufijos ( LZSS ). Un árbol de sufijos también se utiliza en la agrupación de árboles de sufijos , un algoritmo de agrupación de datos utilizado en algunos motores de búsqueda. ^[26]

Implementación

Si cada nodo y borde se puede representar en el espacio, el árbol completo se puede representar en el espacio. La longitud total de todas las cadenas en todos los bordes del árbol es , pero cada borde se puede almacenar como la posición y longitud de una subcadena de S , lo que proporciona un uso total del espacio de las palabras de computadora. El peor uso del espacio de un árbol de sufijos se ve con una palabra de Fibonacci , que proporciona los nodos completos . ${\displaystyle \Theta (1)}$ ${\displaystyle \Theta (n)}$ ${\displaystyle O(n^{2})}$ ${\displaystyle \Theta (n)}$ ${\displaystyle 2n}$

Una elección importante al implementar un árbol de sufijos son las relaciones padre-hijo entre nodos. Lo más común es utilizar listas enlazadas llamadas listas de hermanos . Cada nodo tiene un puntero a su primer hijo y al siguiente nodo de la lista de hijos del que forma parte. Otras implementaciones con propiedades de tiempo de ejecución eficientes utilizan mapas hash , matrices ordenadas o no ordenadas (con duplicación de matrices ) o árboles de búsqueda equilibrados . Estamos interesados ​​en:

• El costo de encontrar al niño en un personaje determinado.
• El costo de insertar un niño.
• El costo de alistar a todos los hijos de un nodo (dividido por el número de hijos en la siguiente tabla).

Sea σ el tamaño del alfabeto. Entonces tienes los siguientes costos:

El costo de inserción se amortiza y los costos de hash se dan para un hash perfecto.

La gran cantidad de información en cada borde y nodo hace que el árbol de sufijos sea muy costoso, consumiendo entre 10 y 20 veces el tamaño de memoria del texto fuente en buenas implementaciones. La matriz de sufijos reduce este requisito a un factor de 8 (para matrices que incluyen valores LCP creados dentro de un espacio de direcciones de 32 bits y caracteres de 8 bits). Este factor depende de las propiedades y puede llegar a 2 con el uso de caracteres de 4 bytes de ancho ( necesario contener cualquier símbolo en algunos sistemas tipo UNIX , consulte wchar_t ) en sistemas de 32 bits. Los investigadores han seguido encontrando estructuras de indexación más pequeñas.

Construcción paralela

Se han propuesto varios algoritmos paralelos para acelerar la construcción del árbol de sufijos. ^{[27] [28] [29] [30] [31]} Recientemente, se ha desarrollado un algoritmo paralelo práctico para la construcción de árboles de sufijos con trabajo (tiempo secuencial) y tramo . El algoritmo logra una buena escalabilidad paralela en máquinas multinúcleo de memoria compartida y puede indexar el genoma humano (aproximadamente 3 GB ) en menos de 3 minutos utilizando una máquina de 40 núcleos. ^[32] ${\displaystyle O(n)}$ ${\displaystyle O(\log ^{2}n)}$

Construcción exterior

Aunque es lineal, el uso de memoria de un árbol de sufijos es significativamente mayor que el tamaño real de la colección de secuencias. Para un texto extenso, la construcción puede requerir enfoques de memoria externa.

Existen resultados teóricos para la construcción de árboles de sufijos en la memoria externa. El algoritmo de Farach-Colton, Ferragina y Muthukrishnan (2000) es teóricamente óptimo, con una complejidad de E/S igual a la de la clasificación. Sin embargo, la complejidad general de este algoritmo ha impedido, hasta ahora, su implementación práctica. ^[33]

Por otro lado, se han realizado trabajos prácticos para construir árboles de sufijos basados ​​en disco que escalan a (pocos) GB/hora. Los métodos más avanzados son TDD, ^[34] TRELLIS, ^[35] DiGeST, ^[36] y B ² ST. ^[37]

TDD y TRELLIS escalan hasta todo el genoma humano, lo que da como resultado un árbol de sufijos basado en disco de un tamaño de decenas de gigabytes. ^{[34] [35]} Sin embargo, estos métodos no pueden manejar de manera eficiente colecciones de secuencias que superen los 3 GB. ^[36] DiGeST funciona significativamente mejor y es capaz de manejar colecciones de secuencias del orden de 6 GB en aproximadamente 6 horas. ^[36]

Todos estos métodos pueden construir eficientemente árboles de sufijos para el caso en que el árbol no cabe en la memoria principal, pero la entrada sí. El método más reciente, B ² ST, ^[37] escala para manejar entradas que no caben en la memoria principal. ERA es un método reciente de construcción de árboles de sufijos paralelos que es significativamente más rápido. ERA puede indexar todo el genoma humano en 19 minutos en una computadora de escritorio de 8 núcleos con 16 GB de RAM. En un clúster Linux simple con 16 nodos (4 GB de RAM por nodo), ERA puede indexar todo el genoma humano en menos de 9 minutos. ^[38]

Ver también

• autómata sufijo

Notas

1. Donald E. Knuth; James H. Morris; Vaughan R. Pratt (junio de 1977). "Coincidencia rápida de patrones en cadenas" (PDF) . Revista SIAM de Computación . 6 (2): 323–350. doi :10.1137/0206024.Aquí: p.339 abajo.
2. Knuth conjeturó en 1970 que el problema no podría resolverse en tiempo lineal. ^[1] En 1973, esto fue refutado por el algoritmo de árbol de sufijos de Weiner (1973).
3. Este término se utiliza aquí para distinguir las estructuras de datos precursoras de Weiner de los árboles de sufijos adecuados como se definió anteriormente y no se consideró antes de McCreight (1976).
4. es decir, con cada rama etiquetada con un solo carácter
5. Consulte Archivo: WeinerB aaaabbbbaaaabbbb.gif y Archivo: WeinerC aaaabbbbaaaabbbb.gif para ver un árbol de ejemplo sin comprimir y su correspondiente comprimido.
6. Giegerich y Kurtz (1997).
7. Gusfield (1999) , p.90.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
8. Gusfield (1999) , páginas 90-91.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
9. Farach (1997).
10. Gusfield (1999) , p.92.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
11. Gusfield (1999) , página 123.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
12. Baeza-Yates y Gonnet (1996).
13. Gusfield (1999) , página 132.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
14. Gusfield (1999) , página 125.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
15. Gusfield (1999) , p.144.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
16. Gusfield (1999) , página 166.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
17. Gusfield (1999) , Capítulo 8.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
18. Gusfield (1999) , página 196.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
19. Gusfield (1999) , página 200.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
20. Gusfield (1999) , página 198.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
21. Gusfield (1999) , p.201.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
22. Gusfield (1999) , página 204.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
23. Gusfield (1999) , página 205.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
24. Gusfield (1999) , págs.197-199.Error de harvtxt: sin destino: CITEREFGusfield1999 ( ayuda )
25. Allison, L. "Árboles de sufijos". Archivado desde el original el 13 de octubre de 2008 . Consultado el 14 de octubre de 2008 .
26. Introducido por primera vez por Zamir y Etzioni (1998).
27. Apostólico et al. (1988).
28. Hariharan (1994).
29. Sahinalp y Vishkin (1994).
30. Farach y Muthukrishnan (1996).
31. Iliopoulos y Rytter (2004).
32. Shun y Blelloch (2014).
33. Smith (2003).
34. Tata, Hankins y Patel (2003).
35. Phoophakdee y Zaki (2007).
36. Barsky y col. (2008).
37. Barsky y col. (2009).
38. Mansour y col. (2011).

Referencias

• Ah, Alfred V .; Hopcroft, John E .; Ullman, Jeffrey D. (1974), El diseño y análisis de algoritmos informáticos , Reading/MA: Addison-Wesley, ISBN 0-201-00029-6.
• Apostólico, A.; Iliopoulos, C.; Landau, GM; Schieber, B.; Vishkin, U. (1988), "Construcción paralela de un árbol de sufijos con aplicaciones", Algorithmica , 3 (1–4): 347–365, doi :10.1007/bf01762122, S2CID  5024136.
• Baeza-Yates, Ricardo A .; Gonnet, Gaston H. (1996), "Búsqueda rápida de texto para expresiones regulares o búsqueda automática en intentos", Journal of the ACM , 43 (6): 915–936, doi : 10.1145/235809.235810 , S2CID  1420298.
• Barsky, Marina; Stege, Ulrike; Thomas, Alex; Upton, Chris (2008), "Un nuevo método para indexar genomas utilizando árboles de sufijos en disco", CIKM '08: Actas de la 17ª Conferencia ACM sobre gestión de la información y el conocimiento (PDF) , Nueva York, NY, EE. UU.: ACM, págs. 649–658.
• Barsky, Marina; Stege, Ulrike; Thomas, Alex; Upton, Chris (2009), "Árboles de sufijos para secuencias genómicas muy grandes", CIKM '09: Actas de la 18ª Conferencia ACM sobre gestión de la información y el conocimiento (PDF) , Nueva York, NY, EE. UU.: ACM.
• Farach, Martin (1997), "Construcción óptima de árboles de sufijos con alfabetos grandes" (PDF) , 38.º Simposio del IEEE sobre fundamentos de la informática (FOCS '97) , págs..
• Farach, Martín ; Muthukrishnan, S. (1996), "Construcción de árbol de sufijos aleatorios en tiempo logarítmico óptimo", Coloquio internacional sobre programación y lenguajes de autómatas (PDF).
• Farach-Colton, Martín ; Ferragina, Paolo; Muthukrishnan, S. (2000), "Sobre la complejidad de clasificación de la construcción de árboles con sufijos", Journal of the ACM , 47 (6): 987–1011, doi : 10.1145/355541.355547 , S2CID  8164822.
• Giegerich, R.; Kurtz, S. (1997), "De Ukkonen a McCreight y Weiner: una visión unificadora de la construcción de árboles de sufijos de tiempo lineal" (PDF) , Algorithmica , 19 (3): 331–353, doi :10.1007/PL00009177, S2CID  18039097 , archivado desde el original (PDF) el 3 de marzo de 2016 , consultado el 13 de julio de 2012.
• Gusfield, Dan (1997), Algoritmos sobre cadenas, árboles y secuencias: informática y biología computacional , Cambridge University Press, ISBN 0-521-58519-8.
• Hariharan, Ramesh (1994), "Construcción óptima de árboles de sufijos paralelos", Simposio ACM sobre teoría de la informática (PDF).
• Iliopoulos, Costas; Rytter, Wojciech (2004), "Sobre transformaciones paralelas de matrices de sufijos en árboles de sufijos", 15º taller de Australasia sobre algoritmos combinatorios , CiteSeerX  10.1.1.62.6715.
• Mansur, Essam; Allam, Amin; Skiadopoulos, Spiros; Kalnis, Panos (2011), "ERA: construcción eficiente de árboles de sufijos paralelos y en serie para cadenas muy largas" (PDF) , Actas de VLDB Endowment , 5 (1): 49–60, arXiv : 1109.6884 , Bibcode : 2011arXiv1109.6884M , doi :10.14778/2047485.2047490, S2CID  7582116.
• McCreight, Edward M. (1976), "Un algoritmo de construcción de árboles de sufijos económicos y espaciales", Journal of the ACM , 23 (2): 262–272, CiteSeerX  10.1.1.130.8022 , doi :10.1145/321941.321946, S2CID  9250303.
• Phoophakdee, Benjarath; Zaki, Mohammed J. (2007), "Indexación de árboles de sufijos basada en disco a escala genómica", SIGMOD '07: Actas de la Conferencia internacional ACM SIGMOD sobre gestión de datos , Nueva York, NY, EE. UU.: ACM, págs. 844, CiteSeerX  10.1.1.81.6031.
• Sahinalp, Cenk; Vishkin, Uzi (1994), "Rotura de simetría para la construcción de árboles de sufijos", Simposio ACM sobre teoría de la computación , doi : 10.1145/195058.195164 , S2CID  5985171
• Smyth, William (2003), Patrones informáticos en cadenas , Addison-Wesley.
• Evita, Julián; Blelloch, Guy E. (2014), "Un algoritmo de árbol cartesiano paralelo simple y su aplicación a la construcción de árboles de sufijos paralelos", Transacciones ACM en computación paralela , 1 : 1–20, doi :10.1145/2661653, S2CID  1912378.
• Tata, Sandeep; Hankins, Richard A.; Patel, Jignesh M. (2003), "Practical Suffix Tree Construction", VLDB '03: Actas de la 30ª Conferencia internacional sobre bases de datos muy grandes (PDF) , Morgan Kaufmann, págs..
• Ukkonen, E. (1995), "Construcción en línea de árboles de sufijos" (PDF) , Algorithmica , 14 (3): 249–260, doi :10.1007/BF01206331, S2CID  6027556.
• Weiner, P. (1973), "Algoritmos de coincidencia de patrones lineales" (PDF) , 14º Simposio anual del IEEE sobre teoría de conmutación y autómatas , págs. 1-11, doi :10.1109/SWAT.1973.13, archivado desde el original (PDF) en 03/03/2016 , consultado el 16 de abril de 2015.
• Zamir, Oren; Etzioni, Oren (1998), "Agrupación de documentos web: una demostración de viabilidad", SIGIR '98: Actas de la 21ª conferencia internacional anual ACM SIGIR sobre investigación y desarrollo en recuperación de información , Nueva York, NY, EE. UU.: ACM, págs.46 –54, CiteSeerX  10.1.1.36.4719.

enlaces externos

• Árboles de sufijos de Sartaj Sahni
• Diccionario de algoritmos y estructuras de datos del NIST: árbol de sufijos
• Compresión universal de datos basada en la transformación de Burrows-Wheeler: teoría y práctica, aplicación de árboles de sufijos en el BWT
• Teoría y práctica de estructuras de datos sucintas, implementación en C++ de un árbol de sufijos comprimidos
• Implementación del árbol de sufijos de Ukkonen en C Parte 1 Parte 2 Parte 3 Parte 4 Parte 5 Parte 6
• Demostración en línea: visualización del árbol de sufijos de Ukkonen