Arreglo de sufijos

Arreglo de Sufijos
Tipo	Arreglo
Inventado por	Manber y Myers (1990)
Complejidad temporal in Notación big O
	Caso promedio	Caso Peor
Espacio	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$
Construcción	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$

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.

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=banana\$$ 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 $ana\$$ .

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.^[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).

Eficiencia en espacio

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 $n$ enteros.Asumiendo que un entero requiere $4$ bytes, un arreglo de sufijos requiere un total de implementación $4n$ bytes. Esto es significantemente mucho menor que los $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 ${\mathcal {O}}(n\log n)$ , donde el texto original sobre un alfabeto de longitud $\sigma$ require solamente ${\mathcal {O}}(n\log \sigma )$ 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 ${\mathcal {O}}(n\log n)$ comparaciones entre sufijos, pero una comparación entre sufijos se puede realizar en un tiempo de ${\mathcal {O}}(n)$ , entonces el tiempo completo de ejecución de esta ventaja es ${\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:

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

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 Archivado el 26 de julio de 2014 en Wayback Machine. 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 ${\mathcal {O}}(m\log n)$ , dado que solo se necesita una simple comparación de sufijos para comparar $m$ caracteres.Manber y Myers (1990) describe como esta cota se puede mejorar a ${\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 ${\mathcal {O}}(m)$ como el del árbol de sufijos.

Referencias

Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). «Replacing suffix trees with enhanced suffix arrays». Journal of Discrete Algorithms 2: 53. doi:10.1016/S1570-8667(03)00065-0.
Manber, Udi; Myers, Gene (1990). «Suffix arrays: a new method for on-line string searches». In Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms 90 (319): 327.
Gonnet, G.H; Baeza-Yates, R.A; Snider, T (1992). «New indices for text: PAT trees and PAT arrays». Information retrieval: data structures and algorithms.
Kurtz, S (1999). «Reducing the space requirement of suffix trees». Software-Practice and Experience 29 (13): 1149. doi:10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O.
Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). «The Enhanced Suffix Array and Its Applications to Genome Analysis». Algorithms in Bioinformatics. Lecture Notes in Computer Science 2452. p. 449. ISBN 978-3-540-44211-0. doi:10.1007/3-540-45784-4_35.
Puglisi, Simon J.; Smyth, W. F.; Turpin, Andrew H. (2007). «A taxonomy of suffix array construction algorithms». ACM Computing Surveys 39 (2): 4. doi:10.1145/1242471.1242472.
Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). «Linear Suffix Array Construction by Almost Pure Induced-Sorting». 2009 Data Compression Conference. p. 193. ISBN 978-0-7695-3592-0. doi:10.1109/DCC.2009.42.
Fischer, Johannes (2011). «Inducing the LCP-Array». Algorithms and Data Structures. Lecture Notes in Computer Science 6844. p. 374. ISBN 978-3-642-22299-3. doi:10.1007/978-3-642-22300-6_32.
Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). «Dynamic extended suffix arrays». Journal of Discrete Algorithms 8 (2): 241. doi:10.1016/j.jda.2009.02.007.
Burkhardt, Stefan; Kärkkäinen, Juha (2003). «Fast Lightweight Suffix Array Construction and Checking». Combinatorial Pattern Matching. Lecture Notes in Computer Science 2676. p. 55. ISBN 978-3-540-40311-1. doi:10.1007/3-540-44888-8_5.
Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). «Rapid identification of repeated patterns in strings, trees and arrays». Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. p. 125. doi:10.1145/800152.804905.
Farach, M. (1997). «Optimal suffix tree construction with large alphabets». Proceedings 38th Annual Symposium on Foundations of Computer Science. p. 137. ISBN 0-8186-8197-7. doi:10.1109/SFCS.1997.646102.
Kärkkäinen, Juha; Sanders, Peter (2003). «Simple Linear Work Suffix Array Construction». Automata, Languages and Programming. Lecture Notes in Computer Science 2719. p. 943. ISBN 978-3-540-40493-4. doi:10.1007/3-540-45061-0_73.
Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). «Better external memory suffix array construction». Journal of Experimental Algorithmics 12: 1. doi:10.1145/1227161.1402296.
Kulla, Fabian; Sanders, Peter (2007). «Scalable parallel suffix array construction». Parallel Computing 33 (9): 605. doi:10.1016/j.parco.2007.06.004.

Enlaces externos

Suffix sorting module for BWT in C code
Suffix Array Implementation in Ruby
Suffix array library and tools
Project containing various Suffix Array c/c++ Implementations with a unified interface
A fast, lightweight, and robust C API library to construct the suffix array
Suffix Array implementation in Python