Transformada de Burrows-Wheeler (BWT)

Al ordenar todas las rotaciones cíclicas de un texto, cada rotación que comparte el mismo sufijo termina adyacente a las demás. La última columna — el carácter justo antes de cada prefijo ordenado — reúne los caracteres que precedían al mismo contexto en el texto original. Los patrones repetidos hacen que muchas rotaciones compartan un sufijo común, así que el mismo carácter precedente aparece muchas veces seguidas en la última columna. Esas rachas son lo que explotan la RLE y la codificación move-to-front. La transformación es sin pérdidas porque la primera columna F (BWT ordenada) y la última columna L (la BWT en sí) codifican juntas un mapa completo — el LF-mapping — que permite reconstruir el original carácter por carácter solo con estas dos columnas y la clave.

Por sí sola, la BWT no hace el texto más pequeño: la salida tiene exactamente la misma longitud y los mismos caracteres, solo en otro orden. Su verdadera función es ser un paso de preparación reversible que agrupa caracteres idénticos para que los compresores que vienen después — move-to-front, codificación por longitud de series y luego Huffman o codificación aritmética — lo tengan fácil. La conclusión: la ventaja no está en el tamaño de la salida de la BWT, sino en lo mucho más comprimible que se vuelve.

Una idea de compresión se convirtió discretamente en pilar de la genómica. Envuelta en una estructura llamada índice FM, la BWT permite buscar un fragmento corto de ADN dentro de un genoma humano de 3000 millones de letras almacenando ese genoma en apenas un par de gigabytes. Alineadores como Bowtie y BWA — el Burrows-Wheeler Aligner — se basan en ella, así que un truco de compresión de 1994 sostiene hoy el emparejamiento diario de millones de lecturas de secuenciación.