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 .
Matriz de sufijo | ||
---|---|---|
Tipo | Formación | |
Inventado por | Manber y Myers (1990) | |
Complejidad del tiempo en notación O grande | ||
Promedio | Peor de los casos | |
Espacio | ||
Construcción |
Los arreglos de sufijos fueron introducidos por Manber y Myers (1990) como una alternativa simple y eficiente en el espacio a los árboles de sufijos . Gaston Gonnet los había descubierto de forma independiente en 1987 con el nombre de matriz PAT ( Gonnet, Baeza-Yates & Snider 1992 ).
Li, Li y Huo (2016) dieron el primer lugaralgoritmo de construcción de matriz de sufijo de tiempo 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.
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 la complejidad de la memoria. [1] La matriz de sufijos para un subconjunto de todos los sufijos de una cadena se llama matriz de sufijos dispersos . [2] Se han desarrollado múltiples algoritmos probabilísticos para minimizar el uso de memoria adicional, incluido un tiempo óptimo y un algoritmo de memoria. [3]
Definición
Dejar frijol -cadena y deja denotar la subcadena de que van desde a .
La matriz de sufijos de ahora se define como una matriz de enteros que proporcionan las posiciones iniciales de los sufijos deen orden lexicográfico . Esto significa, una entrada contiene la posición inicial del -th sufijo más pequeño en y así para todos : .
Cada sufijo de aparece en 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.
Ejemplo
Considere el texto = banana$
para ser indexado:
I | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
B | a | norte | a | norte | a | PS |
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:
Sufijo | I |
---|---|
banana $ | 1 |
anana $ | 2 |
nana $ | 3 |
ana $ | 4 |
na $ | 5 |
un $ | 6 |
PS | 7 |
Estos sufijos se pueden ordenar en orden ascendente:
Sufijo | I |
---|---|
PS | 7 |
un $ | 6 |
ana $ | 4 |
anana $ | 2 |
banana $ | 1 |
na $ | 5 |
nana $ | 3 |
La matriz de sufijos contiene las posiciones iniciales de estos sufijos ordenados:
yo = | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
= | 7 | 6 | 4 | 2 | 1 | 5 | 3 |
La matriz de sufijos con los sufijos escritos verticalmente debajo para mayor claridad:
yo = | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
= | 7 | 6 | 4 | 2 | 1 | 5 | 3 |
1 | PS | a | a | a | B | norte | norte |
2 | PS | norte | norte | a | a | a | |
3 | a | a | norte | PS | norte | ||
4 | PS | norte | a | a | |||
5 | a | norte | PS | ||||
6 | PS | a | |||||
7 | PS |
Así 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 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 hoja 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 de la matriz LCP .
Se ha demostrado que cada algoritmo de árbol de sufijos se puede reemplazar sistemáticamente con un algoritmo que usa una matriz de sufijos mejorada con información adicional (como la matriz LCP ) y resuelve el mismo problema con la misma complejidad de tiempo. [4] 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. [5]
Eficiencia espacial
Las matrices de sufijos fueron introducidas por Manber & Myers (1990) con el fin de mejorar los requisitos de espacio de los árboles de sufijos : Tienda de matrices de sufijosenteros. Suponiendo que un número entero requiere bytes, una matriz de sufijos requiere bytes en total. Esto es significativamente menor que elbytes que son necesarios para una implementación cuidadosa del árbol de sufijos. [6]
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. Para un genoma humano con y por tanto, la matriz de sufijos ocuparía unas 16 veces más memoria que el propio genoma.
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 solo requieren espacio dentro del tamaño del texto o incluso menos.
Algoritmos de construcción
Se puede construir un árbol de sufijos y se puede convertir en una matriz de sufijos atravesando la profundidad del árbol primero también en , por lo que existen algoritmos que pueden construir una matriz de sufijos en .
Un enfoque ingenuo para construir una matriz de sufijos es utilizar un algoritmo de clasificación basado en comparaciones . Estos algoritmos requieren comparaciones de sufijos, pero una comparación de sufijos se ejecuta en tiempo, por lo que el tiempo de ejecución general de este enfoque es .
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: [7]
- complejidad asintótica mínima
- liviano en el espacio, lo que significa poca o ninguna memoria de trabajo al lado del texto y se necesita 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 & Chan (2009) . El algoritmo también es bastante simple (<100 LOC ) y se puede mejorar para construir simultáneamente la matriz LCP . [8] El algoritmo SA-IS es uno de los algoritmos de construcción de matrices de sufijos más rápidos que se conocen. Una implementación cuidadosa de Yuta Mori supera a la mayoría de los otros 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 compatible : 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 dey alfabetos generales donde solo se permiten las comparaciones de caracteres. [9]
La mayoría de los algoritmos de construcción de matrices de sufijos se basan en uno de los siguientes enfoques: [7]
- Los algoritmos de duplicación de prefijos se basan en una estrategia de Karp, Miller y Rosenberg (1972) . La idea es encontrar prefijos que honren el orden lexicográfico de los sufijos. La longitud del prefijo evaluado 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 árbol de sufijos de Farach (1997) para ordenar recursivamente un subconjunto de sufijos. Este subconjunto se usa 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 un tipo rápido 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 / sesgo 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 paralelo [10] y memoria externa [11] .
El 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 del 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ámicos 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.
En el trabajo práctico de código abierto , una rutina de uso común 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]
Matriz de sufijo generalizado
El concepto de matriz de sufijos se puede extender a más de una cadena. Esto se denomina matriz de sufijos generalizados (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. [14]
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 cuerda . 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 podrán 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 ]
n = len ( S ) def búsqueda ( P : str ) -> Tuple [ int , int ]: "" " Índices de retorno (s, r) de manera que el intervalo A [s: r] (incluido el índice final ) represente 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 que l < r : mid = ( l + r ) // 2 # división redondeando hacia abajo al entero más cercano # sufijoAt (A [i]) es el i-ésimo sufijo más pequeño si P > sufijoAt ( 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 = mid + 1 else : r = mid return ( s , r )
Encontrar el patrón de subcadena de longitud en la cuerda de longitud acepta 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 paratiempo usando la información de LCP . La idea es que una comparación de patrones no necesita volver a comparar ciertos caracteres, cuando ya se sabe que son parte del prefijo común más largo del patrón y del intervalo de búsqueda actual. Abouelhoda, Kurtz & Ohlebusch (2004) harvtxt error: múltiples objetivos (2 ×): CITEREFAbouelhodaKurtzOhlebusch2004 ( ayuda ) mejorar el límite aún más y lograr un tiempo de búsqueda decomo se conoce a partir de árboles de sufijo .
Los algoritmos de clasificación de sufijos se pueden utilizar para calcular la transformada de Burrows-Wheeler (BWT) . El BWT requiere la clasificació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, el BWT se puede calcular en tiempo lineal construyendo primero una matriz de sufijos del texto y luego deduciendo la cadena BWT :.
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 se usa en la traducción automática estadística .
Muchas aplicaciones adicionales de la matriz de sufijos requieren la matriz LCP . Algunos de estos se detallan en la sección de aplicación de este último.
Notas
- ^ Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (marzo de 2004). "Reemplazo de árboles de sufijos con matrices de sufijos mejoradas" . Diario de algoritmos discretos . 2 (1): 53–86. doi : 10.1016 / s1570-8667 (03) 00065-0 . ISSN 1570-8667 .
- ^ Kärkkäinen, Juha; Ukkonen, Esko (1996), "Sparse suffix trees", Lecture Notes in Computer Science , Springer Berlin Heidelberg, págs. 219-230, doi : 10.1007 / 3-540-61332-3_155 , ISBN 9783540613329
- ^ Gawrychowski, Paweł; Kociumaka, Tomasz (enero de 2017). "Construcción de árbol de sufijo disperso 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 .
- ^ Abouelhoda, Kurtz y Ohlebusch 2004 . error sfn: varios objetivos (2 ×): CITEREFAbouelhodaKurtzOhlebusch2004 ( ayuda )
- ^ Abouelhoda, Kurtz y Ohlebusch 2002 .
- ^ Kurtz 1999 .
- ^ a b Puglisi, Smyth y Turpin 2007 .
- ^ Fischer, 2011 .
- ^ Burkhardt y Kärkkäinen 2003 .
- ^ Kulla y Sanders 2007 .
- ^ Dementiev y col. 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). "Desmontaje de DivSufSort". Actas de la Conferencia de Tetrología de Praga 2017 . arXiv : 1710.01896 .
- ^ Shi, Fei (1996), Arreglos de sufijos para múltiples cadenas: un método para búsquedas en línea de múltiples cadenas. , Lecture Notes in Computer Science, 1179 , Springer Berlin Heidelberg, págs. 11-22, doi : 10.1007 / BFb0027775 , ISBN 978-3-540-62031-0
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 .
- 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 en Ciencias de la Computación. 11147 . Saltador. págs. 268-284. arXiv : 1610.08305 . doi : 10.1007 / 978-3-030-00479-8_22 . ISBN 978-3-030-00478-1.
- Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). "Reemplazo de árboles de sufijos con matrices de sufijos mejoradas" . Diario de algoritmos discretos . 2 (1): 53–86. doi : 10.1016 / S1570-8667 (03) 00065-0 .
- Gonnet, GH; Baeza-Yates, RA; Snider, T (1992). "Nuevos índices de 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". Práctica y experiencia en software . 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 .
- 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 en Ciencias de la Computación . 2452 . pag. 449. doi : 10.1007 / 3-540-45784-4_35 . ISBN 978-3-540-44211-0.
- Puglisi, Simon J .; Smyth, 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 sufijo lineal mediante clasificación inducida casi pura . Conferencia de Compresión de Datos de 2009. pag. 193. doi : 10.1109 / DCC.2009.42 . ISBN 978-0-7695-3592-0.
- Fischer, Johannes (2011). Induciendo el LCP-Array . Algoritmos y estructuras de datos. Apuntes de conferencias en Ciencias de la Computación. 6844 . pag. 374. 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 dinámicas de sufijos extendidos" . Diario de algoritmos discretos . 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 conferencias en Ciencias de la Computación. 2676 . pag. 55. 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 computación - STOC '72. pag. 125. doi : 10.1145 / 800152.804905 .
- Farach, M. (1997). Construcción óptima del árbol de sufijos con grandes alfabetos . Actas 38º Simposio Anual sobre Fundamentos de la Informática. pag. 137. doi : 10.1109 / SFCS.1997.646102 . ISBN 0-8186-8197-7.
- Kärkkäinen, Juha; Sanders, Peter (2003). Construcción de matriz de sufijo de trabajo lineal simple . Autómatas, lenguajes y programación. Apuntes de conferencias en Ciencias de la Computación. 2719 . pag. 943. doi : 10.1007 / 3-540-45061-0_73 . ISBN 978-3-540-40493-4.
- Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). "Mejor construcción de matrices de sufijos de memoria externa" . Revista de algoritmos experimentales . 12 : 1-24. doi : 10.1145 / 1227161.1402296 . S2CID 12296500 .
- Kulla, Fabián; Sanders, Peter (2007). "Construcción de matrices de sufijos paralelos escalables". Computación paralela . 33 (9): 605. doi : 10.1016 / j.parco.2007.06.004 .
enlaces externos
- Matriz de sufijo en Java
- Módulo de clasificación de sufijo para BWT en código C
- Implementación de matriz de sufijo en Ruby
- Herramientas y biblioteca de matrices de sufijos
- Proyecto que contiene varias implementaciones de Suffix Array c / c ++ con una interfaz unificada
- Una biblioteca C API rápida, liviana y robusta para construir la matriz de sufijos
- Implementación de Suffix Array en Python
- Implementación de matriz de sufijo de tiempo lineal en C usando árbol de sufijos