Matriz de sufijos

Estructura de datos para una cadena

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

Manber y Myers (1990) introdujeron las matrices de sufijos como una alternativa simple y eficiente en cuanto a espacio a los árboles de sufijos . Habían sido descubiertos de forma independiente por Gaston Gonnet en 1987 con el nombre de matriz PAT (Gonnet, Baeza-Yates y Snider 1992).

Li, Li y Huo (2016) proporcionaron el primer algoritmo de construcción de matrices de sufijos de tiempo in situ que es óptimo tanto en el tiempo como en el espacio, donde in situ significa que el algoritmo solo necesita espacio adicional más allá de la cadena de entrada y la matriz de sufijos de salida. ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\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 el mismo tiempo y complejidad de memoria. ^[1] La matriz de sufijos para un subconjunto de todos los sufijos de una cadena se llama 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. ${\displaystyle S=S[1]S[2]...S[n]}$ ${\textstyle n}$ ${\displaystyle S[i,j]}$ ${\displaystyle S}$ ${\displaystyle i}$ ${\displaystyle j}$

La matriz de sufijos de ahora se define como una matriz de números enteros que proporcionan las posiciones iniciales de los sufijos de en orden lexicográfico . Esto significa que una entrada contiene la posición inicial del -ésimo sufijo más pequeño en y, por tanto, para todos : . ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle A[i]}$ ${\displaystyle i}$ ${\displaystyle S}$ ${\displaystyle 1\leq i\leq n}$ ${\displaystyle 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 en papel), antes de que sus posiciones iniciales (índices enteros) se guarden en formato . ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle A}$

Ejemplo

Considere el texto = a indexar: ${\displaystyle S}$banana$

El texto termina con la carta 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: ${\displaystyle 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 . ${\displaystyle A[3]}$ ${\displaystyle S}$ana$

Correspondencia a á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 hojas dadas en el orden en que se visitan durante el recorrido, si los bordes 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 matriz de sufijos y matriz LCP . Para obtener una descripción del algoritmo, consulte la sección correspondiente en el artículo sobre matrices 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 con la misma complejidad temporal. ^[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 menor que los bytes que requiere una implementación cuidadosa del árbol de sufijos. ^[5] ${\displaystyle n}$ ${\displaystyle 4}$ ${\displaystyle 4n}$ ${\displaystyle 20n}$

Sin embargo, en determinadas aplicaciones, los requisitos de espacio de las matrices de sufijos pueden seguir siendo prohibitivos. Analizado 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 , un genoma humano con y la matriz de sufijos ocuparía aproximadamente 16 veces más memoria que el propio genoma. ${\displaystyle {\mathcal {O}}(n\log n)}$ ${\displaystyle \sigma }$ ${\displaystyle {\mathcal {O}}(n\log \sigma )}$ ${\displaystyle \sigma =4}$ ${\displaystyle n=3.4\times 10^{9}}$

Tales 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 sólo espacio dentro del tamaño del texto o incluso menos.

Algoritmos de construcción

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

Un enfoque ingenuo para construir una matriz de sufijos es utilizar un algoritmo de clasificación 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 general de este enfoque es . ${\displaystyle {\mathcal {O}}(n\log n)}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n^{2}\log n)}$

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

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

Uno de los primeros algoritmos en lograr todos los objetivos es 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 por parte de Yuta Mori ^[8] supera a la mayoría de los otros enfoques de construcción lineal o superlineal.

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 admitido : 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] ${\displaystyle 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. Luego, 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 clasificación rápida de los sufijos restantes. La diferencia es que estos algoritmos favorecen la iteración sobre la recursividad para ordenar el subconjunto de sufijos seleccionado. Puglisi, Smyth y Turpin (2007) han elaborado un estudio de este grupo diverso de algoritmos.

Un algoritmo recursivo bien 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 de memoria externa ^[10] y paralela ^[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 dinámicas de sufijos es generalmente más eficiente que la reconstrucción cuando se considera la inserción de un número razonable de letras en el texto original. ${\displaystyle {\mathcal {O}}(n\log n)}$

En trabajos prácticos de código abierto , una rutina comúnmente utilizada para la construcción de matrices de sufijos era qsufsort, basada en el algoritmo de Larsson-Sadakane de 1999. ^[12] Esta rutina ha sido reemplazada por DivSufSort de Yuta Mori, "el algoritmo de clasificació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 [14]} presentó una implementación más rápida del algoritmo 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 está ordenada lexicográficamente con todos los sufijos de cada cadena) ^. ${\displaystyle 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 aparición de un patrón de subcadena dentro de la cadena . 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 la matriz de sufijos y se podrán encontrar de manera 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: ^{[ cita necesaria ]} ${\displaystyle P}$ ${\displaystyle S}$

n  =  len ( S ) def  search ( P :  str )  ->  Tupla [ int ,  int ]: """  Devuelve índices (s, r) tales que el intervalo A[s:r] (incluido el  índice final) representa todos 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 mientras 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 si P > suffixAt ( A [ mid ]): l = mid + 1 else : r = mid s = l                                        # Encuentra la posición final del intervalo  r  =  n  while  l  <  r :  mid  =  ( l  +  r )  //  2  if  suffixAt ( A [ mid ]) . comienza con ( P ):  l  =  medio  +  1  más :  r  =  medio  retorno  ( s ,  r )

Encontrar el patrón de longitud de subcadena en la cadena de longitud lleva tiempo, dado que una comparación de sufijo único 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 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 para un tamaño de alfabeto constante, como se conoce por los árboles de sufijos . ${\displaystyle P}$ ${\displaystyle m}$ ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {O}}(m\log n)}$ ${\displaystyle m}$ ${\displaystyle {\mathcal {O}}(m+\log n)}$ ${\displaystyle {\mathcal {O}}(m)}$

Se pueden utilizar algoritmos de clasificación de sufijos para calcular la transformada de Burrows-Wheeler (BWT) . El BWT requiere ordenar 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, el BWT se puede calcular en tiempo lineal construyendo primero una matriz de sufijos del texto y luego deduciendo la cadena BWT : . ${\displaystyle 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 exige 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 el apartado de aplicación de este último.

Matrices de sufijos mejoradas

Los árboles de sufijos son poderosas estructuras de datos que tienen una amplia aplicación en áreas de coincidencia de patrones y cadenas, indexación y estadísticas textuales. Sin embargo, ocupa una cantidad significativa de espacio y, por tanto, tiene 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 constan de matrices de sufijos y una tabla adicional llamada tabla secundaria que contiene 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 vinculada. 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 utilice un árbol de sufijos utilizando 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:

1. pos array pos[1,...n]: Representa una lista ordenada de todos los sufijos S. Sólo las posiciones iniciales de los sufijos se almacenan en la matriz para reducir la complejidad del espacio 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.

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 algunos 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 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 n matrices, up , down y nextlIndex . La información sobre los bordes del árbol de sufijos correspondiente se almacena y mantiene mediante las matrices arriba y abajo . La matriz nextlIndex almacena los enlaces en la lista enlazada utilizada para la bifurcación de nodos del árbol de sufijos.

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

1. El elemento up[i] registra el índice inicial del intervalo secundario del intervalo lcp-segundo más largo, que termina en el índice i-1 .
2. El índice inicial del segundo intervalo secundario del intervalo lcp más largo, comenzando en el índice i, se almacena en el elemento down[i] .
3. Si y solo si el intervalo no es el primer hijo ni el hijo final 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, la tabla secundaria se puede construir en tiempo lineal. Los valores arriba/abajo y los valores nextlIndex se pueden calcular por separado utilizando dos algoritmos distintos.

Construyendo una tabla de enlaces de sufijos

Los enlaces de sufijo para una matriz de sufijo 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 va de 0 a n. La tabla de enlaces de sufijos se construye mediante el recorrido de izquierda a derecha del árbol de intervalo lcp. Cada vez que se calcula un intervalo l , se agrega a la lista de intervalos l, que se conoce como 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 ( l -1) -lista, 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 lyr se almacenan finalmente en el primer índice de [i,...,j] .

Notas

1. Abouelhoda, Kurtz y Ohlebusch 2004.
2. Yo, Kärkkäinen y Kempa 2014.
3. Gawrychowski y Kociumaka 2017.
4. Abouelhoda, Kurtz y Ohlebusch 2002.
5. Kurtz 1999.
6. Puglisi, Smyth y Turpin 2007.
7. Fischer 2011.
8. Mori, Yuta. "dice". Archivado desde el original el 9 de marzo de 2023 . Consultado el 31 de agosto de 2023 .
9. Burkhardt y Kärkkäinen 2003.
10. Kulla y Sanders 2007.
11. Dementiev y col. 2008.
12. 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.
13. Fischer, Johannes; Kurpicz, Florian (5 de octubre de 2017). "Desmantelamiento de DivSufSort". Actas de la Conferencia de Stringología de Praga 2017 . arXiv : 1710.01896 .
14. "Nueva biblioteca saca y bwt (libsais)". codificar.su . Consultado el 3 de octubre de 2021 .
15. Grebnov, Ilya (22 de septiembre de 2021), libsais , consultado el 2 de octubre de 2021
16. 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 Computación . 22 (5): 935–948. doi :10.1137/0222058. S2CID  5074629.
• Gawrychowski, Paweł; Kociumaka, Tomasz (enero de 2017). "Construcción de árbol de sufijos dispersos en tiempo y espacio óptimos". Actas del vigésimo octavo simposio anual ACM-SIAM sobre algoritmos discretos . Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas: 425–439. arXiv : 1608.00865 . doi :10.1137/1.9781611974782.27. ISBN 9781611974782. S2CID  6608776.
• Li, Zhize; Li, Jian; Huo, Hongwei (2016). Clasificación óptima de sufijos in situ . Actas del 25º Simposio internacional sobre procesamiento de cadenas y recuperación de información (SPIRE). Apuntes de conferencias sobre informática. vol. 11147. Saltador. 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 múltiples cadenas: un método para búsquedas de múltiples cadenas en línea". Concurrencia y paralelismo, programación, redes y seguridad . Apuntes de conferencias sobre informática. vol. 1179. Springer Berlín 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 conferencias sobre 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". Revista de algoritmos discretos . 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). "Reducir el requisito 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, Simón J.; Smith, WF; Turpin, Andrew H. (2007). "Una taxonomía de algoritmos de construcción de matrices de sufijos". Encuestas de Computación ACM . 39 (2): 4. doi :10.1145/1242471.1242472. S2CID  2653529.
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). "Construcción de matriz de sufijos lineales mediante clasificación inducida casi pura" . Conferencia sobre compresión de datos de 2009. pag. 193. doi :10.1109/DCC.2009.42. ISBN 978-0-7695-3592-0.
• Fischer, Johannes (2011). Inducir el LCP-Array . Algoritmos y estructuras de datos. Apuntes de conferencias sobre 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.; Leonardo, M.; Mouchard, L. (2010). "Matrices dinámicas de sufijos extendidos". Revista de algoritmos discretos . 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 matrices de sufijos" . Coincidencia de patrones combinatorios. Apuntes de conferencias sobre 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 ACM sobre teoría de la informática - STOC '72. págs. 125-136. doi : 10.1145/800152.804905.
• Farach, M. (1997). Óptima construcción de árbol 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; Lijadoras, Peter (2003). Construcción de matriz de sufijos de trabajo lineal simple . Autómatas, Lenguajes y Programación. Apuntes de conferencias sobre 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, Fabián; Lijadoras, Peter (2007). "Construcción de matriz de sufijos paralelos escalable". Computación paralela . 33 (9): 605–612. doi :10.1016/j.parco.2007.06.004.
• Mohamed Ibrahim Abouelhoda, Stefan Kurtz y Enno Ohlebusch. "Reemplazar árboles de sufijos con matrices de sufijos mejoradas". Revista de algoritmos discretos , 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 no despreciable". Apuntes de conferencias sobre procesamiento de cadenas y recuperación de información en informática , páginas 138-149, 2004.

enlaces externos

• Matriz de sufijos en Java
• Módulo de clasificación de sufijos para BWT en código C
• Implementación de matriz de sufijos en Ruby
• Biblioteca y herramientas de matrices de sufijos
• Proyecto que contiene varias implementaciones de Suffix Array c/c++ con una interfaz unificada
• Una biblioteca API C rápida, liviana y robusta para construir la matriz de sufijos
• Implementación de matriz de sufijos en Python
• Implementación de Linear Time Suffix Array en C usando árbol de sufijos