Árbol de sufijos generalizado

En la informática, una árbol de sufijo generalizado es un árbol de sufijo para un conjunto de cuerdas. Dado el conjunto de cuerdas ${\displaystyle D=S_{1},S_{2},\dotsS_{d}$ de longitud total ${\displaystyle n}$, es un árbol de Patricia que contiene todo ${\displaystyle n}$ sufijos de las cuerdas. Se utiliza principalmente en bioinformática.

Funcionalidad

Se puede construir en ${\displaystyle \Theta (n)}$ tiempo y espacio, y se puede utilizar para encontrar todo ${\displaystyle z}$ ocurrencias de una cadena ${\displaystyle P}$ de longitud ${\displaystyle m}$ dentro ${\displaystyle O(m+z)}$ tiempo, que es asintomáticamente óptimo (asumiendo el tamaño del alfabeto es constante).

Al construir un árbol de este tipo, cada cadena debe rellenarse con un símbolo (o cadena) marcador ú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).

Ejemplo

En la figura anterior se muestra un árbol de sufijos para las cadenas ABAB y BABA. Están rellenados con las cadenas de terminación únicas $0 y $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 de hoja corresponde al orden de los sufijos. Los terminadores pueden ser cadenas o símbolos únicos y únicos. En este ejemplo se omiten los bordes en $ desde la raíz.

Alternativas

Una alternativa a la creación de un árbol de sufijos generalizado es concatenar las cadenas y crear un árbol de sufijos regular o una matriz de sufijos para la cadena resultante. Cuando se evalúan los resultados después de una búsqueda, las posiciones globales se asignan a 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.