Arreglo de sufijos

Arreglo de Sufijos
Tipo	Arreglo
Inventado por	Plantilla:Harvtxt
Complejidad temporal; in Notación big O

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 Plantilla:Harvtxt como una simple variante eficiente en espacio a los árboles de sufijos. Estos fueron descubiertos independientemente por Plantilla:Harvtxt bajo el nombre de arreglo PAT.

Definición

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

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

Ejemplo

Consideremos el texto $S = b a n a n a $$ a ser indexado:

i	1	2	3	4	5	6	7
S[i]	b	a	n	a	n	a	$

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:

Suffix	i
banana$	1
anana$	2
nana$	3
ana$	4
na$	5
a$	6
$	7

Estos sufijos pueden ser ordenados :

Suffix	i
$	7
a$	6
ana$	4
anana$	2
banana$	1
na$	5
nana$	3

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

i	1	2	3	4	5	6	7
A[i]	7	6	4	2	1	5	3

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

Correspondencia con Árboles de Sufijos

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

Los arreglos de sufijos pueden ser construidos ejecutando una búsqueda en profundidad en un árbol de sufijos.El arreglo de sufijos se corresponde con las etiquetas-hojas dadas en el orden en que se visitó durante el recorrido, si las aristas fueron visitadas en orden lexicográfico de su primer carácter.

Un árbol de sufijos puede ser construido en tiempo lineal usando una combinación de sufijos y un arreglo de prefijos comunes.

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.Plantilla:Sfn 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).

Eficiencia en espacio

Los arreglos de sufijos fueron introducidos por Plantilla:Harvtxt para obtener una mejora en cuanto a los requerimientos en espacio de los árboles de sufijos : los arreglos de sufijos guardan $n$ enteros.Asumiendo que un entero requiere $4$ bytes, un arreglo de sufijos requiere un total de implementación $4 n$ bytes. Esto es significantemente mucho menor que los $20 n$ bytes requeridos en implementación cuidadosa de un árbol de sufijos.Plantilla:Sfn

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 $𝒪 (n \log n)$ , donde el texto original sobre un alfabeto de longitud $σ$ require solamente $𝒪 (n \log σ)$ bits.

Algoritmos de construcción

Una primera idea para construir un arreglo de sufijos es usar un método de ordenamiento basado en comparación. Estos algoritmos requieren $𝒪 (n \log n)$ comparaciones entre sufijos, pero una comparación entre sufijos se puede realizar en un tiempo de $𝒪 (n)$ , entonces el tiempo completo de ejecución de esta ventaja es $𝒪 (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:

complejidad asimptótica minimal $Θ (n)$
rápido en práctica

Uno de los primeros algoritmos en cumplir todos los objetivos es el algoritmo SA-IS de Plantilla:Harvtxt. El algoritmo es también muy simple (< 100 LOC y puede ser mejorado para simultáneamente construir el arreglo de prefijos comunes.Plantilla:Sfn 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 Plantilla:Wayback que supera a la mayoría de otros métodos de construcción lineales o super lineales.

Aplicaciones

El arreglo de sufijos de una cadena puede ser usado como un índice para hallar rápidamente todas las ocurrencias de una subcadena $P$ dentro de una cadena $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:

    def search(P):
        l = 1; r = n + 1
        while l < r:
            mid = (l+r) / 2
            if P > suffixAt(A[mid]):
                l = mid + 1
            else:
                r = mid
        s = l; r = n + 1
        while l < r:
            mid = (l+r) / 2
            if P == suffixAt(A[mid]):
                l = mid
            else:
                r = mid - 1
        return (s, r)

Hallar el patrón $P$ de longitud $m$ en la cadena $S$ de longitud $n$ toma un tiempo de $𝒪 (m \log n)$ , dado que solo se necesita una simple comparación de sufijos para comparar $m$ caracteres.Plantilla:Harvtxt describe como esta cota se puede mejorar a $𝒪 (m + \log n)$ usando un arreglo de prefijos comunes.Plantilla:Harvtxt mejoró la cota e incluso obtuvo un tiempo de búsqueda de $𝒪 (m)$ como el del árbol de sufijos.

Notas

Plantilla:Listaref

Referencias

Enlaces externos

Plantilla:Control de autoridades

Arreglo de sufijos

Sumario

Definición

Ejemplo

Correspondencia con Árboles de Sufijos

Eficiencia en espacio

Algoritmos de construcción

Aplicaciones

Notas

Referencias

Enlaces externos

Menú de navegación

Arreglo de sufijos

Definición

Ejemplo

Correspondencia con Árboles de Sufijos

Eficiencia en espacio

Algoritmos de construcción

Aplicaciones

Notas

Referencias

Enlaces externos

Menú de navegación

Buscar