Arreglo de sufijos

En Ciencias de la Computación un arreglo de sufijos es un arreglo ordenado de todos los sufijos de una cadena dada. Esta estructura de datos es muy simple, sin embargo es muy poderosa y es usada en algoritmos de compresión de datos y dentro del campo de la bioinformática , indización de textos completos, entre otros.

Los arreglos de sufijos fueron introducidos por Manber y Myers (1990) como una simple variante eficiente en espacio a los árboles de sufijos. Estos fueron descubiertos independientemente por Gonnet, Baeza-Yates y Snider (1992) bajo el nombre de arreglo PAT.

Sea ${displaystyle S=s_{1},s_{2},...s_{n}$}$ una cadena y sea ${displaystyle S[i,j]}$ la subcadena de ${displaystyle S}$ que va desde el índice ${displaystyle i}$ hasta ${displaystyle j}$.

El arreglo de sufijos ${displaystyle A}$ de la cadena ${displaystyle S}$ va a ser un arreglo de enteros brindando las posiciones iniciales de los sufijos de ${displaystyle S}$ en orden lexicográfico. Esto significa que ${displaystyle A[i]}$ contiene la posición inicial del ${displaystyle i}$-esimo sufijo más pequeño en ${displaystyle S}$ y por tanto se cumple que para todo ${displaystyle 1<ileq n}$: ${displaystyle S[A[i-1],n]<S[A[i],n]}$.

Consideremos el texto ${displaystyle S=banana$}$ a ser indexado:

El texto termina con el carácter especial $ el cual debe ser único dentro de la cadena y lexicográficamente más pequeño que cualquier otro carácter.El texto contiene los siguientes sufijos:

Estos sufijos pueden ser ordenados :

El arreglo de sufijos ${displaystyle A}$ conteniendo las posiciones iniciales de los sufijos ordenados :

Por ejemplo, ${displaystyle A[3]}$ contiene el valor ${displaystyle 4}$ y por tanto se refiere al sufijo que empieza el la posición ${displaystyle 4}$ dentro de ${displaystyle S}$, el cual es el sufijo ${displaystyle ana$}$.

Los arreglos de sufijos están muy relacionados con los árboles de sufijos:

Ha sido demostrado todo algoritmo de árbol de sufijos puede ser sistemáticamente reemplazado con un algoritmo que use un arreglo de sufijos unido con información adicional (como un arreglo de prefijos comunes) y resuelve el mismo problema y con la misma complejidad temporal.^[1]​ Las ventajas de los arreglos de sufijos sobre los árboles de sufijos incluyen mejoras en los requerimientos de espacio y algoritmos simples de construcción en tiempo linear (e.g., comparados con el Algoritmo de Ukkonen).

Los arreglos de sufijos fueron introducidos por Manber y Myers (1990) para obtener una mejora en cuanto a los requerimientos en espacio de los árboles de sufijos : los arreglos de sufijos guardan ${displaystyle n}$ enteros.Asumiendo que un entero requiere ${displaystyle 4}$ bytes, un arreglo de sufijos requiere un total de implementación ${displaystyle 4n}$ bytes. Esto es significantemente mucho menor que los ${displaystyle 20n}$ bytes requeridos en implementación cuidadosa de un árbol de sufijos.^[2]​

Sin embargo, en ciertas aplicaciones, los requerimientos en espacio de los arreglos de sufijos pueden ser prohibitivos.Analizando en cuanto a bits, un arreglo de sufijos requiere un espacio de ${displaystyle {mathcal {O}}(nlog n)}$, donde el texto original sobre un alfabeto de longitud ${displaystyle sigma }$ require solamente ${displaystyle {mathcal {O}}(nlog sigma )}$ bits.

Una primera idea para construir un arreglo de sufijos es usar un método de ordenamiento basado en comparación. Estos algoritmos requieren ${displaystyle {mathcal {O}}(nlog n)}$ comparaciones entre sufijos, pero una comparación entre sufijos se puede realizar en un tiempo de ${displaystyle {mathcal {O}}(n)}$, entonces el tiempo completo de ejecución de esta ventaja es ${displaystyle {mathcal {O}}(n^{2}log n)}$.

Algoritmos más avanzados toman ventaja del hecho de que los sufijos a ordenar no son cadenas arbitrarias sino que está relacionadas unas con otras.Estos algoritmos tratan de priorizar los siguientes objetivos:

Uno de los primeros algoritmos en cumplir todos los objetivos es el algoritmo SA-IS de Nong, Zhang y Chan (2009). El algoritmo es también muy simple (< 100 LOC y puede ser mejorado para simultáneamente construir el arreglo de prefijos comunes.^[3]​ El algoritmo SA-IS es uno de los más rápidos algoritmos de construcción de arreglos de sufijos conocidos. Una cuidadosa implementanción implementation by Yuta Mori que supera a la mayoría de otros métodos de construcción lineales o super lineales.

El arreglo de sufijos de una cadena puede ser usado como un índice para hallar rápidamente todas las ocurrencias de una subcadena ${displaystyle P}$ dentro de una cadena ${displaystyle S}$.Hallar todas la ocurrencias de un patrón es equivalente a hallar todo sufijo que empiece con la subcadena. Gracias al ordenamiento lexicográfico, los sufijos pueden ser agrupados juntos en el arreglo de sufijos y pueden ser hallados eficientementes con dos búsquedas binarias. La primera búsqueda localiza la posición inicial del intervalo, y la segunda determina la posición final:

Hallar el patrón ${displaystyle P}$ de longitud ${displaystyle m}$ en la cadena ${displaystyle S}$ de longitud ${displaystyle n}$ toma un tiempo de ${displaystyle {mathcal {O}}(mlog n)}$, dado que solo se necesita una simple comparación de sufijos para comparar ${displaystyle m}$ caracteres.Manber y Myers (1990) describe como esta cota se puede mejorar a ${displaystyle {mathcal {O}}(m+log n)}$ usando un arreglo de prefijos comunes.Abouelhoda, Kurtz y Ohlebusch (2004) mejoró la cota e incluso obtuvo un tiempo de búsqueda de ${displaystyle {mathcal {O}}(m)}$ como el del árbol de sufijos.

---