Los árboles de sufijos y sus Aplicaciones

Los árboles de sufijos y sus Aplicaciones

Cadena De Algoritmos *

Palabras clave : La concordancia de patrones , algoritmos de Cuerda , árbol de sufijos

El árbol de sufijo es una estructura de datos potente y versátil que tiene aplicaciones en muchos algoritmos de cadena [77, 101]. Es básicamente un trie compactado para almacenar los sufijos de una cadena dada, para que todas las subcadenas posibles de la cadena están representadas por algún camino (único) desciende de la raíz. El poder de un árbol del sufijo radica principalmente en su capacidad para codificar todos los sufijos de la cadena dada en el espacio lineal. Esta codificación sucinta permite recuperar una gran cantidad de información del índice: por ejemplo, puede ser utilizado como un diagrama de transiciones de estado de un autómata que reconozca todas las subcadenas de la cadena dada. La importancia del árbol del sufijo es subrayada por el hecho de que se ha redescubierto muchas veces en la literatura científica, disfrazada bajo nombres diferentes, y que ha sido estudiado en numerosas variantes. Sólo para mencionar algunos aspectos del árbol del sufijo, citamos el compactado bi-árbol [101], el árbol de prefijo [24], el árbol PAT [50], el árbol de la posición [3, 65, 75], el buscador de repetición [82] y el árbol de subcadena [8, 24]. La capacidad del árbol del sufijo para representar todas las subcadenas en el espacio lineal ha inspirado diversas variantes. La matriz de sufijo [76], matriz de sufijo de cactus [63], arbol dinámico de sufijo [37], árbol PAT [50] y SB-árbol [38] son ejemplos de arreglos de discos o árboles con los sufijos de la cadena dada en el orden lexicográfico obtenida visitando las hojas del árbol del sufijo correspondiente. El grafo dirigido acíclico palabra (DAWG) y sufijo mínimo y factor de autómatas [16, 28, 30] son gráficos etiquetados o autómatas reconociendo las subcadenas de la cadena dada (o sólo sus sufijos), cuyos nodos pueden ser afines a los del árbol del sufijo en la cadena invertida. El archivo invertido completo [17] es un DAWG compactada que es aumentada con información adicional en los nodos, equivalente a la obtenida del árbol del sufijo de la cadena dada por sus subárboles con borde isomorfo de fusión y eliminar parte de la estructura resultante. En la literatura conocida, una definición implícita del árbol sufijo puede encontrarse ya en árboles de Patricia Morrison [78]. Sin embargo, Weiner fue el primero en introducir explícitamente el árbol del sufijo en [101] (el nombre original fue compactado como bi-árbol). Tras la labor pionera de Weiner, varias construcciones lineales de tiempo y espacio se han dado más tarde como la de McCreight [77], Pratt [82], Slisenko [92] y Chen y Seiferas [24] (algunos de los algoritmos han sido mostrados en [24, 47, 74]). Las construcciones en [24, 101] tienen también la ventaja de ser online, bajo el supuesto de que la cadena de entrada es leída como un carácter a la vez de derecha a izquierda. De izquierda a derecha en línea (aunque no lineal-tiempo) de construcción ha sido descrita por Majster y Reiser [75] y Kempf, Bayer, G¨untzer [65]. Un algoritmo de tiempo lineal en línea ha recibido Ukkonen [99], y una construcción en tiempo real se ha dado por Slisenko [92] y Kosaraju [67]. La mayoría de las construcciones anteriores para las cadenas de un alfabeto grande, al precio de una disminución logarítmica de complejidad de tiempo (en el tamaño del alfabeto). El primer algoritmo paralelo para la construcción del árbol del sufijo ha sido presentado por Landau y Vishkin [70]. Apostolico et al [9] han dado la primera construcción paralela eficiente que tiene trabajo óptimo para un alfabeto grande. Hariharan [57], Sahinalp y Vishkin [86] y Farach Muthukrishnan [35] han ideado construcciones paralelas cuyo trabajo es óptimo también para un alfabeto pequeño. El comportamiento estadístico de árboles de sufijo ha sido estudiado marcos probabilísticos generales y leves por Apostolico y Szpankowski [12], Blumer et al [18], Devroye et al [32], [51] de Grassberger, Jacquet Szpankowski [60], escudos [89] y Szpankowski 2 [94, 95]. Una de las principales propiedades del árbol del sufijo es que su profundidad esperada asintótica es logarítmica en la longitud de la cadena dada, aunque puede ser lineal en el peor de los casos. O ' Connor y Snider [81] han relacionado con una medida de complejidad para las cadenas al azar en Criptología, llamado complejidad de orden máximo, a las propiedades estadísticas de los árboles de sufijo. La noción de árbol del sufijo se ha extendido a matrices cuadradas de Gonnet [48, 49], Giancarlo [43] y Giancarlo y Grossi [46]. Esta estructura de datos puede implementarse eficientemente en un área que está cobrando cada vez mayor interés por sus aplicaciones a procesamiento de imágenes de bajo nivel [85], [93] de compresión de imágenes y bases de datos visuales en sistemas multimedia [62] de algoritmos en dimensiones superiores, de coincidencia de patrón. El problema de la construcción de una estructura de datos del árbol que representa todas las submatrices de una matriz dada ha demostrado ser computacionalmente más duro que el problema de la construcción de una estructura de datos del árbol que representa sólo las submatrices cuadradas [44], y ha sido considerado en [45]. Una definición del árbol del sufijo para árboles etiquetados, guardando los caminos del nodo a la raíz del árbol dado como cadenas en un trie condensado, ha sido introducida por Kosaraju [66] y utilizado también por Dubiner et al [33], para propósitos de coincidencia de patrón del árbol. Otra interesante generalización del árbol de sufijo parametrizando cadenas (o, p-cuerdas) ha sido introducida por Baker [13] para encontrar fragmentos del programa en un sistema de software que son idénticos excepto por un cambio sistemático de parámetros. Los arboles de sufijo encuentran una gran variedad de aplicaciones diferentes áreas, relacionadas con el tratamiento de la cadena, tales como: cadena adecuada [6, 29, 101]; cadena aproximada de coincidencia [23, 42, 71, 72, 79, 98]; búsqueda de subcadenas más repetidas [101]; encontrar plazas [10, 68] y repeticiones de una cadena [10]; Computación estadística para las ocurrencias no superpuestas [11]; encontrar la cadena más larga entre todos los pares de prefijo-sufijo ordenado de un conjunto determinado de cadenas [55]; encontrar la más larga subsecuencia que aparece en h de cadenas k, para todo h ≥ 2 [58]; cadenas características informáticas [59]; una cadena como un trazado arbitrario de un árbol etiquetado neutral [4]; realizar eficiente Diccionario que empareja [6, 5, 7, 21, 43]; esquemas de compresión de datos [39, 40, 73, 83, 84, 102, 103]; búsqueda para el funcionamiento más largo de un determinado motivo en secuencias moleculares [53, 54, 100]; distancia métrica en cadenas [34]; complejidad de medida en secuencias al azar para Criptología [81]; índices invertidos [22]; Análisis de secuencias genéticas [25, 23]; encontrando duplicación en código de programación [13]; generar nombres para programas en tareas de montaje [14]; pruebas de decipherability única para un conjunto de palabras [83]; detección de similitudes de un polígono en reconocimiento de patrones [96]; y así sucesivamente. Este documento analiza algunas aplicaciones de árboles de sufijo y las técnicas algorítmicas para la construcción de esta estructura de datos ubicua. Especial hincapié en los desarrollos más recientes en esta área, tales como algoritmos paralelos para la construcción del árbol del sufijo y generalizacion de árboles de sufijo a dimensiones superiores, que son importantes en la adecuación del modelo multidimensional. El resto de este documento está organizado como sigue. En la sección 2, definimos la estructura de datos del árbol de sufijo y describir algunas de sus aplicaciones. Varios algoritmos para su construcción secuencial se describen en la sección 3. Sección 4 contiene algunas aplicaciones y extensiones de árboles sufijo. Finalmente, la sección 5 contiene algunas observaciones finales. 3 2 el sufijo árbol sea x una cadena de n caracteres de un alfabeto ordenado Σ. Denota x como x [1]. Sea $ un carácter especial, no que ningún carácter en Σ. El árbol del sufijo T de x$ es un trie (árbol de búsqueda digital) que contiene todos los sufijos de x$. El carácter $ es un derecho endmarker, y su objetivo es separar (en T) sufijo x [i:n] de sufijo x [j:n], para i > j, siempre que el primero es un prefijo de este último. Esto se traduce en la existencia de una hoja en T para cada sufijo de x$, ya que los dos sufijos de x$ eventualmente se van sus maneras separadas en T. En consecuencia, cada hoja de T puede ser etiquetada con un número entero distinto de j tales que el camino desde la raíz a la hoja (etiquetada) j corresponde al sufijo x [j:n]. por otra parte, la ruta de la raíz de T a un nodo interno u corresponde a una subsecuencia de x. El número de subcadenas diferentes de x que se codifican en T puede ser bastante grande. En efecto, incluso cadenas utilizando sólo dos caracteres distintos pueden tener tantos como subcadenas diferentes Ω (n 2). Un ejemplo de ello está dada por x = a b n/2 n/2 para a, b ∈ Σ, que tiene (n/2 + 1) 2 distintas subseries de caracteres (incluyendo la subcadena vacía). Sin embargo, hay representaciones del árbol del sufijo compactas (y equivalente) que tienen a lo más 2n nodos, como los definidos por Weiner [101], McCreight [77], Pratt [82] o Slisenko [92]. Una manera obvia para compactar un árbol del sufijo es hacerlo un trie compactado omitiendo los nodos internos de grado uno (también llamados unarios nodos). El tamaño de la representación obtenida en la mayoría es 2n + 1, ya que hay a lo más n + 1 hojas (uno para cada sufijo de x$), y en un árbol sin nodos internos unario, el número de nodos internos está limitado por el número de hojas. Tenga en cuenta que O(n) en lugar de O(n 2) los nodos es fundamental en muchas aplicaciones: por ejemplo si la cadena es una pieza de una secuencia de ADN, puede contener n ≈ 105 caracteres; sin el uso de un árbol del sufijo, necesitamos tantos como células de memoria de n 2 ≈ 1010 para representar todas las subcadenas posibles! Más formalmente, las siguientes restricciones a T limita su tamaño a O(n). (T1) Un arco de T puede almacenar cualquier subcadena no vacío de x$, que se representa como un par de números enteros para indicar su posición inicial y su longitud dentro de x$. (T2) Cada nodo interno de T debe tener al menos dos arcos salientes. (T3) Subcadenas representados por arcos de hermano de T deben comenzar con diferentes personajes. Para cada nodo del árbol de sufijo, sea pathstring cadena obtenido concatenando la secuencia de etiquetas encontradas a lo largo de la ruta de la raíz a ese nodo. Tenga en cuenta que las limitaciones anteriores garantizan que un nodo de árbol del sufijo se puede nombrar sin ambigüedad por su pathstring. Por lo tanto decimos que tal un nodo es el lugar geométrico de una cadena y cada vez que su pathstring es igual a y. Una extensión de una y de la cadena es cualquier secuencia de que y es un prefijo. El lugar geométrico extendido y es el lugar geométrico de la extensión más pequeña de y (incluido) tener lugar geométrico definido. Si y sí tiene lugar geométrico definido, entonces su locus y lugar geométrico extendido coinciden. Ahora ilustramos la definición del árbol del sufijo con un ejemplo. El árbol del sufijo T de la secuencia ω = x$ = bbabab$ está representada en la figura 1. Cadena ω tiene siete sufijos, es decir, bbabab$ $ babab, abab$, $ bab, ab$, b$ y $, que están numeradas del 1 al 7. Mediante el árbol del sufijo, podemos comprobar si una cadena dada es una subcadena de ω. Por ejemplo, el aba es una subcadena de ω ya que tiene lugar geométrico extendido en T. De hecho, existe un nodo en el árbol del sufijo que su pathstring comienza con aba, es decir la hoja 3.

...