En informática , un árbol de sufijos (también llamado árbol PAT o, en una forma anterior, árbol de posición ) es un trie comprimido que contiene todos los sufijos del texto dado como sus claves y posiciones en el texto como sus valores. Los árboles de sufijos permiten implementaciones particularmente rápidas de muchas operaciones importantes de cadenas.
La construcción de tal árbol para la cuerda. toma tiempo y espacio lineal en la longitud de . Una vez construido, se pueden realizar varias operaciones rápidamente, por ejemplo, ubicar una subcadena en, ubicar una subcadena si se permite un cierto número de errores, ubicar coincidencias para un patrón de expresión regular , etc. Los árboles de sufijos también proporcionan una de las primeras soluciones de tiempo lineal para el problema de subcadenas común más largo . Estas aceleraciones tienen un costo: almacenar el árbol de sufijos de una cadena generalmente requiere mucho más espacio que almacenar la cadena en sí.
Definición
El árbol de sufijos de la cadena de longitud se define como un árbol tal que: [1]
- El árbol tiene exactamente n hojas numeradas de a .
- A excepción de la raíz, cada nodo interno tiene al menos dos hijos.
- Cada borde está etiquetado con una subcadena no vacía de .
- No hay dos bordes que comiencen en un nodo que puedan tener etiquetas de cadena que comiencen con el mismo carácter.
- La cadena obtenida al concatenar todas las etiquetas de cadena que se encuentran en la ruta de la raíz a la hoja deletrea el sufijo , por de a .
Dado que tal árbol no existe para todas las cadenas, se rellena con un símbolo de terminal que no se ve en la cadena (normalmente se indica $
). 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 . Dado que todos los nodos internos no raíz se ramifican, puede haber como máximo n - 1 de dichos nodos, y n + ( n - 1) + 1 = 2 n nodos en total ( n hojas, n - 1 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 sufijos completo, todos los nodos internos no raíz tienen un enlace de sufijo a otro nodo interno. Si la ruta de la raíz a un nodo deletrea la cadena, dónde es un solo carácter y es una cadena (posiblemente vacía), tiene un enlace de sufijo al nodo interno que representa . Consulte, por ejemplo, el enlace de sufijo del nodo para ANA
al nodo para NA
en la figura anterior. Los enlaces de sufijo también se utilizan en algunos algoritmos que se ejecutan en el árbol.
Un árbol de sufijos generalizados es un árbol de sufijos hecho 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.
Historia
El concepto fue introducido por primera vez por Weiner (1973) . En lugar del sufijo S [ i .. n ], Weiner almacenada en su trie [2] el prefijo identificador para cada posición, es decir, la cadena más corta a partir de i y que ocurre sólo una vez en S . Su algoritmo D toma un trie [3] sin comprimir para S [ k +1 .. n ] y lo extiende a un trie para S [ k .. n ]. De esta manera, partiendo del trivial trivial para S [ n .. n ], se puede construir un trio para S [1 .. n ] mediante n -1 llamadas sucesivas al algoritmo D; sin embargo, el tiempo de ejecución total es O ( n 2 ). 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. Este último todavía puede ser O ( n 2 ) nodos, por ejemplo, para S = a n b n a n b n $. El algoritmo C de Weiner finalmente usa intentos comprimidos para lograr un tamaño de almacenamiento general lineal y tiempo de ejecución. [4] Donald Knuth posteriormente caracterizó a este último como "Algoritmo del año 1973". [ cita requerida ] 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 de todos los sufijos de (comprimido) S . Aunque el sufijo que comienza en i 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.
Ukkonen (1995) simplificó aún más la construcción. [5] 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. 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) dio 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 tanto árboles de sufijos como matrices de sufijos , por ejemplo, en memoria externa, comprimida, sucinta, etc.
Funcionalidad
Un árbol de sufijos para una cadena de longitud se puede construir en tiempo, si las letras provienen de un alfabeto de números enteros en un rango polinomial (en particular, esto es cierto para los alfabetos de tamaño constante). [6] Para alfabetos más grandes, el tiempo de ejecución se domina al ordenar primero las letras para llevarlas a un rango de tamaño.; en general, esto requierehora. Los costos a continuación se dan bajo el supuesto de que el alfabeto es constante.
Suponga que se ha construido un árbol de sufijos para la cadena de longitud , o que se ha construido un árbol de sufijos generalizados para el conjunto de cadenas de longitud total . Usted puede:
- Buscar cadenas:
- Compruebe si una cuerda de longitud es una subcadena en hora. [7]
- Encuentra la primera aparición de los patrones de longitud total como subcadenas en hora.
- Encuentra todos ocurrencias de los patrones de longitud total como subcadenas en hora. [8]
- Busque una expresión regular P en el tiempo esperado sublineal en. [9]
- Encuentra para cada sufijo de un patrón , la longitud de la coincidencia más larga entre un prefijo de y una subcadena en en hora. [10] Esto se denomina estadísticas coincidentes para.
- Encuentra propiedades de las cadenas:
- Encuentra las subcadenas comunes más largas de la cadena y en hora. [11]
- Encuentre todos los pares máximos , repeticiones máximas o repeticiones supermáximas enhora. [12]
- Encuentre la descomposición de Lempel-Ziv enhora. [13]
- Encuentre las subcadenas repetidas más largas en hora.
- Encuentre las subcadenas que ocurren con mayor frecuencia de una longitud mínima en hora.
- Encuentra las cadenas más cortas de que no ocurren en , en tiempo, si hay tales cadenas.
- Encuentre las subcadenas más cortas que ocurren solo una vez en hora.
- Encuentra, para cada , las subcadenas más cortas de no ocurre en ningún otro lugar en en hora.
El árbol de sufijos se puede preparar para la recuperación del ancestro común más bajo en tiempo constante entre nodos enhora. [14] Entonces también se puede:
- Encuentra el prefijo común más largo entre los sufijos y en . [15]
- Busque un patrón P de longitud m con como máximo k desajustes entiempo, donde z es el número de aciertos. [dieciséis]
- Encuentra todos palíndromos máximos en, [17] o tiempo si espacios de longitud están permitidos, o Si se permiten los desajustes. [18]
- Encuentra todos tándem se repite en, y k -mismatch se repite en tándem en. [19]
- Encuentre las subcadenas comunes más largas para al menos cadenas en por en hora. [20]
- Encuentre la subcadena palindrómica más larga de una cuerda dada (usando el árbol de sufijos generalizados de la cuerda y su reverso) en tiempo lineal. [21]
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. [22] Las aplicaciones principales incluyen: [22]
- Búsqueda de cadenas , en complejidad O (m) , donde m es la longitud de la subcadena (pero con el 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 de una cuerda
Los árboles de sufijos se utilizan a menudo en aplicaciones bioinformáticas , 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 usar para buscar 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 que se utiliza en algunos motores de búsqueda. [23]
Implementación
Si cada nodo y borde se puede representar en espacio, todo el árbol se puede representar en espacio. La longitud total de todas las cuerdas en todos los bordes del árbol es, pero cada borde se puede almacenar como la posición y la longitud de una subcadena de S , dando un uso total del espacio depalabras de computadora. El uso de espacio en el peor de los casos de un árbol de sufijos se ve con una palabra de fibonacci , dando el nodos.
Una elección importante al realizar una implementación de árbol de sufijos son las relaciones padre-hijo entre los nodos. La más común es usar listas vinculadas 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 enlistar a todos los hijos de un nodo (dividido por el número de hijos en la tabla a continuación).
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 caro, consumiendo entre 10 y 20 veces el tamaño de la memoria del texto fuente en buenas implementaciones. La matriz de sufijos reduce este requisito a un factor de 8 (para la matriz que incluye valores LCP construidos 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 para contener cualquier símbolo en algunos sistemas similares a 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. [24] [25] [26] [27] [28] Recientemente, un práctico algoritmo paralelo para la construcción de árboles de sufijos con trabajo (tiempo secuencial) y span ha sido desarrollado. 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. [29]
Construcción externa
Aunque 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 grande, 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 & 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. [30]
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, [31] TRELLIS, [32] DiGeST, [33] y B 2 ST. [34]
TDD y TRELLIS escalan a todo el genoma humano, lo que da como resultado un árbol de sufijos basado en disco de un tamaño de decenas de gigabytes. [31] [32] Sin embargo, estos métodos no pueden manejar de manera eficiente colecciones de secuencias que excedan los 3GB. [33] DiGeST funciona significativamente mejor y es capaz de manejar colecciones de secuencias del orden de 6 GB en aproximadamente 6 horas. [33] . Todos estos métodos pueden construir árboles de sufijos de manera eficiente para el caso en que el árbol no cabe en la memoria principal, pero la entrada sí. El método más reciente, B 2 ST, [34] escala para manejar entradas que no caben en la memoria principal. ERA es un método reciente de construcción de árbol 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 de Linux simple con 16 nodos (4 GB de RAM por nodo), ERA puede indexar todo el genoma humano en menos de 9 minutos. [35]
Ver también
- Matriz de sufijo
- Autómata de sufijo
- Árbol de sufijos generalizados
- Trie
Notas
- ^ http://www.cs.uoi.gr/~kblekas/courses/bioinformatics/Suffix_Trees1.pdf [ enlace muerto permanente ]
- ^ Este término se utiliza aquí para distinguir las estructuras de datos precursoras de Weiner de los árboles de sufijos adecuados como se definieron anteriormente y no se consideraron antes de McCreight (1976) .
- ^ es decir, con cada rama etiquetada por un solo carácter
- ^ Consulte Archivo: WeinerB aaaabbbbaaaabbbb.gif y Archivo: WeinerC aaaabbbbaaaabbbb.gif para ver un árbol de ejemplo sin comprimir y su correspondiente comprimido.
- ^ Giegerich y Kurtz (1997) .
- ^ Farach (1997) .
- ^ Gusfield (1999) , p. 92.
- ^ Gusfield (1999) , p.123.
- ^ Baeza-Yates y Gonnet (1996) .
- ^ Gusfield (1999) , p.132.
- ^ Gusfield (1999) , p.125.
- ^ Gusfield (1999) , p.144.
- ^ Gusfield (1999) , p.166.
- ^ Gusfield (1999) , Capítulo 8.
- ^ Gusfield (1999) , p. 196.
- ↑ Gusfield (1999) , p. 200.
- ^ Gusfield (1999) , p.198.
- ^ Gusfield (1999) , p.201.
- ^ Gusfield (1999) , p.204.
- ^ Gusfield (1999) , p.205.
- ^ Gusfield (1999) , págs. 197-199.
- ^ a b Allison, L. "Árboles de sufijo" . Archivado desde el original el 13 de octubre de 2008 . Consultado el 14 de octubre de 2008 .
- ^ Introducido por primera vez por Zamir y Etzioni (1998) .
- ^ Apostolico et al. (1988) .
- ^ Hariharan (1994) .
- ^ Sahinalp y Vishkin (1994) .
- ^ Farach y Muthukrishnan (1996) .
- ^ Iliopoulos y Rytter (2004) .
- ^ Shun y Blelloch (2014) .
- ^ Smyth (2003) .
- ↑ a b Tata, Hankins y Patel (2003) .
- ↑ a b Phoophakdee y Zaki (2007) .
- ^ a b c Barsky y col. (2008) .
- ^ a b Barsky y col. (2009) .
- ^ Mansour y col. (2011) .
Referencias
- 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.
- 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 usando árboles de sufijos en disco", CIKM '08: Actas de la 17a Conferencia de ACM sobre Gestión de la Información y el Conocimiento , Nueva York, NY, EE. UU.: ACM, págs. 649 –658.
- Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2009), "Árboles de sufijo para secuencias genómicas muy grandes", CIKM '09: Actas de la 18a Conferencia de ACM sobre Gestión de la Información y el Conocimiento , Nueva York, NY, EE. UU.: ACM.
- Farach, Martin (1997), "Optimal Suffix Tree Construction with Large Alphabets" (PDF) , 38º Simposio IEEE sobre Fundamentos de las Ciencias de la Computación (FOCS '97) , págs. 137–143.
- Farach, Martin ; Muthukrishnan, S. (1996), "Optimal Logarithmic Time Randomized Suffix Tree Construction", Coloquio internacional sobre lenguajes y programación de autómatas.
- Farach-Colton, Martin ; Ferragina, Paolo; Muthukrishnan, S. (2000), "Sobre la complejidad de clasificación de la construcción de árboles de sufijos". , Journal of the ACM , 47 (6): 987–1011, doi : 10.1145 / 355541.355547 , S2CID 8164822.
- Giegerich, R .; Kurtz, S. (1997), "From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction" (PDF) , Algorithmica , 19 (3): 331–353, doi : 10.1007 / PL00009177 , archivado de el original (PDF) el 2016-03-03 , consultado el 2012-07-13.
- Gusfield, Dan (1999), Algoritmos sobre cadenas, árboles y secuencias: informática y biología computacional , Cambridge University Press, ISBN 0-521-58519-8.
- Hariharan, Ramesh (1994), "Optimal Parallel Suffix Tree Construction", Simposio ACM sobre Teoría de la Computación.
- Iliopoulos, Costas; Rytter, Wojciech (2004), "Sobre transformaciones paralelas de matrices de sufijos en árboles de sufijos", 15º Taller de Australasia sobre algoritmos combinatorios.
- Mansour, Essam; Allam, Amin; Skiadopoulos, Spiros; Kalnis, Panos (2011), "ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings" (PDF) , Proceedings of the VLDB Endowment , 5 (1): 49–60, arXiv : 1109.6884 , Bibcode : 2011arXiv1109.6884M , doi : 10.14778 / 2047485.2047490.
- McCreight, Edward M. (1976), "A Space-Economic Suffix Tree Construction Algorithm", Journal of the ACM , 23 (2): 262-272, CiteSeerX 10.1.1.130.8022 , doi : 10.1145 / 321941.321946.
- Phoophakdee, Benjarath; Zaki, Mohammed J. (2007), "Indexación de árbol 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. 833– 844.
- Sahinalp, Cenk; Vishkin, Uzi (1994), "Romper la simetría para la construcción de árboles de sufijos", Simposio ACM sobre Teoría de la Computación
- Smyth, William (2003), Computación de patrones en cuerdas , Addison-Wesley.
- Shun, Julian; Blelloch, Guy E. (2014), "A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction" , ACM Transactions on Parallel Computing , 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 , 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.
- Weiner, P. (1973), "Algoritmos de coincidencia de patrones lineales" (PDF) , XIV Simposio Anual de IEEE sobre Teoría de Conmutación y Autómatas , págs. 1-11, doi : 10.1109 / SWAT.1973.13.
- 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 la recuperación de información , Nueva York, NY, EE. UU .: ACM, págs. 46 –54.
enlaces externos
- Árboles de sufijo de Sartaj Sahni
- Diccionario de NIST de algoritmos y estructuras de datos: árbol de sufijos
- Compresión de datos universal 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 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