Transformada de Burrows-Wheeler (BWT)

observa cómo las rotaciones cíclicas se ordenan en una matriz cuya última columna agrupa caracteres repetidos, y luego revierte el proceso sin pérdidas

Valores iniciales — Transformada de Burrows-Wheeler (BWT)

Texto de entrada	banana

Cambia cualquier control de arriba y los resultados se recalculan.

Cargando simulación interactiva...

por qué ordenar rotaciones crea rachas 🖖

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.

La BWT reordena, no reduce 🖖

Por sí sola, la BWT no reduce el tamaño del texto: el resultado tiene exactamente la misma longitud y los mismos caracteres, solo que en otro orden. Su verdadera función es servir de paso previo reversible y agrupar los caracteres idénticos para facilitar el trabajo de los compresores posteriores: transformación move-to-front, codificación por longitud de rachas y, finalmente, codificación de Huffman o aritmética. Con "abracadabra$", el resultado contiene los mismos doce caracteres, pero reúne cuatro aes seguidas donde la entrada no tenía ni dos adyacentes.

El mismo truco que mapea tu ADN 🖖

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.

Problema resuelto al detalle

La transformada de Burrows–Wheeler de "banana$" con las siete rotaciones ordenadas 5 pasos
Halle la transformada de Burrows-Wheeler de "banana$" y decida a continuación si se ha comprimido algo. Este es el paso de Salida BWT: centinela añadido, las siete rotaciones ordenadas y lectura de la última columna.
1. El centinela se añade antes de que ocurra cualquier otra cosa. Como $ se ordena antes que cualquier letra y aparece exactamente una vez, no hay dos rotaciones que puedan resultar iguales al compararse, por lo que la ordenación tiene una única respuesta no ambigua.
  
  $s = banana$ (n = 7), r_{k} = s [k :] + s [: k], k = 0, \dots, 6$
2. Ordenar lexicográficamente las rotaciones es el único trabajo que realiza la transformada. Al leer hacia abajo las siete filas, obsérvese que la ordenación ha agrupado la cadena según lo que viene después de cada posición.
  
  $$banana, a$banan, ana$ban, anana$b, banana$, na$bana, nana$ba$
3. El último carácter de una rotación es el carácter situado inmediatamente antes de su primer carácter en la cadena original. Por eso la ordenación produce rachas: las filas 1 y 2 empiezan por 'a' y terminan en 'n', porque a ambas 'a' les precede una 'n' en banana. La clave es el número de fila de la cadena original, y sin ella la transformada no se puede deshacer.
  
  $L_{j} = s_{(k_{j} - 1) mod n} ⟹ L = annb$aa, key = 4$
4. Todavía no se ha comprimido nada, ni se podría haber comprimido: la salida es una permutación de la entrada, los mismos siete caracteres en un orden diferente. Lo que ha cambiado es la estructura de rachas, y eso es lo único que ha cambiado.
  
  $b ∣ a ∣ n ∣ a ∣ n ∣ a ∣ $ : R = 7, \overset{r}{ˉ} = 1.00 ⟶ a ∣ nn ∣ b ∣ $ ∣ aa : R = 5, \overset{r}{ˉ} = \frac{7}{5} = 1.4$
5. RLE cobra dos bytes por racha, por lo que cinco rachas cuestan diez bytes frente a una entrada de siete bytes. Su punto de equilibrio nunca cambia: el número de rachas tiene que ser inferior a la mitad de la longitud, lo que aquí significa tres o menos.
  
  $2 R = 10 > N = 7 ⟹ \frac{7}{10} = 0.70 \times, 2 R < N ⟺ R < 3.5$
Respuesta

El panel muestra annb$aa con key = 4, una racha media de 1,4 caracteres, 10 bytes de RLE y una puntuación de 0,70×. La transformada hizo exactamente lo que promete: aumentó la racha media un 40 % sin tocar un solo carácter, y aun así la cadena de procesamiento perdió, porque siete caracteres no es suficiente texto para que esa ganancia cubra dos bytes por racha. Duplíquese la palabra y la aritmética se invierte. "bananabanana$" tiene trece caracteres y su transformada es annnnbba$aaaa: seis rachas en lugar de cinco, mientras que la longitud casi se duplicó, lo que da 12 bytes frente a 13 y una puntuación de 1,08×. Ese es todo el argumento a favor de la BWT: el recuento de rachas se rige por cuántos contextos distintos tiene el texto, no por su longitud, de modo que cuanto más largo es el bloque, mejor rinde, motivo por el cual bzip2 transforma bloques de hasta 900 kB en lugar de palabras.

$bananabanana$ : N = 13, R = 6 ⟹ 2 R = 12 < 13, \frac{13}{12} = 1.08 \times$

Ruta de aprendizaje

Compresión a mano

Referencias (3)

Insight blocks 1 and 2 — the transform itself: M. Burrows and D. J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm." Digital Systems Research Center, Research Report 124, 1994.
Insight block 3 — the aligners it turned into: B. Langmead, C. Trapnell, M. Pop and S. L. Salzberg, "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome." Genome Biology 10, R25, 2009.
And the one the block names outright: H. Li and R. Durbin, "Fast and accurate short read alignment with Burrows–Wheeler transform." Bioinformatics 25(14), 1754–1760, 2009.

Por el equipo de 42Math · Actualizado 2026-08-17

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo

banana - "banana$" se transforma en "annb$aa": las tres aes que nunca estaban juntas quedan ahora en dos grupos, y el número de rachas baja de 7 a 5.
mississippi - "mississippi$" se transforma en "ipssm$pissii": es el ejemplo clásico de los libros de texto y, con esta longitud, el número de rachas se mantiene en 9. La BWT necesita textos más largos para que el agrupamiento resulte ventajoso.
abracadabra - "abracadabra$" se transforma en "ard$rcaaaabb": aparecen cuatro aes seguidas donde en el original no había ni dos adyacentes, y las rachas bajan de 12 a 8. Es el mejor agrupamiento de los cuatro ejemplos predefinidos.
secuencia de ADN - "AGATCAGA$" se transforma en "AGC$GTAAA": tres aes quedan juntas, aunque en la cadena original ninguna era adyacente a otra. En un genoma, esto es lo que indexa un índice FM.