stringtranslate.com

Árbol de sufijos

Árbol de sufijos para el texto BANANA. Cada subcadena termina con el carácter especial $. Las seis rutas desde la raíz hasta las hojas (mostradas como cuadros) corresponden a los seis sufijos A$, NA$, ANA$, y . Los números en las hojas indican la posición inicial del sufijo correspondiente. Los enlaces de sufijos, dibujados con líneas discontinuas, se utilizan durante la construcción 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 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í.

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 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 .

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.

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.

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.

Definición

El árbol de sufijos para la cadena de longitud se define como un árbol tal que: [7]

  1. El árbol tiene exactamente n hojas numeradas del a .
  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 .
  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 .

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).$

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.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 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.

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:

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:

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]

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]

Implementación

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.

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:

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.

Construcción paralela

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]

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 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 2 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 2 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]

Véase también

Notas

  1. ^ Donald E. Knuth; James H. Morris; Vaughan R. Pratt (junio de 1977). "Coincidencia rápida de patrones en cadenas" (PDF) . SIAM Journal on Computing . 6 (2): 323–350. doi :10.1137/0206024.Aquí: p.339 abajo.
  2. ^ Knuth conjeturó en 1970 que el problema no podí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, tal como se definieron anteriormente y no se consideraron 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 ejemplo de árbol sin comprimir y su correspondiente comprimido.
  6. ^ ab Giegerich y Kurtz (1997).
  7. ^ Gusfield (1999) , pág. 90.
  8. ^ Gusfield (1999) , págs. 90-91.
  9. ^ Farach (1997).
  10. ^ Gusfield (1999) , pág. 92.
  11. ^ Gusfield (1999) , pág.123.
  12. ^ Baeza-Yates y Gonnet (1996).
  13. ^ Gusfield (1999) , pág.132.
  14. ^ Gusfield (1999) , pág.125.
  15. ^ Gusfield (1999) , pág. 144.
  16. ^ Gusfield (1999) , pág. 166.
  17. ^ Gusfield (1999) , Capítulo 8.
  18. ^ Gusfield (1999) , pág. 196.
  19. ^ Gusfield (1999) , pág. 200.
  20. ^ Gusfield (1999) , pág. 198.
  21. ^ Gusfield (1999) , pág. 201.
  22. ^ Gusfield (1999) , pág. 204.
  23. ^ Gusfield (1999) , pág. 205.
  24. ^ Gusfield (1999) , págs. 197-199.
  25. ^ ab Allison, L. "Suffix Trees". 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. ^ Apostolico y otros (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. ^ Smyth (2003).
  34. ^ por Tata, Hankins y Patel (2003).
  35. ^ ab Phoophakdee y Zaki (2007).
  36. ^ abc Barsky y otros (2008).
  37. ^ desde Barsky y col. (2009).
  38. ^ Mansour y otros (2011).

Referencias

Enlaces externos