En informática , una matriz de sufijos comprimidos [1] [2] [3] es una estructura de datos comprimidos para la coincidencia de patrones . Las matrices de sufijos comprimidos son una clase general de estructura de datos que mejoran la matriz de sufijos . [1] [2] Estas estructuras de datos permiten una búsqueda rápida de una cadena arbitraria con un índice comparativamente pequeño.
Dado un texto T de n caracteres de un alfabeto Σ, un comprimido soportes sufijo matriz búsqueda de patrones arbitrarios en T . Para un patrón de entrada P de m caracteres, el tiempo de búsqueda es típicamente O ( m ) u O ( m + log ( n )). El espacio utilizado suele ser, dónde es el k-ésimo orden entropía empírica del texto T . El tiempo y el espacio para construir una matriz de sufijos comprimidos son normalmente.
La instanciación original de la matriz de sufijos comprimidos [1] resolvió un problema abierto de larga data al mostrar que la coincidencia rápida de patrones era posible usando solo una estructura de datos de espacio lineal, es decir, una proporcional al tamaño del texto T , que tomabits. La matriz de sufijos convencional y el uso del árbol de sufijosbits, que es sustancialmente más grande. La base de la estructura de datos es una descomposición recursiva utilizando la "función de vecino", que permite que una matriz de sufijos sea representada por uno de la mitad de su longitud. La construcción se repite varias veces hasta que la matriz de sufijos resultante utiliza un número lineal de bits. El siguiente trabajo mostró que el espacio de almacenamiento real estaba relacionado con la entropía de orden cero y que el índice admite la autoindexación. [4] El límite de espacio se mejoró aún más para lograr el objetivo final de la entropía de orden superior; la compresión se obtiene dividiendo la función vecina por contextos de orden superior y comprimiendo cada partición con un árbol de ondículas . [3] El uso del espacio es extremadamente competitivo en la práctica con otros compresores de última generación, [5] y también admite una rápida coincidencia de patrones.
Los accesos a la memoria realizados por matrices de sufijos comprimidos y otras estructuras de datos comprimidos para la coincidencia de patrones normalmente no están localizados y, por lo tanto, estas estructuras de datos han sido notoriamente difíciles de diseñar de manera eficiente para su uso en memoria externa . El progreso reciente que utiliza la dualidad geométrica aprovecha el acceso a bloques proporcionado por los discos para acelerar significativamente el tiempo de E / S [6]. Además, se ha demostrado un rendimiento de búsqueda potencialmente práctico para una matriz de sufijos comprimidos en la memoria externa. [7]
Implementaciones de código abierto
Hay varias implementaciones de código abierto de matrices de sufijos comprimidos disponibles (consulte los enlaces externos a continuación). Bowtie y Bowtie2 son implementaciones de matriz de sufijos comprimidos de código abierto de alineación de lectura para su uso en bioinformática . La biblioteca de estructura de datos sucinta (SDSL) es una biblioteca que contiene una variedad de estructuras de datos comprimidas, incluidas matrices de sufijos comprimidos. FEMTO es una implementación de matrices de sufijos comprimidos para memoria externa. Además, una variedad de implementaciones, incluidas las implementaciones originales del índice FM , están disponibles en el sitio web de Pizza & Chili (ver enlaces externos).
Ver también
Referencias
- ^ a b c R. Grossi y JS Vitter, Matrices de sufijos comprimidos y árboles de sufijos, con aplicaciones a la indexación de texto y la coincidencia de cadenas, SIAM Journal on Computing, 35 (2), 2005, 378-407. Una versión anterior apareció en Proceedings of the 32nd ACM Symposium on Theory of Computing, mayo de 2000, págs. 397-406.
- ↑ a b Paolo Ferragina y Giovanni Manzini (2000). "Estructuras de datos oportunistas con aplicaciones". Actas del 41º Simposio Anual sobre Fundamentos de las Ciencias de la Computación. p. 390.
- ^ a b R. Grossi, A. Gupta y JS Vitter, Índices de texto comprimido con entropía de alto orden, Actas del 14º Simposio anual SIAM / ACM sobre algoritmos discretos, enero de 2003, 841-850.
- ^ K. Sadakane, Bases de datos de texto comprimido con algoritmos de consulta eficientes basados en matrices de sufijos comprimidos, Actas del Simposio internacional sobre algoritmos y computación , Notas de la conferencia en Ciencias de la Computación, vol. 1969, Springer, diciembre de 2000, 410-421.
- ^ L. Foschini, R. Grossi, A. Gupta y JS Vitter, Indexación es igual a compresión: experimentos en matrices de sufijos y árboles , ACM Transactions on Algorithms , 2 (4), 2006, 611-639.
- ^ W.-K. Hon, R. Shah, SV Thankachan y JS Vitter, Sobre la indexación de texto comprimido con entropía en la memoria externa, Actas de la conferencia sobre procesamiento de cadenas y recuperación de información , agosto de 2009.
- ^ MP Ferguson, FEMTO: búsqueda rápida de colecciones de secuencias grandes , Actas de la 23a Conferencia Anual sobre Coincidencia de Patrones Combinatorios , julio de 2012
enlaces externos
Implementaciones: