Árbol de sufijos generalizados
En informática , un árbol de sufijos generalizados es un árbol de sufijos para un conjunto de cadenas . Dado el conjunto de cadenas de longitud total , es un árbol de Patricia que contiene todos los sufijos de las cadenas. Se utiliza principalmente en bioinformática . [1]
Puede construirse en tiempo y espacio, y puede usarse para encontrar todas las ocurrencias de una cadena de longitud en el tiempo, que es asintóticamente óptima (asumiendo que el tamaño del alfabeto es constante [2] : 119 ).
Al construir un árbol de este tipo, cada cadena debe rellenarse con un símbolo de marcador (o cadena) único fuera del alfabeto para garantizar que ningún sufijo sea una subcadena de otro, garantizando que cada sufijo esté representado por un nodo hoja único.
Los algoritmos para construir un GST incluyen el algoritmo de Ukkonen (1995) y el algoritmo de McCreight (1976).
Un árbol de sufijos para las cadenas ABABy BABAse muestra en una figura de arriba. Están acolchados con las exclusivas cadenas de terminación $0y $1. Los números en los nodos hoja son el número de cadena y la posición inicial. Observe cómo un recorrido de izquierda a derecha de los nodos hoja corresponde al orden de clasificación de los sufijos. Los terminadores pueden ser cadenas o símbolos únicos únicos. Los bordes $desde la raíz se omiten en este ejemplo.
Una alternativa a la construcción de un árbol de sufijos generalizados es concatenar las cadenas y construir un árbol de sufijos regular o una matriz de sufijos para la cadena resultante. Cuando se evalúan los aciertos después de una búsqueda, las posiciones globales se mapean en documentos y posiciones locales con algún algoritmo y / o estructura de datos, como una búsqueda binaria en las posiciones inicial / final de los documentos.
