El FM-index (Full-text index in Minute space) es una estructura de datos auto-indexada y comprimida que permite realizar búsquedas de subcadenas (patrones) en un texto de manera eficiente, sin necesidad de descomprimirlo completamente. Se basa en la Burrows-Wheeler Transform (BWT), que reordena el texto para agrupar caracteres similares, facilitando la compresión. Complementa la BWT con estructuras de datos auxiliares como Wavelet Trees o Rank/Select dictionaries, que permiten reconstruir el texto original y realizar operaciones de búsqueda (como 'count' para el número de ocurrencias y 'locate' para sus posiciones) directamente sobre la representación comprimida. Su principal ventaja es su capacidad para operar en espacio de memoria cercano al tamaño del texto comprimido, en lugar del texto original.
El FM-index encuentra aplicación en sistemas que manejan grandes volúmenes de datos genómicos y textuales donde la eficiencia de memoria es crítica. Por ejemplo, es fundamental en herramientas de alineamiento de secuencias de ADN y ARN como Bowtie, BWA (Burrows-Wheeler Aligner) y HISAT2, que deben buscar rápidamente secuencias cortas (reads) en genomas de miles de millones de bases. También se utiliza en herramientas de compresión y búsqueda de texto, así como en bases de datos de series temporales o sistemas de log management que necesitan indexar y consultar grandes flujos de datos con restricciones de memoria.
Para un Arquitecto de Sistemas, el FM-index es una herramienta poderosa para diseñar soluciones que requieren búsquedas rápidas en grandes volúmenes de datos inmutables, especialmente cuando la memoria es un recurso limitado. Permite construir sistemas con una huella de memoria reducida para índices de texto completo, lo que se traduce en menores costos de infraestructura y mayor escalabilidad. El trade-off principal es la complejidad de su construcción y el tiempo de indexación, que puede ser considerable para textos muy grandes. Sin embargo, una vez construido, las consultas son extremadamente rápidas. Es ideal para escenarios donde el texto base cambia poco pero se consulta frecuentemente, como en bioinformática o archivos de logs históricos, donde la eficiencia de espacio y la velocidad de consulta superan el costo de construcción inicial.