> bwt | transformar | comprimir <
// Burrows-Wheeler Transform - transformación reversible de texto para mejorar la compresión
>> características
Totalmente reversible
Transformación sin pérdidas que puede invertirse de forma exacta.
Agrupación de caracteres
Agrupa caracteres similares para que los codificadores posteriores compriman mejor.
Núcleo de bzip2
Base de muchos algoritmos de compresión de estilo bzip2.
>> información técnica
Cómo funciona BWT
La transformada de Burrows-Wheeler genera todas las rotaciones cíclicas de la cadena de entrada, ordena esas filas lexicográficamente y toma la última columna de la matriz ordenada junto con el índice de la cadena original. El resultado tiende a agrupar caracteres similares, lo que facilita una compresión eficaz mediante RLE, Move-to-Front u otros codificadores.
Ejemplo de BWT
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
Por qué usar BWT
- Mejora la compresibilidad de los datos
- Es totalmente reversible
- Agrupa contextos similares
- Fundamento de bzip2
- Preprocesamiento eficaz para otros codificadores
>> preguntas frecuentes
¿Qué es la transformada de Burrows-Wheeler?
La transformada de Burrows-Wheeler (BWT) es un algoritmo reversible que reordena una cadena de caracteres para producir secuencias con muchos símbolos repetidos. Fue propuesta por Michael Burrows y David Wheeler en 1994 y se usa como paso de preprocesamiento en compresores como bzip2 para obtener mejores ratios de compresión.
¿Por qué BWT mejora la compresión?
BWT agrupa caracteres que aparecen en contextos similares, de modo que en el resultado muchas apariciones de un mismo símbolo quedan juntas. Esas rachas de caracteres se comprimen muy bien con codificación por longitudes de corrida, transformada Move-to-Front o codificadores entrópicos como Huffman o arithmetic coding.
¿Qué es el marcador EOF?
El marcador EOF (fin de archivo), normalmente el símbolo '$' u otro carácter único, garantiza que todas las rotaciones sean distintas y permite recuperar la posición de la cadena original. Sin este marcador algunas cadenas no tendrían una representación única. Durante la transformación inversa, el marcador se elimina.
¿BWT comprime por sí misma?
No. BWT no es un algoritmo de compresión completo, sino una transformación que hace que los datos sean más fáciles de comprimir. Suele combinarse con Move-to-Front, RLE y codificación de Huffman en esquemas como bzip2.