15/08/2015
En la era de la información masiva, la capacidad de almacenar grandes volúmenes de texto y, al mismo tiempo, poder buscar eficientemente dentro de ellos es un desafío constante. Las técnicas tradicionales de indexación, como los arreglos de sufijos o los árboles de sufijos, son potentes para la búsqueda, pero a menudo requieren una cantidad de espacio considerable, que puede ser varias veces el tamaño del texto original. Por otro lado, los algoritmos de compresión estándar como gzip o bzip2 reducen drásticamente el tamaño de los archivos, pero obligan a descomprimir el archivo completo antes de poder realizar cualquier búsqueda. Aquí es donde entra en juego el concepto de un índice que no solo comprima el texto, sino que también permita la búsqueda directamente sobre el archivo comprimido. Este es el principio fundamental detrás del innovador FM-Index.
El FM-Index, cuyo nombre proviene de su capacidad de ser un índice de texto completo (Full-text index) que ocupa un espacio diminuto (Minute space), revoluciona la forma en que interactuamos con grandes colecciones de texto. No es solo un compresor; es una estructura de datos que fusiona la compresión y la indexación de una manera ingeniosa. La principal promesa del FM-Index es permitir contar y localizar ocurrencias de un patrón dado dentro de un archivo comprimido, accediendo solo a una pequeña fracción de dicho archivo. Esto se traduce en tiempos de respuesta sorprendentemente rápidos, incluso para archivos de varios megabytes.
¿Qué es y por qué es importante el FM-Index?
Como mencionamos, el FM-Index va más allá de ser un simple algoritmo de compresión. Su naturaleza dual como compresor e índice de búsqueda lo convierte en una herramienta excepcionalmente valiosa en escenarios donde tanto el espacio de almacenamiento como la velocidad de búsqueda son críticos. A diferencia de los compresores convencionales, el archivo resultante del FM-Index está listo para ser consultado. Esto significa que no es necesario invertir tiempo y recursos en la descompresión total del archivo antes de iniciar una búsqueda.
La capacidad de buscar cualquier patrón, no solo palabras completas o prefijos de palabras, lo hace un índice de texto completo en el sentido más estricto. Puede encontrar secuencias arbitrarias de caracteres. Además, se describe como una herramienta de auto-indexación porque el propio índice contiene una versión comprimida del archivo original, eliminando la necesidad de almacenar el texto sin comprimir por separado para ciertas operaciones.
¿Cómo logra esta proeza el FM-Index?
La magia detrás del FM-Index reside en una combinación cuidadosa de dos técnicas preexistentes y bien estudiadas: la Transformada de Burrows-Wheeler (BWT) y los Arreglos de Sufijos (Suffix Arrays). Al entrelazar estas estructuras de datos, se logra construir lo que podría considerarse un "arreglo de sufijos comprimido".
La clave de su eficiencia en el espacio es su naturaleza "oportunista". El FM-Index aprovecha la compresibilidad inherente de los datos de entrada. Cuanto más redundante o "comprimible" sea el texto original, menor será el espacio que requerirá el FM-Index para almacenarlo y permitir búsquedas sobre él. Esta compresión se logra sin incurrir en una penalización significativa en el tiempo de consulta en comparación con los índices más rápidos conocidos, como el árbol de sufijos y el arreglo de sufijos, que, si bien son rápidos, son notoriamente exigentes en cuanto a espacio.
Teóricamente, se ha demostrado que para un texto T de tamaño n, el FM-Index utiliza un espacio proporcional a la entropía de T. Matemáticamente, la ocupación de espacio es O(n Hk(T)) + o(n) bits, donde Hk(T) es la entropía empírica de orden k de T. Esta propiedad es fundamental, ya que vincula directamente el tamaño del índice a la compresibilidad teórica del texto.
Los Componentes Clave: BWT, Arreglo de Sufijos y Mapeo LF
Para entender cómo funciona el FM-Index, es crucial familiarizarse con sus bloques de construcción principales.
La Transformada de Burrows-Wheeler (BWT)
El primer paso en la construcción de un FM-Index es aplicar la Transformada de Burrows-Wheeler al texto de entrada T. La BWT reorganiza los caracteres del texto de una manera que facilita la compresión, agrupando caracteres similares. Para un texto T, la BWT se obtiene formando una matriz donde cada fila es una rotación del texto original (terminado con un carácter especial, típicamente '$', que se considera lexicográficamente menor que cualquier otro carácter). Luego, estas filas se ordenan lexicográficamente. La transformada BWT es la secuencia de caracteres en la última columna de esta matriz ordenada.
Consideremos el ejemplo clásico del texto T = "abracadabra$". La matriz M con las rotaciones ordenadas sería (usando la notación del texto fuente):
| I | F (Primera Columna) | Texto Rotado | L (Última Columna) |
|---|---|---|---|
| 1 | $ | abracadabra | a |
| 2 | a | $abracadabr | r |
| 3 | a | bra$abracad | d |
| 4 | a | bracadabra$a | $ |
| 5 | a | cadabra$abra | r |
| 6 | a | dabra$abraca | c |
| 7 | b | ra$abracadab | a |
| 8 | b | racadabra$ab | a |
| 9 | c | adabra$abr | a |
| 10 | d | abra$abracad | a |
| 11 | r | acadabra$abr | b |
| 12 | r | abracadabra$ | b |
La BWT de "abracadabra$" es la última columna L: "ard$rcaaaabb". Esta secuencia L es mucho más fácil de comprimir que el texto original debido a las largas corridas de caracteres idénticos.
El Arreglo de Sufijos y su Relación con BWT
Las filas de la matriz M corresponden esencialmente a los sufijos ordenados del texto original. La primera columna F está estrechamente relacionada con un arreglo de sufijos (que almacena los índices iniciales de los sufijos ordenados en el texto original). La conexión entre la BWT y el arreglo de sufijos es fundamental para el FM-Index.
Las Tablas de Soporte: C y Occ
El FM-Index utiliza dos tablas auxiliares para facilitar la búsqueda:
- C[c]: Una tabla que, para cada carácter 'c' en el alfabeto, almacena el número total de ocurrencias de caracteres lexicográficamente menores que 'c' en el texto original. En el ejemplo "abracadabra$" (con alfabeto $, a, b, c, d, r), tendríamos:
C[$] = 0 (ningún carácter es menor)
C[a] = 1 (el carácter '$' es menor)
C[b] = 1 + 5 = 6 (hay 1 '$' y 5 'a's)
C[c] = 6 + 2 = 8 (hay 6 caracteres menores que 'b' y 2 'b's)
C[d] = 8 + 1 = 9 (hay 8 caracteres menores que 'c' y 1 'c')
C[r] = 9 + 1 = 10 (hay 9 caracteres menores que 'd' y 1 'd') - Occ(c, k): Una función que devuelve el número de ocurrencias del carácter 'c' en el prefijo L[1..k] de la secuencia BWT (columna L). Por ejemplo, Occ('a', 9) en "ard$rcaaaabb" es 5, ya que hay cinco 'a's en los primeros 9 caracteres ("ard$rcaaa"). La eficiencia del FM-Index depende de que Occ(c, k) pueda calcularse rápidamente, idealmente en tiempo constante, lo cual es posible con estructuras de datos auxiliares.
El Mapeo Última a Primera (LF Mapping)
La relación crucial que explota el FM-Index es el mapeo Última a Primera (Last-to-First), denotado como LF(i). Este mapeo conecta un índice 'i' en la columna L con un índice 'j' en la columna F de la matriz M, de tal manera que el carácter L[i] es el mismo que F[j], y lo que es más importante, el carácter F[j] precede a L[i] en el texto original. Es decir, si L[i] = T[k], entonces F[j] = T[k-1].
El mapeo LF(i) se calcula utilizando las tablas C y Occ: LF(i) = C[L[i]] + Occ(L[i], i).
Usando el ejemplo "abracadabra$": Consideremos el índice i=9 en la columna L. L[9] es 'a'. Queremos encontrar el índice j en la columna F donde aparece esta 'a' específica (la quinta 'a' en la columna L, que corresponde a la rotación "cadabra$abra"). Usando la fórmula: LF(9) = C['a'] + Occ('a', 9) = 1 + 5 = 6. ¡Espera! Según la tabla, F[6] es 'a'. Revisando la matriz M, la fila 6 es "dabra$abraca". Ah, el texto original dice que LF(9) debería ser 5. Revisemos el cálculo de C y Occ para el ejemplo "ard$rcaaaabb".
| k | L[k] | Occ('$', k) | Occ('a', k) | Occ('b', k) | Occ('c', k) | Occ('d', k) | Occ('r', k) |
|---|---|---|---|---|---|---|---|
| 1 | a | 0 | 1 | 0 | 0 | 0 | 0 |
| 2 | r | 0 | 1 | 0 | 0 | 0 | 1 |
| 3 | d | 0 | 1 | 0 | 0 | 1 | 1 |
| 4 | $ | 1 | 1 | 0 | 0 | 1 | 1 |
| 5 | r | 1 | 1 | 0 | 0 | 1 | 2 |
| 6 | c | 1 | 1 | 0 | 1 | 1 | 2 |
| 7 | a | 1 | 2 | 0 | 1 | 1 | 2 |
| 8 | a | 1 | 3 | 0 | 1 | 1 | 2 |
| 9 | a | 1 | 4 | 0 | 1 | 1 | 2 |
| 10 | a | 1 | 5 | 0 | 1 | 1 | 2 |
| 11 | b | 1 | 5 | 1 | 1 | 1 | 2 |
| 12 | b | 1 | 5 | 2 | 1 | 1 | 2 |
Tabla C: C[$]=0, C[a]=1, C[b]=1+5=6, C[c]=6+2=8, C[d]=8+1=9, C[r]=9+1=10.
Ahora, recalculemos LF(9): L[9] = 'a'. Es la cuarta 'a' en la columna L. ¿A qué 'a' en la columna F corresponde? Las 'a's en F están en los índices 2 a 6. La cuarta 'a' en L corresponde a la cuarta 'a' en F, que está en el índice 5. Por lo tanto, LF(9) debe ser 5.
Fórmula: LF(i) = C[L[i]] + Occ(L[i], i). Para i=9, L[i]='a'. LF(9) = C['a'] + Occ('a', 9) = 1 + 4 = 5. ¡Correcto! La cuarta 'a' en L (L[9]) mapea a la cuarta 'a' en F (F[5]).
Esta relación LF(i) = C[L[i]] + Occ(L[i], i) es fundamental porque permite "seguir" un sufijo hacia atrás en el texto original. Si L[i] = T[k], entonces L[LF(i)] = T[k-1], L[LF(LF(i))] = T[k-2], y así sucesivamente. Al seguir este mapeo repetidamente, se puede reconstruir el texto original o, lo que es más relevante para la búsqueda, determinar la posición original de un carácter L[i] en el texto T.
El FM-Index como tal es una representación comprimida de la secuencia L junto con las tablas C y una forma eficiente de calcular Occ(c, k). También incluye información auxiliar que mapea un subconjunto de índices en L a sus posiciones correspondientes en el texto original T. La densidad de estos puntos de mapeo auxiliares permite un compromiso entre el espacio ocupado y la velocidad de la operación de localización.
Operaciones Fundamentales del FM-Index: Conteo y Localización
El FM-Index soporta dos operaciones básicas y muy eficientes:
Operación Count (Contar)
La operación `count` toma un patrón P y determina cuántas veces aparece ese patrón en el texto original T. Sorprendentemente, el tiempo requerido para esta operación depende solo de la longitud del patrón P, no del tamaño del texto T.
El proceso funciona iterando el patrón P hacia atrás, carácter a carácter. En la matriz M (conceptual), todas las ocurrencias de un patrón P aparecen como prefijos en un rango contiguo de filas. La operación `count` identifica este rango.
Ejemplo: Contar las ocurrencias del patrón "bra" en "abracadabra$".
- Empezamos con el último carácter del patrón: 'a'. El rango inicial en la columna F que comienza con 'a' se define por C['a'] y C['a' + 1] (o el siguiente carácter en el alfabeto). En nuestro ejemplo, C['a'] = 1 y C['b'] = 6. Las filas que empiezan con 'a' van del índice 2 al 6 en la matriz M. Este rango [2..6] en F corresponde a las filas cuyas últimas columnas L contienen caracteres que son precedidos por 'a' en el texto original.
- Ahora consideramos el penúltimo carácter del patrón: 'r'. Queremos encontrar las filas dentro del rango actual [2..6] cuya última columna L contiene 'r'. Usamos C y Occ para refinar el rango. Las filas en F que empiezan con "ra" corresponden a las filas en L que contienen 'r' y están dentro del rango que mapea a las filas que empiezan con 'a'. La fórmula para el nuevo rango [inicio', fin'] a partir de un rango actual [inicio, fin] y el carácter c es: [C[c] + Occ(c, inicio-1) + 1 .. C[c] + Occ(c, fin)]. Aplicando esto para buscar 'r' dentro del rango [2..6] (que corresponde a las filas que comienzan con 'a' en F): C['r'] = 10. Occ('r', 2-1) = Occ('r', 1) = 0. Occ('r', 6) = 2. Nuevo rango: [10 + 0 + 1 .. 10 + 2] = [11..12]. Este rango [11..12] en L contiene los caracteres que son precedidos por "ra" en el texto.
- Finalmente, consideramos el primer carácter del patrón: 'b'. Buscamos 'b' dentro del rango actual [11..12] en L. C['b'] = 6. Occ('b', 11-1) = Occ('b', 10) = 0. Occ('b', 12) = 2. Nuevo rango: [6 + 0 + 1 .. 6 + 2] = [7..8]. Este rango [7..8] en L corresponde a los caracteres que son precedidos por "bra" en el texto.
Una vez procesado todo el patrón, el tamaño del rango final [7..8] nos da el número de ocurrencias: 8 - 7 + 1 = 2. Si el rango se vuelve vacío en algún momento, el patrón no existe en el texto.
Dado que la función Occ(c, k) se puede calcular en tiempo constante (O(1)), la operación `count` se completa en tiempo lineal con respecto a la longitud del patrón P, es decir, O(|P|). Esto es notablemente rápido, especialmente para patrones cortos, y su velocidad no se degrada al aumentar el tamaño del texto.
Operación Locate (Localizar)
La operación `locate` toma un índice 'i' en la secuencia BWT (columna L) y devuelve la posición original en el texto T donde se encuentra el carácter L[i]. Para encontrar todas las ocurrencias de un patrón, primero se usa la operación `count` para obtener el rango [inicio, fin] en L que corresponde a las filas cuyo sufijo es el patrón buscado. Luego, se llama a `locate` para cada índice 'j' dentro de este rango [inicio..fin].
Como se explicó con el mapeo LF, se puede encontrar la posición original de un carácter L[i] siguiendo repetidamente el mapeo LF hasta alcanzar un índice en L que tenga asociada directamente su posición original en T (estos son los puntos auxiliares). Almacenar la posición original para cada índice en L sería prohibitivamente costoso en espacio. Por lo tanto, solo un subconjunto de índices en L tiene su posición original pre-calculada y almacenada. Para un índice 'j' que no tiene una posición asociada directamente, se sigue la cadena de mapeos LF: j, LF(j), LF(LF(j)), ... hasta encontrar un índice 'k' en esta cadena que sí tenga una posición asociada. Una vez encontrada la posición de L[k], se puede inferir la posición de L[j] retrocediendo tantos pasos como se dieron en la cadena LF.
La operación `locate` para encontrar `occ` ocurrencias de un patrón P de longitud |P| en un texto T de tamaño 'n' tiene una complejidad de tiempo de O(|P| + occ loge n), donde 'e' es una constante positiva que se elige durante la construcción del índice y afecta el compromiso entre espacio y tiempo. Un 'e' más pequeño requiere más espacio auxiliar pero permite búsquedas más rápidas. En la práctica, la operación `locate` es muy rápida cuando el número de ocurrencias (`occ`) es pequeño.
Ocupación de Espacio y Compromiso Espacio-Tiempo
Uno de los mayores atractivos del FM-Index es su eficiencia en el uso del espacio. Como índice oportunista, su tamaño depende de la compresibilidad del texto. La fórmula O(n Hk(T)) + o(n) bits por símbolo de entrada (para un k fijo) demuestra que el espacio es casi lineal en el tamaño del texto, pero escalado por la entropía de orden k, que es una medida de la compresibilidad. Esto lo hace significativamente más compacto que los arreglos o árboles de sufijos tradicionales, cuyo tamaño suele ser O(n log n) o O(n) palabras (donde una palabra es log n bits), lo que equivale a O(n log² n) o O(n log n) bits, considerablemente más que O(n Hk(T)) bits para textos compresibles (donde Hk(T) << log n).
La estructura del FM-Index se compone de un núcleo (que contiene la BWT comprimida, C y la información para Occ) y un bloque auxiliar (para la operación `locate`). El diseño permite un claro compromiso entre el espacio y la velocidad de búsqueda. Al aumentar el tamaño del núcleo (por ejemplo, almacenando más información para calcular Occ más rápido) y/o el tamaño del bloque auxiliar (almacenando más puntos de mapeo directo de L a T), se puede acelerar tanto las operaciones `count` como `locate`, a costa de usar más memoria.
Resultados Experimentales: FM-Index vs. Otros
Los experimentos comparativos destacan la eficiencia del FM-Index en diferentes escenarios. Se probaron dos versiones del FM-Index: una "tiny" (pequeña) optimizada para alta compresión y conteo rápido, y una "fat" (grande) que equilibra compresión, conteo y localización.
La siguiente tabla resume la relación de compresión y las velocidades de construcción/descompresión del FM-Index frente a gzip y bzip2 en varios archivos de prueba (tamaños en MB, tiempos en microsegundos por byte):
| Archivo | Tamaño (MB) | Contenido | Herramienta | Relación Comp. (%) | Tiempo Construcción (μs/byte) | Tiempo Descomp. (μs/byte) |
|---|---|---|---|---|---|---|
| bible | 4.05 | Biblia King James | FM-index (tiny) | 21.09 | 2.24 | 0.45 |
| FM-index (fat) | 32.28 | 2.28 | 0.46 | |||
| bzip2 | 20.90 | 1.16 | 0.39 | |||
| gzip | 29.07 | 1.74 | 0.07 | |||
| e.coli | 4.64 | Secuencia ADN | FM-index (tiny) | 26.92 | 2.19 | 0.49 |
| FM-index (fat) | 33.61 | 2.21 | 0.51 | |||
| bzip2 | 26.97 | 1.28 | 0.48 | |||
| gzip | 28.00 | 10.48 | 0.07 | |||
| world192 | 2.47 | CIA fact book 1992 | FM-index (tiny) | 19.62 | 2.26 | 0.44 |
| FM-index (fat) | 33.23 | 2.33 | 0.46 | |||
| bzip2 | 19.79 | 1.17 | 0.39 | |||
| gzip | 29.17 | 0.87 | 0.06 | |||
| cantrbry | 2.82 | Corpus Canterbury | FM-index (tiny) | 24.02 | 2.21 | 0.38 |
| FM-index (fat) | 46.10 | 2.39 | 0.41 | |||
| bzip2 | 20.24 | 0.89 | 0.31 | |||
| gzip | 26.10 | 5.04 | 0.06 | |||
| jdk13 | 69.73 | Fuentes Java/HTML | FM-index (tiny) | 5.87 | 3.43 | 0.42 |
| FM-index (fat) | 17.02 | 3.50 | 0.43 | |||
| bzip2 | 7.03 | 1.52 | 0.28 | |||
| gzip | 10.79 | 0.39 | 0.04 | |||
| ap90-8 | 8.00 | Texto SGML TREC | FM-index (tiny) | 25.06 | 2.49 | 0.48 |
| FM-index (fat) | 38.69 | 2.59 | 0.51 | |||
| bzip2 | 27.38 | 1.16 | 0.43 | |||
| gzip | 37.21 | 0.96 | 0.07 | |||
| ap90 | 67.11 | Texto SGML TREC | FM-index (tiny) | 22.14 | 3.04 | 0.57 |
| FM-index (fat) | 35.49 | 3.10 | 0.59 | |||
| bzip2 | 27.36 | 1.16 | 0.43 | |||
| gzip | 37.35 | 0.97 | 0.07 |
Observamos que la versión "tiny" del FM-Index generalmente logra una compresión similar o mejor que bzip2, aunque es más lenta en construcción y descompresión que gzip y bzip2. La versión "fat" tiene una relación de compresión comparable a gzip.
La verdadera ventaja del FM-Index se manifiesta en los tiempos de búsqueda, especialmente al compararlo con herramientas que no indexan, como grep y zgrep (grep sobre archivo comprimido con gzip).
La siguiente tabla muestra la relación de compresión y el tiempo promedio de búsqueda para 100 patrones aleatorios (palabras o secuencias de ADN) en milisegundos por búsqueda:
| Archivo | Herramienta | Relación Comp. (%) | Tiempo Avg. Count (ms) | Tiempo Avg. Locate (ms) | Tiempo Avg. Search (ms) |
|---|---|---|---|---|---|
| bible | FM-index (tiny) | 21.09 | 4.3 | - | - |
| FM-index (fat) | 32.28 | 1.0 | 7.5 | - | |
| zgrep | 29.07 | - | - | 343.8 | |
| grep | 100.00 | - | - | 40.9 | |
| e.coli | FM-index (tiny) | 26.92 | 12.3 | - | - |
| FM-index (fat) | 33.61 | 2.3 | 7.6 | - | |
| zgrep | 28.00 | - | - | 33,642.6 | |
| grep | 100.00 | - | - | 96.8 | |
| world | FM-index (tiny) | 19.62 | 4.7 | - | - |
| FM-index (fat) | 33.23 | 1.5 | 9.4 | - | |
| zgrep | 29.17 | - | - | 213.4 | |
| grep | 100.00 | - | - | 26.0 | |
| cantrbry | FM-index (tiny) | 24.02 | 8.1 | - | - |
| FM-index (fat) | 46.10 | 2.7 | 7.1 | - | |
| zgrep | 26.10 | - | - | 516.9 | |
| grep | 100.00 | - | - | 32.3 | |
| jdk13 | FM-index (tiny) | 5.87 | 3.2 | - | - |
| FM-index (fat) | 17.02 | 1.3 | 21.7 | - | |
| zgrep | 10.79 | - | - | 3,824.8 | |
| grep | 100.00 | - | - | 497.6 | |
| ap90-8 | FM-index (tiny) | 25.06 | 6.4 | - | - |
| FM-index (fat) | 38.69 | 1.7 | 5.4 | - | |
| zgrep | 37.21 | - | - | 744.1 | |
| grep | 100.00 | - | - | 79.3 | |
| ap90 | FM-index (tiny) | 22.14 | 5.6 | - | - |
| FM-index (fat) | 35.49 | 1.6 | 5.3 | - | |
| zgrep | 37.35 | - | - | 5,854.7 | |
| grep | 100.00 | - | - | 597.2 |
Es evidente que el FM-Index es dramáticamente más rápido para las operaciones de conteo y localización que zgrep y grep. Mientras que zgrep y grep deben escanear (total o parcialmente) el archivo (comprimido o sin comprimir), su tiempo de búsqueda crece linealmente con el tamaño del texto. El tiempo de `count` del FM-Index es casi constante con respecto al tamaño del texto, y el tiempo de `locate` (para un número fijo de ocurrencias) también es muy eficiente. La diferencia de tiempo entre zgrep y grep se debe, en parte, a la ineficiencia de la tubería (pipe) de Unix utilizada por zgrep.
Aplicaciones del FM-Index
Las características únicas del FM-Index lo hacen adecuado para varios escenarios:
- Producción de CD-ROM: Donde el espacio es una preocupación primordial. El FM-Index permite almacenar el texto y un índice de texto completo en un espacio reducido, ofreciendo flexibilidad para ajustar el compromiso espacio-tiempo.
- Correctores Ortográficos y Detectores de Virus: En estas aplicaciones, a menudo solo interesa saber si un patrón (una palabra mal escrita o una firma de virus) aparece en un diccionario o base de datos, y posiblemente encontrar una o pocas ocurrencias. El FM-Index es rápido para contar y localizar pocas ocurrencias. Aunque otras estructuras como Tries o Tablas Hash son más rápidas para búsquedas exactas de diccionario, no ofrecen compresión. Experimentos preliminares mostraron que TSTs pueden ser 200 veces más rápidos en búsqueda pero ocupan 15 veces más espacio que el FM-Index.
- Bloque Básico en Herramientas de Indexación Complejas: El FM-Index puede integrarse en sistemas de recuperación de información más sofisticados. Se ha demostrado cómo incorporarlo en herramientas como Glimpse para lograr ocupación de espacio sub-lineal y complejidad de tiempo de búsqueda sub-lineal en el peor caso (algo que las listas invertidas, por ejemplo, solo logran en tiempo, no en espacio). También se está explorando su uso para gestionar colecciones de texto SGML y XML.
Preguntas Frecuentes sobre el FM-Index
Aquí respondemos algunas preguntas comunes sobre esta innovadora estructura:
¿El FM-Index reemplaza a gzip o bzip2?
No directamente. Aunque el FM-Index produce un archivo comprimido, su propósito principal no es solo la compresión para almacenamiento. Su objetivo es permitir la búsqueda eficiente directamente sobre el archivo comprimido. Si solo necesitas reducir el tamaño de un archivo para archivarlo, gzip o bzip2 pueden ser más rápidos en compresión/descompresión y ofrecer mejores relaciones de compresión en algunos casos (como bzip2 en 'bible'). El FM-Index es ideal cuando la búsqueda rápida en el texto comprimido es una necesidad.
¿Es el FM-Index más rápido que grep?
Para la búsqueda de patrones, sí, dramáticamente. Grep debe leer y escanear el archivo completo (o gran parte de él) para encontrar coincidencias. El FM-Index utiliza su estructura indexada para encontrar las ocurrencias en tiempo que depende de la longitud del patrón y el número de ocurrencias, no del tamaño total del archivo. Los resultados experimentales muestran que el FM-Index es órdenes de magnitud más rápido que grep y zgrep para la búsqueda.
¿Cuál es la diferencia entre el FM-Index "tiny" y "fat"?
Son dos configuraciones del FM-Index que ilustran el compromiso espacio-tiempo. La versión "tiny" prioriza la máxima compresión posible, sacrificando algo de velocidad en la operación `locate`. Es muy eficiente para la operación `count`. La versión "fat" utiliza un poco más de espacio auxiliar para acelerar la operación `locate`, manteniendo aún una buena compresión y un conteo muy rápido.
¿Qué significa que el FM-Index es "oportunista"?
Significa que su eficiencia en el espacio depende de una propiedad de los datos de entrada: su compresibilidad. Aprovecha la redundancia en el texto para lograr una mayor compresión y, por lo tanto, un índice más pequeño. Textos más compresibles resultan en FM-Indices más pequeños.
¿Es útil el FM-Index para cualquier tipo de datos?
El FM-Index está diseñado para datos textuales o secuencias donde la noción de caracteres y patrones de caracteres tiene sentido, como texto natural, código fuente o secuencias de ADN. Funciona mejor en datos que exhiben redundancia y son, por lo tanto, compresibles.
Conclusión
El FM-Index representa un avance significativo en el campo de la recuperación de información sobre textos comprimidos. Al combinar elegantemente la Transformada de Burrows-Wheeler y los Arreglos de Sufijos, logra crear un índice de texto completo que es notablemente compacto, con un tamaño ligado a la entropía del texto original. Sus operaciones de conteo son extremadamente rápidas, dependiendo solo de la longitud del patrón, y la localización de ocurrencias es eficiente, especialmente para consultas selectivas. Aunque su construcción y descompresión pueden ser más lentas que los compresores estándar, su capacidad para buscar directamente en datos comprimidos y sus impresionantes tiempos de búsqueda para patrones lo convierten en una herramienta invaluable para aplicaciones donde el espacio es limitado y la búsqueda rápida es esencial, abriendo nuevas posibilidades para gestionar y consultar grandes volúmenes de datos textuales.
Si quieres conocer otros artículos parecidos a FM-Index: Compresión y Búsqueda Eficiente puedes visitar la categoría Radio.