Definición: ¿Qué significa la Transformada de Burrows-Wheeler (BWT)?
La transformación de Burrows-Wheeler (BWT) es un algoritmo que toma bloques de datos, como cadenas, y los reorganiza en ejecuciones de caracteres similares. Después de la transformación, el bloque de salida contiene exactamente los mismos elementos de datos antes de que comenzara, pero difiere en el orden. La naturaleza del algoritmo tiende a colocar caracteres similares uno al lado del otro, lo que facilita la compresión del orden de datos resultante. Por tanto, se utiliza en muchos algoritmos de compresión.
Techinfo explica la Transformada de Burrows-Wheeler (BWT)
El algoritmo de transformación de Burrows-Wheeler es un algoritmo relativamente nuevo inventado en 1994 por Michael Burrows y David Wheeler y basado en una transformación inédita descubierta por Wheeler en 1983, publicada en su artículo "A Block-sorting Lossless Data Compression Algorithm".
En el más básico, BWT toma un bloque de datos como una cadena, agrega un carácter EOF y luego ordena todas las rotaciones de esa cadena en orden lexicográfico. Los siguientes pseudocódigo o pasos ilustran el algoritmo:
- Cree una tabla que contenga filas que representen todas las posibles rotaciones de un incremento de la cadena.
- Ordene todas las filas alfabéticamente.
- Imprima la última columna de la tabla.
Por ejemplo: la palabra "banana"; agregar un carácter EOF lo convierte en "banana $" y luego aplicamos el algoritmo:
1. Cree una tabla con filas que representen todas las rotaciones posibles:
banana $
anana $ b
nana $ ba
ana $ ban
na $ yo
un $ banana
$ banana
2. Ordene las filas alfabéticamente / lexicográficamente según la primera columna:
$ banana
un $ banana
ana $ ban
anana $ b
banana $
nana $ ba
na $ yo
3.Vuelva la última columna como salida BWT: annb $ aa
La cadena resultante es más fácil de comprimir porque los caracteres repetidos están agrupados uno al lado del otro. Pero es necesario que haya datos adicionales almacenados con los datos transformados para que se pueda realizar una transformación inversa. Aunque los datos transformados resultantes son más grandes que su forma original, su característica de compresibilidad aumenta muchas veces, lo que esencialmente lo convierte en un método "gratuito" para mejorar la eficiencia de los métodos de compresión.