Matriz de sufijos comprimida

En informática , un array de sufijos comprimido ^{[ 1 ] [ 2 ] [ 3 ]} es una estructura de datos comprimida para la búsqueda de patrones . Los arrays de sufijos comprimidos son una clase general de estructuras de datos que mejoran el array de sufijos . ^{[ 1 ] [ 2 ]} Estas estructuras de datos permiten una búsqueda rápida de una cadena arbitraria con un índice relativamente pequeño.

Dado un texto T de n caracteres de un alfabeto Σ, una matriz de sufijos comprimida permite buscar patrones arbitrarios en T. Para un patrón de entrada P de m caracteres, el tiempo de búsqueda suele ser O( m ) u O( m + log( n )). El espacio utilizado suele ser${\displaystyle O(nH_{k}(T))+o(n)}$, dónde${\displaystyle H_{k}(T)}$es la entropía empírica de orden k del texto T. El tiempo y el espacio para construir una matriz de sufijos comprimidos son normalmente${\displaystyle O(n)}$.​

La presentación original de una matriz de sufijos comprimida ^{[ 1 ]} resolvió un problema abierto de larga data al demostrar 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${\displaystyle O(n\,{\log |\Sigma |})}$bits. El arreglo de sufijos convencional y el árbol de sufijos utilizan${\displaystyle \Omega (n\,{\log n})}$bits, que es sustancialmente mayor. La base de la estructura de datos es una descomposición recursiva que utiliza la "función vecina", que permite que una matriz de sufijos se represente mediante una 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. Trabajos posteriores demostraron que el espacio de almacenamiento real estaba relacionado con el${\displaystyle 0^{th}}$entropía de orden - y que el índice admite autoindexación. ^{[ 4 ]} El límite de espacio se mejoró aún más logrando el objetivo final de entropía de orden superior; la compresión se obtiene particionando la función vecina por contextos de orden superior y comprimiendo cada partición con un árbol de ondículas . ^{[ 3 ]} El uso de espacio es extremadamente competitivo en la práctica con otros compresores de última generación, ^{[ 5 ]} y también admite coincidencia de patrones rápida in situ .

Los accesos a memoria que realizan las matrices de sufijos comprimidos y otras estructuras de datos comprimidas para la búsqueda de patrones no suelen estar localizados, por lo que diseñar estas estructuras de datos de forma eficiente para su uso en memoria externa ha sido notoriamente difícil . Los avances recientes que utilizan la dualidad geométrica aprovechan el acceso a bloques que proporcionan 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 memoria externa ^{[ 7 ] .}

Existen varias implementaciones de código abierto de matrices de sufijos comprimidos (véase Enlaces externos a continuación). Bowtie y Bowtie2 son implementaciones de código abierto de matrices de sufijos comprimidos para alineación de lecturas en bioinformática . La biblioteca Succinct Data Structure Library (SDSL) contiene diversas estructuras de datos comprimidas, incluidas matrices de sufijos comprimidos. FEMTO es una implementación de matrices de sufijos comprimidos para memoria externa. Además, en el sitio web de Pizza & Chili se encuentran disponibles diversas implementaciones, incluidas las originales de FM-index (véase Enlaces externos).

• Índice FM
• Matriz de sufijos

Implementaciones:

• Pajarita y Pajarita2
• Biblioteca de Estructuras de Datos Concisas (SDSL)
• FEMTO
• Sitio web de Pizza&Chili .