Matriz de sufijos

En informática , una matriz de sufijos es una matriz ordenada de todos los sufijos de una cadena . Es una estructura de datos que se utiliza, entre otros, en índices de texto completo, algoritmos de compresión de datos y en el campo de la bibliometría .

Manber y Myers (1990) introdujeron las matrices de sufijos como una alternativa simple y que ahorra espacio a los árboles de sufijos . Gaston Gonnet las había descubierto de forma independiente en 1987 con el nombre de matriz PAT (Gonnet, Baeza-Yates y Snider 1992).

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

Las matrices de sufijos mejoradas (ESA) son matrices de sufijos con tablas adicionales que reproducen la funcionalidad completa de los árboles de sufijos, conservando la misma complejidad de tiempo y memoria. ^[1] La matriz de sufijos para un subconjunto de todos los sufijos de una cadena se denomina matriz de sufijos dispersa. ^[2] Se han desarrollado múltiples algoritmos probabilísticos para minimizar el uso de memoria adicional, incluido un algoritmo de tiempo y memoria óptimos. ^[3]

Definición

Sea una cadena y denote la subcadena que va desde hasta inclusive. $S=S[1]S[2]...S[n]$ ${\textstyle n}$ $S[i,j]$ ${\estilo de visualización S}$ ${\estilo de visualización i}$ ${\estilo de visualización j}$

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

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

Ejemplo

Considere el texto = a indexar: ${\estilo de visualización S}$ banana$

El texto termina con la letra centinela especial $, que es ú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 contiene las posiciones iniciales de estos sufijos ordenados: ${\estilo de visualización A}$

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

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

Correspondencia con árboles de sufijos

Las matrices de sufijos están estrechamente relacionadas con los árboles de sufijos :

Las matrices de sufijos se pueden construir realizando un recorrido en profundidad de un árbol de sufijos. La matriz de sufijos corresponde a las etiquetas de hoja 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 mediante una combinación de una matriz de sufijos y una matriz LCP . Para obtener una descripción del algoritmo, consulte la sección correspondiente en el artículo sobre la matriz LCP .

Se ha demostrado que cada algoritmo de árbol de sufijos se puede reemplazar sistemáticamente con un algoritmo que utiliza una matriz de sufijos mejorada con información adicional (como la matriz LCP ) y resuelve el mismo problema en la misma complejidad de tiempo. ^[1] Las ventajas de las matrices 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 localidad de caché mejorada. ^[4]

Eficiencia espacial

Manber y Myers (1990) introdujeron las matrices de sufijos para mejorar los requisitos de espacio de los árboles de sufijos : las matrices de sufijos almacenan números enteros. Suponiendo que un número entero requiere bytes, una matriz de sufijos requiere bytes en total. Esto es significativamente menos que los bytes que se requieren para una implementación cuidadosa de un árbol de sufijos. ^[5] ${\estilo de visualización n}$ ${\estilo de visualización 4}$ ${\estilo de visualización 4n}$ ${\estilo de visualización 20n}$

Sin embargo, en determinadas aplicaciones, los requisitos de espacio de las matrices de sufijos pueden seguir siendo prohibitivos. Analizadas en bits, una matriz de sufijos requiere espacio, mientras que el texto original sobre un alfabeto de tamaño solo requiere bits. Por lo tanto, para un genoma humano con y la matriz de sufijos ocuparía aproximadamente 16 veces más memoria que el genoma mismo. ${\mathcal {O}}(n\log n)$ ${\estilo de visualización \sigma}$ ${\mathcal {O}}(n\log \sigma)$ $\sigma = 4$ $n=3,4\times 10^{9}$

Estas discrepancias motivaron una tendencia hacia matrices de sufijos comprimidos e índices de texto completo comprimidos basados en BWT, como el índice FM . Estas estructuras de datos requieren solo espacio dentro del tamaño del texto o incluso menos.

Algoritmos de construcción

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

Un enfoque ingenuo para construir una matriz de sufijos es utilizar un algoritmo de ordenamiento basado en comparación . Estos algoritmos requieren comparaciones de sufijos, pero una comparación de sufijos se ejecuta en el tiempo, por lo que el tiempo de ejecución total de este enfoque es . ${\mathcal {O}}(n\log n)$ ${\mathcal {O}}(n)$ ${\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 intentan alcanzar los siguientes objetivos: ^[6]

complejidad asintótica mínima $\Theta (n)$
Ligero en el espacio, lo que significa que se necesita poca o ninguna memoria de trabajo además del texto y la matriz de sufijos.
Rápido en la práctica

Uno de los primeros algoritmos que logró todos los objetivos fue el algoritmo SA-IS de Nong, Zhang y Chan (2009). El algoritmo también es bastante simple (<100 LOC ) y se puede mejorar para construir simultáneamente la matriz LCP . ^[7] 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 ^[8] 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 el alfabeto que admiten : alfabetos constantes donde el tamaño del alfabeto está limitado por una constante, alfabetos enteros donde los caracteres son números enteros en un rango que depende de y alfabetos generales donde solo se permiten comparaciones de caracteres. ^[9] ${\estilo de visualización n}$

La mayoría de los algoritmos de construcción de matrices de sufijos se basan en uno de los siguientes enfoques: ^[6]

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 evaluada se duplica en cada iteración del algoritmo hasta que un prefijo es único y 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 una matriz de sufijos de los sufijos restantes. Ambas matrices de sufijos se fusionan para calcular la matriz 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 es que estos algoritmos favorecen la iteración en lugar de la recursión para ordenar el subconjunto de sufijos seleccionado. Puglisi, Smyth y Turpin (2007) han elaborado un estudio de este diverso grupo de algoritmos.

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

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 , parece funcionar bien en la práctica: los resultados experimentales de los autores mostraron que su implementación de matrices de sufijos dinámicas 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. ${\mathcal {O}}(n\log n)$

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

Matriz de sufijos generalizada

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 de un conjunto de cadenas (por ejemplo, y se ordena lexicográficamente con todos los sufijos de cada cadena. ^[16] $S=S_{1},S_{2},S_{3},...,S_{k}$

Aplicaciones

La matriz de sufijos de una cadena se puede utilizar como índice para localizar rápidamente cada ocurrencia de un patrón de subcadena dentro de la cadena . Encontrar cada ocurrencia del patrón es equivalente a encontrar cada sufijo que comience con la subcadena. Gracias al ordenamiento lexicográfico, estos sufijos se agruparán en la matriz de sufijos y se pueden encontrar de manera eficiente con dos búsquedas binarias . La primera búsqueda ubica la posición inicial del intervalo y la segunda determina la posición final: ^[^{cita requerida}^] ${\estilo de visualización P}$ ${\estilo de visualización S}$

n  =  len ( S ) def  search ( P :  str )  ->  Tuple [ int ,  int ]: """  Devuelve índices (s, r) tales que el intervalo A[s:r] (incluido 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, las matrices se indexan comenzando en 0 r = n while l < r : mid = ( l + r ) // 2 # división redondeada 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  sufijoAt ( A [ mid ]) . startswith ( P ):  l  =  mid  +  1  de lo contrario :  r  =  mid  return  ( s ,  r )

Encontrar el patrón de subcadena de longitud en la cadena de longitud lleva tiempo, dado que una sola comparación de sufijo necesita comparar caracteres. Manber y Myers (1990) describen cómo se puede mejorar este límite en el 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 el intervalo de búsqueda actual. Abouelhoda, Kurtz y Ohlebusch (2004) mejoran el límite aún más y logran un tiempo de búsqueda de para un tamaño de alfabeto constante, como se sabe a partir de los árboles de sufijos . ${\estilo de visualización P}$ ${\estilo de visualización m}$ ${\estilo de visualización S}$ ${\estilo de visualización n}$ ${\mathcal {O}}(m\log n)$ ${\estilo de visualización m}$ ${\mathcal {O}}(m+\log n)$ ${\mathcal {O}}(m)$

Los algoritmos de ordenamiento de sufijos se pueden utilizar para calcular la transformada de Burrows-Wheeler (BWT) . La BWT 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 más pequeño que todos los demás caracteres (es decir, $), entonces el orden de la matriz BWT rotada y ordenada corresponde al orden de los sufijos en una matriz de sufijos. Por lo tanto, la BWT se puede calcular en tiempo lineal construyendo primero una matriz de sufijos del texto y luego deduciendo la cadena BWT : . $BWT[i]=S[A[i]-1]$

Las matrices de sufijos también se pueden utilizar 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 utiliza en la traducción automática estadística .

Muchas aplicaciones adicionales de la matriz de sufijos requieren la matriz LCP . Algunas de ellas se detallan en la sección de aplicaciones de esta última.

Matrices de sufijos mejoradas

Los árboles de sufijos son estructuras de datos potentes que tienen una amplia aplicación en áreas de coincidencia de patrones y cadenas, indexación y estadísticas textuales. Sin embargo, ocupan una cantidad significativa de espacio y, por lo tanto, tienen un inconveniente en muchas aplicaciones en tiempo real que requieren procesar una cantidad considerablemente grande de datos, como el análisis del genoma. Para superar este inconveniente, se desarrollaron matrices de sufijos mejoradas que son estructuras de datos que consisten en matrices de sufijos y una tabla adicional llamada tabla secundaria que contiene la información sobre la relación padre-hijo entre los nodos en el árbol de sufijos. La estructura de datos de ramificación de nodos para este árbol es una lista enlazada. Las matrices de sufijos mejoradas son superiores en términos de eficiencia espacial y complejidad temporal y son fáciles de implementar. Además, se pueden aplicar a cualquier algoritmo que use un árbol de sufijos mediante un concepto abstracto de árboles de intervalo lcp. La complejidad temporal para buscar un patrón en una matriz de sufijos mejorada es O(m|Σ|).

La matriz de sufijos de la cadena es una matriz de n números enteros en el rango de 0 a n que representa los n+1 sufijos de la cadena, incluido el carácter especial #.

La matriz de sufijos se compone de dos matrices:

matriz pos pos[1,...n]: Representa una lista ordenada de todos los sufijos S. Solo las posiciones iniciales de los sufijos se almacenan en la matriz para reducir la complejidad espacial ya que los sufijos son demasiado grandes.
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.

Construyendo el intervalo lcp

Para una matriz de sufijos de S, el intervalo lcp asociado con el nodo correspondiente del árbol de sufijos de S se puede definir como:

El intervalo [i,..j], 0 ≤ i ≤ j ≤ n es un intervalo lcp de valor lcp, si

1. lcptab[i] < l,

2. lcptab[k] ≥ l para todo i + 1 ≤ k ≤ j,

3. lcptab[k] = l para algún i + 1 ≤ k ≤ j si i ≠ j y l = n − i + 1 si i = j,

4. lcptab[j + 1] < l.

La longitud del prefijo común más largo de pos[i − 1] y pos[i] se almacena en lcp[i], donde 2 ≤ i ≤ n. El intervalo lcp representa la misma relación padre-hijo que la que existe entre los nodos asociados en el árbol de sufijos de S. Esto muestra que si el nodo correspondiente de [i..j] es un hijo del nodo correspondiente de [k..l], un intervalo lcp [i..j] es un intervalo hijo de otro intervalo lcp [k..l]. Si [k..l] es un intervalo hijo de [i..j], un intervalo lcp [i..j] es el intervalo padre de un intervalo lcp [k..l].

Construyendo una tabla secundaria

La tabla secundaria cldtab se compone de tres matrices n, up , down y nextlIndex . La información sobre los bordes del árbol de sufijos correspondiente se almacena y se mantiene mediante las matrices up y down . La matriz nextlIndex almacena los vínculos en la lista enlazada utilizada para la ramificación de nodos del árbol de sufijos.

Las matrices up , down y nextlIndex se definen de la siguiente manera:

El elemento up[i] registra el índice inicial del intervalo hijo del intervalo lcp-segundo más largo, que termina en el índice i-1 .
El índice inicial del segundo intervalo secundario del intervalo lcp más largo, que comienza en el índice i, se almacena en el elemento down[i] .
Si y solo si el intervalo no es ni el primer hijo ni el último hijo de su padre, el elemento nextlIndex[i] contiene el primer índice del siguiente intervalo hermano del intervalo lcp más largo, comenzando en el índice i .

Al realizar un recorrido ascendente del intervalo lcp del árbol, se puede construir la tabla secundaria en tiempo lineal. Los valores up/down y los valores nextlIndex se pueden calcular por separado utilizando dos algoritmos distintos.

Construcción de una tabla de enlaces de sufijos

Los enlaces de sufijo para una matriz de sufijos mejorada se pueden calcular generando el intervalo de enlace de sufijo [ 1,..,r ] para cada intervalo [i,..j] durante el preprocesamiento. Los elementos izquierdo y derecho l y r del intervalo se mantienen en el primer índice de [i,..,j]. La tabla para este intervalo varía de 0 a n. La tabla de enlaces de sufijo se construye mediante el recorrido de izquierda a derecha en amplitud del árbol de intervalos lcp. Cada vez que se calcula un intervalo l , se agrega a la lista de intervalos l, que se conoce como la lista l. Cuando el valor lcp > 0, para cada intervalo l [i,..,j] en la lista, se calcula el enlace[i]. El intervalo [ l ,.., r ] se calcula mediante una búsqueda binaria en la lista ( l -1), donde l es el límite izquierdo más grande entre todos los intervalos l -1. El intervalo de enlace de sufijo de [i,..j] está representado por este intervalo [ l,..,r ]. Los valores l y r se almacenan finalmente en el primer índice de [i,..,j].

Notas

^ por Abouelhoda, Kurtz y Ohlebusch 2004.
^ Yo, Kärkkäinen y Kempa 2014.
^ Gawrychowski y Kociumaka 2017.
^ Abouelhoda, Kurtz y Ohlebusch 2002.
^ Kurtz 1999.
^ ab Puglisi, Smyth y Turpin 2007.
^ Fischer 2011.
^ Mori, Yuta. "sais". Archivado desde el original el 9 de marzo de 2023. Consultado el 31 de agosto de 2023 .
^ Burkhardt y Kärkkäinen 2003.
^ Kulla y Sanders 2007.
^ Dementiev y otros. 2008.
^ Larsson, N. Jesper; Sadakane, Kunihiko (22 de noviembre de 2007). "Clasificación de sufijos más rápida". Informática Teórica . 387 (3): 258–272. doi : 10.1016/j.tcs.2007.07.017 . ISSN 0304-3975.
^ Fischer, Johannes; Kurpicz, Florian (5 de octubre de 2017). "Desmantelando DivSufSort". Actas de la Conferencia de Cuerdas de Praga de 2017. arXiv : 1710.01896 .
^ "Nueva biblioteca saca y bwt (libsais)". codificar.su . Consultado el 3 de octubre de 2021 .
^ Grebnov, Ilya (22 de septiembre de 2021), libsais , consultado el 2 de octubre de 2021
^ Shi 1996.

Referencias

Manber, Udi ; Myers, Gene (1990). Matrices de sufijos: un nuevo método para búsquedas de cadenas en línea. Primer simposio anual ACM-SIAM sobre algoritmos discretos. págs. 319–327.
Manber, Udi ; Myers, Gene (1993). "Matrices de sufijos: un nuevo método para búsquedas de cadenas en línea". Revista SIAM de Informática . 22 (5): 935–948. doi :10.1137/0222058. S2CID 5074629.
Gawrychowski, Paweł; Kociumaka, Tomasz (enero de 2017). "Construcción de árboles de sufijos dispersos en tiempo y espacio óptimos". Actas del vigésimo octavo simposio anual ACM-SIAM sobre algoritmos discretos . Filadelfia, PA: Society for Industrial and Applied Mathematics: 425–439. arXiv : 1608.00865 . doi :10.1137/1.9781611974782.27. ISBN 9781611974782.S2CID6608776 .
Li, Zhize; Li, Jian; Huo, Hongwei (2016). Ordenación óptima de sufijos en el lugar . Actas del 25.º Simposio internacional sobre procesamiento de cadenas y recuperación de información (SPIRE). Notas de clase en informática. Vol. 11147. Springer. págs. 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 cadenas múltiples: un método para búsquedas de cadenas múltiples en línea". Concurrencia y paralelismo, programación, redes y seguridad . Apuntes de clase en informática. Vol. 1179. Springer Berlin Heidelberg. págs. 11–22. doi :10.1007/BFb0027775. ISBN. 978-3-540-62031-0.
Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). La matriz de sufijos mejorada y sus aplicaciones al análisis del genoma . Algoritmos en bioinformática. Apuntes de clase en informática . 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). "Reemplazo de árboles de sufijos con matrices de sufijos mejoradas". 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 requerimiento de espacio de los árboles de sufijos". Software: Práctica y Experiencia . 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 matrices 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 ordenamiento inducido casi puro . Conferencia sobre 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 de la matriz LCP . Algoritmos y estructuras de datos. Apuntes de clase en informática. Vol. 6844. págs. 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 comprobación rápida y ligera de matrices de sufijos . Coincidencia de patrones combinatorios. Apuntes de clase en informática. Vol. 2676. págs. 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 de matrices de sufijos de trabajo lineal simple . Autómatas, lenguajes y programación. Apuntes de clase en informática. 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 de matrices de sufijos paralelas escalables". 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 matrices de sufijos mejoradas". 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 las capacidades de árboles de sufijos y matrices de sufijos para alfabetos de tamaño no despreciable". Apuntes de la clase sobre procesamiento de cadenas y recuperación de información en informática , páginas 138-149, 2004.

Enlaces externos

Wikimedia Commons alberga una categoría multimedia sobre Matriz de sufijos .

Matriz de sufijos en Java
Módulo de ordenación de sufijos para BWT en código C
Implementación de una matriz de sufijos en Ruby
Biblioteca y herramientas de matrices de sufijos
Proyecto que contiene varias implementaciones de matrices de sufijos de C/C++ con una interfaz unificada
Una biblioteca API C rápida, liviana y robusta para construir la matriz de sufijos
Implementación de una matriz de sufijos en Python
Implementación de una matriz de sufijos de tiempo lineal en C mediante un árbol de sufijos