La Transformación de Burrows-Wheeler (BWT) es un algoritmo de preprocesamiento de datos reversible que se utiliza principalmente en sistemas de compresión, como el conocido compresor bzip2. Su objetivo no es comprimir directamente, sino reorganizar la cadena de entrada de manera que las secuencias repetidas y los caracteres similares se agrupen, facilitando el trabajo de algoritmos posteriores.
Funcionamiento
El proceso de codificación de la BWT se lleva a cabo en cuatro pasos principales:
- Añadir el Carácter de Fin de Archivo (EOF): Se añade un carácter único (ej.
|o$) al final de la cadena. - Generar la Matriz de Rotaciones: Se crean todas las posibles rotaciones cíclicas de la cadena.
- Ordenar la Matriz: Se ordenan las filas lexicográficamente (alfabéticamente).
- Extraer la Columna Final (L): El resultado es la última columna de la matriz ordenada, junto con el índice de la fila original.
Ejemplo de Codificación
Tomemos la palabra BANANA y usemos | como EOF.
1. Cadena con EOF:
BANANA|
2. Matriz de Rotaciones:
BANANA|
ANANA|B
NANA|BA
ANA|BAB
NA|BANA
A|BANAN
|BANANA
3. Matriz Ordenada:
La fila original (BANANA|) se encuentra en la posición 3:
A|BANAN -- Final: B
ANA|BAB -- Final: N
ANANA|B -- Final: N
BANANA| -- Índice I=3; Final: |
|BANANA -- Final: A
NA|BANA -- Final: A
NANA|BA -- Final: A
4. Resultado BWT:
La última columna leída de arriba abajo es:
BNN|AAA
Para recuperar el original, se requiere el texto BNN|AAA y el índice I=3.