Matriz de sufijos comprimidos - Compressed suffix array

En informática , una matriz de sufijos comprimidos 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 . 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 es típicamente , en donde 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 resolvió un problema abierto de larga data al mostrar que la coincidencia rápida de patrones era posible utilizando solo una estructura de datos de espacio lineal, es decir, una proporcional al tamaño del texto T , que toma bits. La matriz de sufijos y el árbol de sufijos convencionales utilizan bits, que son sustancialmente más grandes. La base para la estructura de datos es una descomposición recursiva usando 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 trabajo siguiente mostró que el espacio de almacenamiento real estaba relacionado con la entropía de orden cero y que el índice admite la autoindexación. 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 ondas . El uso del espacio es extremadamente competitivo en la práctica con otros compresores de última generación 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 generalmente 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 usa la dualidad geométrica aprovecha el acceso a bloques proporcionado por los discos para acelerar significativamente el tiempo de E / S. Además, se ha demostrado un rendimiento de búsqueda potencialmente práctico para una matriz de sufijos comprimidos en la memoria externa.

Implementaciones de código abierto

Hay varias implementaciones de código abierto de matrices de sufijos comprimidos disponibles (consulte 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

  1. ^ 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.
  2. ↑ a b Paolo Ferragina y Giovanni Manzini (2000). "Estructuras de datos oportunistas con aplicaciones". Actas del 41º Simposio Anual sobre Fundamentos de la Informática. p. 390.
  3. ^ 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.
  4. ^ 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 de informática, vol. 1969, Springer, diciembre de 2000, 410-421.
  5. ^ 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.
  6. ^ 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.
  7. ^ 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: