Tabla de contenido:
- Definición - ¿Qué significa la transformación de Burrows-Wheeler (BWT)?
- Techopedia explica la transformación de Burrows-Wheeler (BWT)
Definición - ¿Qué significa la transformación de Burrows-Wheeler (BWT)?
La transformación Burrows-Wheeler (BWT) es un algoritmo que toma bloques de datos, como cadenas, y los reorganiza en series de caracteres similares. Después de la transformación, el bloque de salida contiene los mismos elementos de datos exactos antes de comenzar, pero difiere en el orden. La naturaleza del algoritmo tiende a poner caracteres similares uno al lado del otro, lo que hace que el orden de datos resultante sea más fácil de comprimir. Por lo tanto, se usa en muchos algoritmos de compresión.
Techopedia explica la transformación de Burrows-Wheeler (BWT)
El algoritmo de transformación 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 "Un algoritmo de compresión de datos sin pérdida de clasificación de bloques".
En lo 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. El siguiente pseudocódigo o pasos ilustran el algoritmo:
- Cree una tabla que contenga filas que representen todas las rotaciones posibles de un incremento de la cadena.
- Ordenar todas las filas alfabéticamente.
- Salida de 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 $ bana
un $ banan
$ banana
2. Ordene las filas alfabéticamente / lexicográficamente según la primera columna:
$ banana
un $ banan
ana $ ban
anana $ b
banana $
nana $ ba
na $ bana
3. Devuelva la última columna como salida BWT: annb $ aa
La cadena resultante es más fácil de comprimir porque los caracteres repetidos se agrupan uno al lado del otro. Pero debe haber datos adicionales almacenados con los datos transformados para que se pueda realizar una transformación inversa. A pesar de que los datos transformados resultantes son más grandes que su forma original, pero su característica de compresibilidad aumenta muchas veces, esencialmente haciéndolo un método "libre" para mejorar la eficiencia de los métodos de compresión.
