Ver el código de «Arreglo de sufijos»

{| class="infobox" style="width: 22em"
! colspan="3" style="font-size: 125%; text-align: center;" | Arreglo de Sufijos
|-
! [[List of data structures|Tipo]]
| colspan="2" |  [[Array data structure|Arreglo]]
|-
! Inventado por
{{!}} colspan="2" {{!}}  {{harvtxt|Manber|Myers|1990}}
|-
! colspan="3" class="navbox-abovebelow" | [[Complejidad temporal]]<br />in [[Notación big O]]
|-
|
| Caso promedio
| Caso Peor
|-
! Espacio
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
|-
! Construcción
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
|}

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 {{harvtxt|Manber|Myers|1990}} como una simple variante eficiente en espacio a los árboles de sufijos. Estos fueron descubiertos independientemente por {{harvtxt|Gonnet|Baeza-Yates|Snider|1992}} bajo el nombre de arreglo '''PAT'''.

== Definición ==
Sea <math>S=s_1,s_2,...s_n\$</math> una cadena y sea <math>S[i,j]</math> la subcadena de <math>S</math> que va desde el índice <math>i</math> hasta <math>j</math>.

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

== Ejemplo ==
Consideremos el texto <math>S=banana\$</math> a ser indexado:
{| class="wikitable"
|-
! 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:

{|   class="wikitable"
!  align="left" | Suffix !!  align="left" | i
|-  class="odd"
|  align="left" | banana$ ||  align="left" | 1
|-  class="even"
|  align="left" | anana$ ||  align="left" | 2
|-  class="odd"
|  align="left" | nana$ ||  align="left" | 3
|-  class="even"
|  align="left" | ana$ ||  align="left" | 4
|-  class="odd"
|  align="left" | na$ ||  align="left" | 5
|-  class="even"
|  align="left" | a$ ||  align="left" | 6
|-  class="odd"
|  align="left" | $ ||  align="left" | 7
|}

Estos sufijos pueden ser ordenados :

{|   class="wikitable"
!  align="left" | Suffix !!  align="left" | i
|-  class="odd"
|  align="left" | $ ||  align="left" | 7
|-  class="even"
|  align="left" | a$ ||  align="left" | 6
|-  class="odd"
|  align="left" | ana$ ||  align="left" | 4
|-  class="even"
|  align="left" | anana$ ||  align="left" | 2
|-  class="odd"
|  align="left" | banana$ ||  align="left" | 1
|-  class="even"
|  align="left" | na$ ||  align="left" | 5
|-  class="odd"
|  align="left" | nana$ ||  align="left" | 3
|}

El arreglo de sufijos <math>A</math> conteniendo las posiciones iniciales de los sufijos ordenados :
{| class="wikitable"
! i
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
! A[i]
| 7 || 6 || 4 || 2 || 1 || 5 || 3
|}

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

== 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.{{sfn|Abouelhoda|Kurtz|Ohlebusch|2004}}
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 {{harvtxt|Manber|Myers|1990}} para obtener una mejora en cuanto a los requerimientos en espacio de los árboles de sufijos : los arreglos de sufijos guardan <math>n</math> enteros.Asumiendo que un entero requiere <math>4</math> bytes, un arreglo de sufijos requiere un total de implementación <math>4n</math> bytes. Esto es significantemente mucho menor que los <math>20n</math> bytes requeridos en implementación cuidadosa de un árbol de sufijos.{{sfn|Kurtz|1999}}

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 <math>\mathcal{O}(n \log n)</math>, donde el texto original sobre un alfabeto de longitud <math>\sigma</math> require solamente <math>\mathcal{O}(n \log \sigma)</math> 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 <math>\mathcal{O}(n \log n)</math> comparaciones entre sufijos, pero una comparación entre sufijos se puede realizar en un tiempo de <math>\mathcal{O}(n)</math>, entonces el tiempo completo de ejecución de esta ventaja es <math>\mathcal{O}(n^2 \log n)</math>.

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 <math>\Theta(n)</math>
* rápido en práctica

Uno de los primeros algoritmos en cumplir todos los objetivos es el algoritmo SA-IS de {{harvtxt|Nong|Zhang|Chan|2009}}. El algoritmo es también muy simple (&lt; 100 [[Source lines of code|LOC]] y puede ser mejorado para simultáneamente construir el arreglo de prefijos comunes.{{sfn|Fischer|2011}} 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
[https://sites.google.com/site/yuta256/sais implementation by Yuta Mori] {{Wayback|url=https://sites.google.com/site/yuta256/sais |date=20140726035234 }} 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 <math>P</math> dentro de una cadena <math>S</math>.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:

<syntaxhighlight lang="python">
    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)
</syntaxhighlight>

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

== Notas ==
{{listaref}}

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

== Enlaces externos ==
* [http://code.google.com/p/compression-code/downloads/list Suffix sorting module for BWT in C code]
* [http://www.codeodor.com/index.cfm/2007/12/24/The-Suffix-Array/1845 Suffix Array Implementation in Ruby]
* [http://sary.sourceforge.net/index.html.en Suffix array library and tools]
* [http://pizzachili.dcc.uchile.cl/ Project containing various Suffix Array c/c++ Implementations with a unified interface]
* [http://code.google.com/p/libdivsufsort/ A fast, lightweight, and robust C API library to construct the suffix array]
* [http://code.google.com/p/pysuffix/ Suffix Array implementation in Python]

{{Control de autoridades}}
[[Categoría:Estructura de datos]]