Árbol de sufijos

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 importantes con cadenas.

La construcción de un árbol de este tipo para la cadena requiere tiempo y espacio lineales en la longitud de . Una vez construido, se pueden realizar varias operaciones rápidamente, como localizar una subcadena en , localizar una subcadena si se permite una cierta cantidad de errores y localizar coincidencias para un patrón de expresión regular . Los árboles de sufijos también proporcionaron una de las primeras soluciones en tiempo lineal para el problema de la subcadena común más larga . ^[2] Estas aceleraciones tienen un costo: almacenar el árbol de sufijos de una cadena generalmente requiere significativamente más espacio que almacenar la cadena en sí.${\estilo de visualización S}$${\estilo de visualización S}$${\estilo de visualización S}$

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 aparece solo una vez en . Su algoritmo D toma un trie sin comprimir ^[4] para y lo extiende en un trie para . De esta manera, comenzando desde el trie trivial para , se puede construir un trie para 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 general lineal en el tamaño del trie construido. Estos últimos aún pueden ser nodos, por ejemplo, para el algoritmo C de Weiner finalmente usa tries comprimidos para lograr un tamaño de almacenamiento general y un tiempo de ejecución lineales. ^[5] Donald Knuth posteriormente caracterizó a este último como "Algoritmo del año 1973" según su estudiante Vaughan Pratt . ^{[ investigación 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]}$${\estilo de visualización i}$${\estilo de visualización S}$${\displaystyle S[k+1..n]}$${\displaystyle S[k..n]}$${\displaystyle S[n..n]}$${\displaystyle S[1..n]}$${\estilo de visualización 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 del prefijo, sus representaciones de ruta en un trie comprimido no difieren en tamaño. Por otro lado, McCreight pudo prescindir de la mayoría de las estructuras de datos auxiliares de Weiner; solo quedaron los enlaces de sufijos.${\estilo de visualización S}$${\estilo de visualización 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 la época. Estos algoritmos son todos de tiempo lineal para un alfabeto de tamaño constante y tienen un tiempo de ejecución en el peor de los casos de en general.${\displaystyle O(n\log n)}$

Farach (1997) presentó el primer algoritmo de construcción de árboles 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 tanto árboles de sufijos como matrices de sufijos , por ejemplo, en memoria externa, comprimidos, sucintos, etc.

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

1. El árbol tiene exactamente n hojas numeradas del a .${\estilo de visualización 1}$${\estilo de visualización n}$
2. A excepción de la raíz, cada nodo interno tiene al menos dos hijos.
3. Cada borde está etiquetado con una subcadena no vacía de .${\estilo de visualización S}$
4. No es posible que dos aristas que comiencen desde un nodo tengan 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 la ruta desde la raíz hasta la hoja deletrea sufijo , para desde hasta .${\estilo de visualización i}$${\displaystyle S[i..n]}$${\estilo de visualización i}$${\estilo de visualización 1}$${\estilo de visualización 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 es también un prefijo del sufijo bcbc . En tal caso, la ruta que deletrea bc no terminará en una hoja, violando la quinta regla. Para solucionar este problema, se rellena con un símbolo terminal que no se ve en la cadena (generalmente denotado ). Esto asegura que ningún sufijo sea un prefijo de otro, y que habrá nodos de hoja, uno para cada uno de los sufijos de . ^[8] Dado que todos los nodos internos no raíz se ramifican, puede haber como máximo dichos nodos, y nodos en total ( hojas, nodos internos no raíz, 1 raíz).${\estilo de visualización S}$${\estilo de visualización S}$$${\estilo de visualización n}$${\estilo de visualización n}$${\estilo de visualización S}$${\estilo de visualización n-1}$${\displaystyle n+(n-1)+1=2n}$${\estilo de visualización n}$${\estilo de visualización n-1}$

Los enlaces de sufijo 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 sufijo. En un árbol de sufijo 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 para al nodo para en la figura anterior. Los enlaces de sufijo también se utilizan en algunos algoritmos que se ejecutan en el árbol.${\displaystyle \chi \alpha}$${\estilo de visualización \chi}$${\estilo de visualización \alpha}$${\estilo de visualización \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.

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 la primera clasificación de las letras para llevarlas a 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.${\estilo de visualización S}$${\estilo de visualización n}$${\displaystyle \Theta (n)}$${\displaystyle O(n)}$${\displaystyle O(n\log n)}$

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

• Buscar cadenas:
  • Comprueba si una cadena de longitud es una subcadena en el tiempo. ^[10]${\estilo de visualización P}$${\estilo de visualización m}$${\displaystyle O(m)}$
  • Encuentre la primera aparición de los patrones de longitud total como subcadenas en el tiempo.${\displaystyle P_{1},\puntos ,P_{q}}$${\estilo de visualización m}$${\displaystyle O(m)}$
  • Encuentre todas las ocurrencias de los patrones de longitud total como subcadenas en el tiempo. ^[11]${\estilo de visualización z}$${\displaystyle P_{1},\puntos ,P_{q}}$${\estilo de visualización m}$${\displaystyle O(m+z)}$
  • Búsqueda de una expresión regular P en el tiempo sublineal esperado en . ^[12]${\estilo de visualización 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 en el tiempo. ^[13] Esto se denomina estadísticas de coincidencia para .${\estilo de visualización P}$${\displaystyle P[i\puntos m]}$${\estilo de visualización D}$${\displaystyle \Theta (m)}$${\estilo de visualización P}$
• Encuentra propiedades de las cadenas:
  • Encuentra las subcadenas comunes más largas de la cadena y en el tiempo. ^[14]$Estilo de visualización S_{i}}$$Estilo de visualización 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]$Estilo de visualización: \Theta (n+z)$
  • Encuentra la descomposición de Lempel-Ziv en el tiempo. ^[16]${\displaystyle \Theta (n)}$
  • Encuentra las subcadenas repetidas más largas en el tiempo.${\displaystyle \Theta (n)}$
  • Encuentre las subcadenas que aparecen con mayor frecuencia y tienen una longitud mínima en el tiempo.${\displaystyle \Theta (n)}$
  • Encuentra las cadenas más cortas de que no ocurren en , en el tiempo, si existen tales cadenas.${\estilo de visualización \Sigma}$${\estilo de visualización D}$${\displaystyle O(n+z)}$${\estilo de visualización z}$
  • Encuentre las subcadenas más cortas que ocurren solo una vez en el tiempo.${\displaystyle \Theta (n)}$
  • Encuentra, para cada , las subcadenas más cortas de que no aparecen en ningún otro lugar en el tiempo.${\estilo de visualización i}$$Estilo de visualización S_{i}}$${\estilo de visualización 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] Luego también se puede:${\displaystyle \Theta (n)}$

• Encuentra 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)}$
• Búsqueda de 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 tiempo si se permiten espacios de longitud , o si se permiten desajustes. ^[21]${\estilo de visualización z}$${\displaystyle \Theta (n)}$${\displaystyle \Theta (gn)}$${\estilo de visualización g}$${\displaystyle \Theta(kn)}$${\estilo de visualización k}$
• Encuentre todas las repeticiones en tándem en , y las repeticiones en tándem con k desajustes en . ^[22]${\estilo de visualización z}$ ${\displaystyle O(n\log n+z)}$${\displaystyle O(kn\log(n/k)+z)}$
• Encuentra las subcadenas comunes más largas a al menos cadenas en for en el tiempo. ^[23]${\estilo de visualización k}$${\estilo de visualización D}$${\displaystyle k=2,\puntos ,K}$${\displaystyle \Theta (n)}$
• Encuentra la subcadena palindrómica más larga de una cadena dada (utilizando el árbol de sufijos generalizado de la cadena y su inverso) en tiempo lineal. ^[24]

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 un tiempo inicial O ( n ) requerido 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 en una cadena

Los árboles de sufijos se utilizan a menudo en aplicaciones de bioinformática , buscando patrones en secuencias de ADN o proteínas (que pueden verse como largas cadenas de caracteres). La capacidad de buscar de manera eficiente con desajustes podría considerarse su mayor fortaleza. Los árboles de sufijos también se utilizan en la compresión de datos ; se pueden utilizar para encontrar datos repetidos y se pueden utilizar 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]

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

Una elección importante al realizar una implementación de árbol de sufijos son las relaciones padre-hijo entre nodos. La más común es el uso de listas enlazadas llamadas listas hermanas . Cada nodo tiene un puntero a su primer hijo y al siguiente nodo en la lista de hijos de la 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 balanceados . Estamos interesados ​​en:

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

Sea σ el tamaño del alfabeto. Entonces, tienes los siguientes costos: ^{[ cita requerida ]}

El coste de inserción se amortiza y los costes 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 aproximadamente de 10 a 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 (necesarios para contener cualquier símbolo en algunos sistemas tipo UNIX , consulte wchar_t ) en sistemas de 32 bits. ^{[ cita requerida ]} Los investigadores han seguido encontrando estructuras de indexación más pequeñas.

Se han propuesto varios algoritmos paralelos para acelerar la construcción de árboles 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 duración . El algoritmo logra una buena escalabilidad paralela en máquinas multinúcleo con 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)}$

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 métodos 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 ordenación. Sin embargo, la complejidad general de este algoritmo ha impedido, hasta ahora, su implementación práctica. ^[33]

Por otra parte, se han realizado trabajos prácticos para construir árboles de sufijos basados ​​en discos que escalan a (pocos) GB/hora. Los métodos de última generación son TDD, ^[34] TRELLIS, ^[35] DiGeST, ^[36] y B ² ST. ^[37]

TDD y TRELLIS escalan hasta el genoma humano completo, lo que da como resultado un árbol de sufijos basado en discos 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 puede 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 quepa en la memoria principal, pero la entrada sí. El método más reciente, B ² ST, ^[37] se escala para manejar entradas que no caben en la memoria principal. ERA es un método reciente de construcción de árboles de sufijos en paralelo 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]

• Autómata de sufijo

• Aho, 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.
• Apostolico, 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; Thomo, Alex; Upton, Chris (2008), "Un nuevo método para indexar genomas utilizando árboles de sufijos en disco", CIKM '08: Actas de la 17.ª Conferencia de la 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; Thomo, Alex; Upton, Chris (2009), "Árboles de sufijos para secuencias genómicas muy grandes", CIKM '09: Actas de la 18.ª Conferencia de la 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 IEEE sobre fundamentos de la informática (FOCS '97) , págs. 137-143.
• Farach, Martin ; Muthukrishnan, S. (1996), "Construcción de árboles de sufijos aleatorios en tiempo logarítmico óptimo", Coloquio internacional sobre lenguajes autómatas y programación (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 en tiempo lineal" (PDF) , Algorithmica , 19 (3): 331–353, doi :10.1007/PL00009177, S2CID  18039097, archivado desde el original (PDF) el 2016-03-03 , consultado el 2012-07-13.
• 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 computación (PDF).
• Iliopoulos, Costas; Rytter, Wojciech (2004), "Sobre transformaciones paralelas de matrices de sufijos en árboles de sufijos", 15.º Taller Australasiano sobre algoritmos combinatorios , CiteSeerX  10.1.1.62.6715.
• Mansour, Essam; Allam, Amin; Skiadopoulos, Spiros; Kalnis, Panos (2011), "ERA: Construcción eficiente de árboles de sufijos seriales y paralelos para cadenas muy largas" (PDF) , Actas de la Fundación VLDB , 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 con economía espacial", 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 discos 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. 833–844, CiteSeerX  10.1.1.81.6031.
• Sahinalp, Cenk; Vishkin, Uzi (1994), "Ruptura de simetría para la construcción de árboles de sufijos", Simposio ACM sobre teoría de la computación , págs. 300–309, doi : 10.1145/195058.195164 , ISBN 0-89791-663-8, Número de identificación del sujeto  5985171
• Smyth, William (2003), Cálculo de patrones en cadenas , Addison-Wesley.
• Shun, Julian; Blelloch, Guy E. (2014), "Un algoritmo de árbol cartesiano paralelo simple y su aplicación a la construcción de árboles de sufijos paralelos", ACM Transactions on Parallel Computing , 1 : 1–20, doi :10.1145/2661653, S2CID  1912378.
• Tata, Sandeep; Hankins, Richard A.; Patel, Jignesh M. (2003), "Construcción práctica de árboles de sufijos", VLDB '03: Actas de la 30.ª Conferencia internacional sobre bases de datos muy grandes (PDF) , Morgan Kaufmann, págs. 36–47.
• 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 IEEE sobre conmutación y teoría de autómatas , págs. 1–11, doi :10.1109/SWAT.1973.13, archivado desde el original (PDF) el 2016-03-03 , consultado el 2015-04-16.
• Zamir, Oren; Etzioni, Oren (1998), "Agrupamiento de documentos web: una demostración de viabilidad", SIGIR '98: Actas de la 21.ª conferencia anual internacional 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.

• Á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 la BWT
• Teoría y práctica de estructuras de datos sucintas, implementación en C++ de un árbol de sufijos comprimido
• 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