Matriz de sufijos

En informática , un array de sufijos es un array ordenado que contiene todos los sufijos de una cadena . Es una estructura de datos utilizada, entre otros campos, en índices de texto completo, algoritmos de compresión de datos y bibliometría .

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

Li, Li y Huo (2016) dieron el primer informe in situ.${\displaystyle {\mathcal {O}}(n)}$Algoritmo de construcción de arreglos de sufijos de tiempo que es óptimo tanto en tiempo como en espacio, donde in situ significa que el algoritmo solo necesita${\displaystyle {\mathcal {O}}(1)}$espacio adicional más allá de la cadena de entrada y la matriz de sufijos de salida.

Los arreglos de sufijos mejorados (ESA) son arreglos de sufijos con tablas adicionales que reproducen la funcionalidad completa de los árboles de sufijos, conservando la misma complejidad de tiempo y memoria. ^{[ 1 ]} Un arreglo ordenado de solo algunos (en lugar de todos) los sufijos de una cadena se denomina arreglo de sufijos disperso . ^{[ 2 ]}

Dejar${\displaystyle S=S[1]S[2]...S[n]}$frijol${\textstyle n}$-cadena y deja${\displaystyle S[i,j]}$denota la subcadena de${\displaystyle S}$que van desde${\displaystyle i}$a${\displaystyle j}$inclusivo.

La matriz de sufijos${\displaystyle A}$de${\displaystyle S}$ahora se define como una matriz de enteros que proporciona las posiciones iniciales de los sufijos de${\displaystyle S}$en orden lexicográfico . Esto significa que una entrada${\displaystyle A[i]}$contiene la posición inicial del${\displaystyle i}$-o sufijo más pequeño en${\displaystyle S}$y por lo tanto para todos${\displaystyle 1\leq i\leq n}$:${\displaystyle S[A[i-1],n]<S[A[i],n]}$.

Cada sufijo de${\displaystyle S}$aparece en${\displaystyle A}$exactamente una vez. Los sufijos son cadenas simples. Estas cadenas se ordenan (como en un diccionario en papel), antes de que sus posiciones iniciales (índices enteros) se guarden en${\displaystyle A}$.

Considere el texto${\displaystyle S}$= banana$para ser indexado:

El texto finaliza con la letra centinela especial $, única y lexicográficamente más pequeña que cualquier otro carácter. El texto tiene los siguientes sufijos:

Estos sufijos se pueden ordenar en orden ascendente:

La matriz de sufijos${\displaystyle A}$Contiene las posiciones iniciales de estos sufijos ordenados:

La matriz de sufijos con los sufijos escritos verticalmente debajo para mayor claridad:

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

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

• Los arreglos de sufijos se pueden construir realizando un recorrido en profundidad de un árbol de sufijos. El arreglo de sufijos corresponde a las etiquetas de las hojas dadas en el orden en que se visitan durante el recorrido, si las aristas se visitan en el orden lexicográfico de su primer carácter.
• Se puede construir un árbol de sufijos en tiempo lineal utilizando una combinación de un arreglo de sufijos y un arreglo LCP . Para una descripción del algoritmo, consulte la sección correspondiente en el artículo sobre arreglos LCP .

Se ha demostrado que cualquier algoritmo de árbol de sufijos puede reemplazarse sistemáticamente por un algoritmo que utiliza un arreglo de sufijos mejorado con información adicional (como el arreglo LCP ) y resuelve el mismo problema con la misma complejidad temporal. ^{[ 1 ]} Las ventajas de los arreglos de sufijos sobre los árboles de sufijos incluyen requisitos de espacio mejorados, algoritmos de construcción de tiempo lineal más simples (por ejemplo, en comparación con el algoritmo de Ukkonen ) y una mejor localidad de caché. ^{[ 3 ]}

Los arreglos de sufijos fueron introducidos por Manber y Myers (1990) para mejorar los requisitos de espacio de los árboles de sufijos : Los arreglos de sufijos almacenan${\displaystyle n}$enteros. Suponiendo que un entero requiere${\displaystyle 4}$bytes, una matriz de sufijo requiere${\displaystyle 4n}$bytes en total. Esto es significativamente menor que el${\displaystyle 20n}$bytes que son necesarios para una implementación cuidadosa del árbol de sufijos. ^{[ 4 ]}

Sin embargo, en ciertas aplicaciones, los requisitos de espacio de las matrices de sufijos aún pueden ser prohibitivos. Analizada en bits, una matriz de sufijos requiere${\displaystyle {\mathcal {O}}(n\log n)}$espacio, mientras que el texto original sobre un alfabeto de tamaño${\displaystyle \sigma }$solo requiere${\displaystyle {\mathcal {O}}(n\log \sigma )}$bits. Para un genoma humano con${\displaystyle \sigma =4}$y${\displaystyle n=3.4\times 10^{9}}$Por lo tanto, la matriz de sufijos ocuparía aproximadamente 16 veces más memoria que el propio genoma.

Estas discrepancias impulsaron una tendencia hacia los arreglos de sufijos comprimidos y los índices de texto completo comprimidos basados ​​en BWT, como el índice FM . Estas estructuras de datos solo requieren espacio equivalente al tamaño del texto, o incluso menos.

Se puede construir un árbol de sufijos en${\displaystyle {\mathcal {O}}(n)}$y se puede convertir en una matriz de sufijos recorriendo el árbol en profundidad también en${\displaystyle {\mathcal {O}}(n)}$, por lo que existen algoritmos que pueden construir una matriz de sufijos en${\displaystyle {\mathcal {O}}(n)}$.

Un enfoque ingenuo para construir una matriz de sufijos es utilizar un algoritmo de ordenación basado en comparaciones . Estos algoritmos requieren${\displaystyle {\mathcal {O}}(n\log n)}$comparaciones de sufijos, pero una comparación de sufijos se ejecuta en${\displaystyle {\mathcal {O}}(n)}$tiempo, por lo que el tiempo de ejecución total de este enfoque es${\displaystyle {\mathcal {O}}(n^{2}\log n)}$.

Los algoritmos más avanzados aprovechan el hecho de que los sufijos que se van a ordenar no son cadenas arbitrarias, sino que están relacionados entre sí. Estos algoritmos se esfuerzan por lograr los siguientes objetivos: ^{[ 5 ]}

• complejidad asintótica mínima${\displaystyle \Theta (n)}$
• ligero en espacio, lo que significa que se necesita poca o ninguna memoria de trabajo aparte del texto y la matriz de sufijos en sí.
• rápido en la práctica

Uno de los primeros algoritmos que logra todos los objetivos es el algoritmo SA-IS de Nong, Zhang y Chan (2009) . El algoritmo es bastante simple ( < 100 LOC ) y puede mejorarse para construir simultáneamente la matriz LCP . ^{[ 6 ]} El algoritmo SA-IS es uno de los algoritmos de construcción de matrices de sufijos más rápidos conocidos. Una implementación cuidadosa de Yuta Mori ^{[ 7 ]} supera a la mayoría de los demás enfoques de construcción lineales o superlineales.

Además de los requisitos de tiempo y espacio, los algoritmos de construcción de matrices de sufijos también se diferencian por su alfabeto admitido : alfabetos constantes donde el tamaño del alfabeto está limitado por una constante, alfabetos enteros donde los caracteres son enteros en un rango que depende de${\displaystyle n}$y alfabetos generales donde solo se permiten comparaciones de caracteres. ^{[ 8 ]}

La mayoría de los algoritmos de construcción de arreglos de sufijos se basan en uno de los siguientes enfoques: ^{[ 5 ]}

• Los algoritmos de duplicación de prefijos se basan en una estrategia de Karp, Miller y Rosenberg (1972) . La idea es encontrar prefijos que respeten el orden lexicográfico de los sufijos. La longitud del prefijo evaluado se duplica en cada iteración del algoritmo hasta que se obtiene un prefijo único que proporciona el rango del sufijo asociado.
• Los algoritmos recursivos siguen el enfoque del algoritmo de construcción de árboles de sufijos de Farach (1997) para ordenar recursivamente un subconjunto de sufijos. Este subconjunto se utiliza luego para inferir un arreglo de sufijos con los sufijos restantes. Ambos arreglos de sufijos se combinan para calcular el arreglo de sufijos final.
• Los algoritmos de copia inducida son similares a los algoritmos recursivos en el sentido de que utilizan un subconjunto ya ordenado para inducir una ordenación rápida de los sufijos restantes. La diferencia radica en que estos algoritmos priorizan la iteración sobre la recursión para ordenar el subconjunto de sufijos seleccionado. Puglisi, Smyth y Turpin (2007) realizaron un estudio comparativo de este diverso grupo de algoritmos .

Un algoritmo recursivo bien conocido para alfabetos enteros es el algoritmo DC3/skew de Kärkkäinen y Sanders (2003) . Se ejecuta en tiempo lineal y se ha utilizado con éxito como base para algoritmos de construcción de matrices de sufijos paralelos ^{[ 9 ]} y de memoria externa ^{[ 10 ] .}

Un trabajo reciente de Salson et al. (2010) propone un algoritmo para actualizar la matriz de sufijos de un texto que ha sido editado en lugar de reconstruir una nueva matriz de sufijos desde cero. Incluso si la complejidad temporal teórica en el peor de los casos es${\displaystyle {\mathcal {O}}(n\log n)}$En la práctica, parece funcionar bien: los resultados experimentales de los autores demostraron que su implementación de matrices de sufijos dinámicos es generalmente más eficiente que la reconstrucción cuando se considera la inserción de una cantidad razonable de letras en el texto original.

En el trabajo práctico de código abierto , una rutina comúnmente utilizada para la construcción de arreglos de sufijos era qsufsort, basada en el algoritmo de Larsson-Sadakane de 1999. ^{[ 11 ]} Esta rutina ha sido reemplazada por DivSufSort de Yuta Mori, "el algoritmo de ordenación de sufijos más rápido conocido en memoria principal" a partir de 2017. También puede modificarse para calcular un arreglo LCP. Utiliza una copia inducida combinada con Itoh-Tanaka. ^{[ 12 ]} En 2021, Ilya Grebnov presentó una implementación más rápida del algoritmo ^{[ 13 ]} que en promedio mostró una mejora de rendimiento del 65% sobre la implementación de DivSufSort en el corpus Silesia . ^{[ 14 ]}

El concepto de matriz de sufijos se puede extender a más de una cadena. Esto se denomina matriz de sufijos generalizada (o GSA), una matriz de sufijos que contiene todos los sufijos para un conjunto de cadenas (por ejemplo,${\displaystyle S=S_{1},S_{2},S_{3},...,S_{k}}$y está ordenado lexicográficamente con todos los sufijos de cada cadena. ^{[ 15 ]}

El array de sufijos de una cadena se puede utilizar como índice para localizar rápidamente cada aparición de un patrón de subcadena.${\displaystyle P}$dentro de la cadena${\displaystyle S}$Encontrar cada aparición del patrón equivale a encontrar cada sufijo que comienza con la subcadena. Gracias al orden lexicográfico, estos sufijos se agruparán en el array de sufijos y se pueden encontrar de forma eficiente con dos búsquedas binarias . La primera búsqueda localiza la posición inicial del intervalo y la segunda determina la posición final.

n = longitud ( S )def search ( P : str ) -> tuple [ int , int ]: """  Devuelve los índices (s, r) tales que el intervalo A[s:r] (excluyendo el  índice final) representa todos los sufijos de S que comienzan con el patrón P.  """ # Encuentra la posición inicial del intervalo l = 0 # en Python, los arrays se indexan comenzando en 0 r = n while l < r : mid = ( l + r ) // 2 # división redondeando hacia abajo al entero más cercano # suffixAt(A[i]) es el i-ésimo sufijo más pequeño if P > suffixAt ( A [ mid ]): l = mid + 1 else : r = mid s = l# Encuentra la posición final del intervalo r = n mientras l < r : mid = ( l + r ) // 2 si suffixAt ( A [ mid ]) . startswith ( P ): l = mid + 1 sino : r = mid return ( s , r )

Encontrar el patrón de subcadena${\displaystyle P}$de longitud${\displaystyle m}$en la cadena${\displaystyle S}$de longitud${\displaystyle n}$acepta${\displaystyle {\mathcal {O}}(m\log n)}$tiempo, dado que una sola comparación de sufijos necesita comparar${\displaystyle m}$personajes. Manber y Myers (1990) describen cómo se puede mejorar este límite para${\displaystyle {\mathcal {O}}(m+\log n)}$tiempo utilizando información LCP . La idea es que una comparación de patrones no necesita volver a comparar ciertos caracteres, cuando ya se sabe que estos son parte del prefijo común más largo del patrón y del intervalo de búsqueda actual. Abouelhoda, Kurtz y Ohlebusch (2004) mejoran aún más el límite y logran un tiempo de búsqueda de${\displaystyle {\mathcal {O}}(m)}$para un tamaño de alfabeto constante, como se sabe a partir de los árboles de sufijos .

Los algoritmos de ordenación de sufijos se pueden utilizar para calcular la transformada de Burrows-Wheeler (TBB) . La TBB requiere la ordenación de todas las permutaciones cíclicas de una cadena. Si esta cadena termina en un carácter especial de fin de cadena que es lexicográficamente menor que todos los demás caracteres (es decir, $), entonces el orden de la matriz TBB rotada y ordenada corresponde al orden de los sufijos en un arreglo de sufijos. Por lo tanto, la TBB se puede calcular en tiempo lineal construyendo primero un arreglo de sufijos del texto y luego deduciendo la cadena TBB .${\displaystyle BWT[i]=S[A[i]-1]}$.

Las matrices de sufijos también se pueden usar para buscar subcadenas en la traducción automática basada en ejemplos , lo que requiere mucho menos almacenamiento que una tabla de frases completa como la que se usa en la traducción automática estadística .

Muchas aplicaciones adicionales del arreglo de sufijos requieren el arreglo LCP . Algunas de ellas se detallan en la sección de aplicaciones de este último.

Los árboles de sufijos son estructuras de datos potentes con amplia aplicación en áreas como la búsqueda de patrones y cadenas, la indexación y la estadística textual. Sin embargo, ocupan una cantidad considerable de espacio, lo que supone un inconveniente en muchas aplicaciones en tiempo real que requieren el procesamiento de grandes cantidades de datos, como el análisis genómico. Para superar este inconveniente, se desarrolló el Enhanced Suffix Array (ARRAY de Sufijos Mejorado). Se trata de una estructura de datos compuesta por un array de sufijos y una tabla adicional, denominada tabla hija, que contiene información sobre la relación padre-hijo entre los nodos del árbol de sufijos. La estructura de datos de ramificación de nodos para este árbol es una lista enlazada . Los arrays de sufijos mejorados superan a los árboles de sufijos en eficiencia espacial y complejidad temporal, y son fáciles de implementar. Además, pueden aplicarse a cualquier algoritmo que utilice un árbol de sufijos mediante un concepto abstracto denominado árboles de intervalo LCP. La complejidad temporal para buscar un patrón de longitud${\displaystyle m}$en una matriz de sufijos mejorada es${\displaystyle {\mathcal {O}}(m|\Sigma |)}$.

La matriz de sufijos mejorada se compone de dos matrices:

1. El array pos pos[1,...n] representa una lista ordenada de todos los sufijos S. Solo se almacenan las posiciones iniciales de los sufijos en el array para reducir la complejidad espacial, ya que los sufijos son demasiado grandes.
2. matriz lcp lcp[1,...n]: Es una matriz de n enteros que mantiene las longitudes del prefijo común más largo de dos sufijos consecutivos almacenados en la matriz pos.

• Manber, Udi ; Myers, Gene (1990). Suffix arrays: a new method for on-line string searching . First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327 . 
• Manber, Udi ; Myers, Gene (1993). "Suffix arrays: a new method for on-line string searching" . SIAM Journal on Computing . 22 (5): 935–948 . doi : 10.1137/0222058 . S2CID 5074629 . 
• Li, Zhize; Li, Jian; Huo, Hongwei (2016). Ordenación óptima de sufijos in situ . Actas del 25.º Simposio Internacional sobre Procesamiento de Cadenas y Recuperación de Información (SPIRE). Lecture Notes in Computer Science. Vol.  11147. Springer. pp. 268–284 . arXiv : 1610.08305 . doi : 10.1007/978-3-030-00479-8_22 . ISBN  978-3-030-00478-1.
• Shi, Fei (1996). "Matrices de sufijos para múltiples cadenas: Un método para búsquedas en línea de múltiples cadenas". Concurrencia y paralelismo, programación, redes y seguridad . Notas de clase en ciencias de la computación. Vol.  1179. Springer Berlin Heidelberg. pp. 11–22 . doi : 10.1007/BFb0027775 . ISBN  978-3-540-62031-0.
• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). El array de sufijos mejorado y sus aplicaciones al análisis del genoma . Algoritmos en bioinformática. Notas de clase en ciencias de la computación . Vol.  2452. doi : 10.1007/3-540-45784-4_35 . ISBN 978-3-540-44211-0.
• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (marzo de 2004). "Reemplazando árboles de sufijos con arreglos de sufijos mejorados" . Journal of Discrete Algorithms . 2 (1): 53– 86. doi : 10.1016/S1570-8667(03)00065-0 . ISSN 1570-8667 . 
• Gonnet, GH; Baeza-Yates, RA; Snider, T. (1992). "Nuevos índices para texto: árboles PAT y matrices PAT" . Recuperación de información: estructuras de datos y algoritmos .
• Kurtz, S (1999). "Reducción del espacio requerido en los árboles de sufijos". Software: Practice and Experience . 29 (13): 1149– 1171. doi : 10.1002/(SICI)1097-024X(199911)29:13 < 1149::AID-SPE274 > 3.0.CO ; 2-O . hdl : 10338.dmlcz/135448 .
• Puglisi, Simon J.; Smyth, WF; Turpin, Andrew H. (2007). "Una taxonomía de algoritmos de construcción de arreglos de sufijos" . ACM Computing Surveys . 39 (2): 4. doi : 10.1145/1242471.1242472 . S2CID 2653529 . 
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Construcción de matrices de sufijos lineales mediante ordenación inducida casi pura . Conferencia de compresión de datos de 2009. pág.  193. doi : 10.1109/DCC.2009.42 . ISBN 978-0-7695-3592-0.
• Fischer, Johannes (2011). Inducción del arreglo LCP . Algoritmos y estructuras de datos. Notas de clase en ciencias de la computación. Vol.  6844. pp. 374–385 . arXiv : 1101.3448 . doi : 10.1007/978-3-642-22300-6_32 . ISBN  978-3-642-22299-3.
• Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). "Matrices de sufijos extendidos dinámicos" . Journal of Discrete Algorithms . 8 (2): 241. doi : 10.1016/j.jda.2009.02.007 .
• Burkhardt, Stefan; Kärkkäinen, Juha (2003). Construcción y verificación rápida y ligera de arreglos de sufijos . Coincidencia de patrones combinatorios. Lecture Notes in Computer Science. Vol.  2676. pp. 55–69 . doi : 10.1007/3-540-44888-8_5 . ISBN  978-3-540-40311-1.
• Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). Identificación rápida de patrones repetidos en cadenas, árboles y matrices . Actas del cuarto simposio anual de la ACM sobre Teoría de la Computación - STOC '72. págs. 125–136 . doi : 10.1145/800152.804905 . 
• Farach, M. (1997). Construcción óptima de árboles de sufijos con alfabetos grandes . Actas del 38.º Simposio Anual sobre Fundamentos de la Informática. doi : 10.1109/SFCS.1997.646102 . ISBN 0-8186-8197-7.
• Yo, Tomohiro; Kärkkäinen, Juha; Kempa, Dominik (2014). Clasificación de sufijos dispersos más rápida . Procedimientos internacionales de informática de Leibniz (LIPIcs). vol.  25. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. págs. 386– 396. doi : 10.4230/LIPIcs.STACS.2014.386 . ISBN  978-3-939897-65-1.
• Kärkkäinen, Juha; Sanders, Peter (2003). Construcción simple de arreglos de sufijos de trabajo lineales . Autómatas, lenguajes y programación. Notas de clase en ciencias de la computación. Vol.  2719. doi : 10.1007/3-540-45061-0_73 . ISBN 978-3-540-40493-4.
• Dementiev, romano; Kärkkäinen, Juha; Mehnert, Jens; Lijadoras, Peter (2008). "Mejor construcción de matriz de sufijos de memoria externa" . Revista de algorítmica experimental . 12 : 1– 24. doi : 10.1145/1227161.1402296 . S2CID 12296500 . 
• Kulla, Fabian; Sanders, Peter (2007). "Construcción escalable de matrices de sufijos paralelas". Computación paralela . 33 (9): 605– 612. doi : 10.1016/j.parco.2007.06.004 .
• Mohamed Ibrahim Abouelhoda, Stefan Kurtz y Enno Ohlebusch. "Reemplazo de árboles de sufijos con arreglos de sufijos mejorados". Journal of Discrete Algorithms , 2(1):53–86, 2004.
• Dong Kyue Kim, Jeong Eun Jeon y Heejin Park. «Una estructura de datos de índice eficiente con capacidades de árboles de sufijos y matrices de sufijos para alfabetos de tamaño considerable». Procesamiento de cadenas y recuperación de información: Notas de clase en informática , páginas 138-149, 2004.

• Arreglo de sufijos en Java
• Módulo de ordenación de sufijos para BWT en código C
• Implementación de un array de sufijos en Ruby
• Biblioteca y herramientas para matrices de sufijos
• Proyecto que contiene varias implementaciones de Suffix Array en C/C++ con una interfaz unificada.
• Una biblioteca API de C rápida, ligera y robusta para construir el array de sufijos.
• Implementación de un array de sufijos en Python
• Implementación de un arreglo de sufijos en tiempo lineal en C usando un árbol de sufijos.