Julian Esteban Zapata Osorio
Universidad de Antioquia
Ingeniera de Telecomunicaciones
2014-1
Julian Zapata Codificacin BWT
Historia
Los autores de la BWT, adems de presentar su
transformacin, dan una idea de cmo es posible
comprimir eficientemente la secuencia transformada.
Su propuesta consiste en aplicar lo que se conoce con
el nombre de codificacin mover al frente (move to
front) o MTF. Esta recodificacin de los smbolos no
expande ni comprime la secuencia, sino que de nuevo
la transforma, para que sea fcilmente comprimida por
un compresor entrpico.
Julian Zapata Codificacin BWT
BWT
La BWT no es una tcnica de compresin sino slo una
forma de transformar un determinado mensaje de
entrada en una representacin equivalente con
mejores propiedades para su compresin. La BWT es
un algoritmo reversible que se ejecuta sobre un
mensaje M= m1 m2 ...mn y cuyo resultado es un nuevo
mensaje M con el mismo contenido que M pero
expresado en un orden diferente. La transformada
inversa de Burrows Wheeler es capaz de recuperar M a
partir de M y un pequeo conjunto de informacin
extra.
Julian Zapata Codificacin BWT
Algoritmo
Julian Zapata Codificacin BWT
El algoritmo BWT toma un bloque de datos y lo ordena
usando un algoritmo de ordenacin. El bloque de
salida resultante contiene exactamente los mismos
elementos de datos con los que empez, difiriendo
slo en el ordenamiento. La transformacin es
reversible, o sea, la ordenacin original puede ser
restablecida sin prdida de fidelidad.
Ejemplo
Julian Zapata Codificacin BWT
Ejemplo
Para poder representar las cadenas de manera
eficiente, no debemos crear cada cadena en memoria,
sino que simplemente debemos almacenar la cadena
inicial en un bfer y luego el ndice de inicio de cada
cadena. Luego, ordenamos las cadenas utilizando una
comparacin lexicogrfica.
Julian Zapata Codificacin BWT
Ejemplo
Despus de reorganizar nos queda algo como lo
siguiente:
Julian Zapata Codificacin BWT
Ejemplo
Hemos marcado las columnas Inicio (I) y Final (F) ya
que son importantes por el siguiente motivo: los
caracteres en F son los caracteres prefijos de los
caracteres en I en las mismas filas. O sea, en C1, w es
el prefijo de h.
La salida de BWT consiste en dos cadenas: una copia
de la columna L y un ndice primario, un entero que
indica la fila en la cual se encuentra la primera letra del
bfer original, o sea, la posicin de la cadena 1. En este
caso, la primera cadena es helwerr y la segunda el
ndice 3.
Julian Zapata Codificacin BWT
Recomposicin
Lo ms interesante sobre la BWT no es que genere una
salida ms fcil de codificaruna ordenacin
ordinaria podra hacerlo igualmentesino que es un
proceso reversible, permitiendo re-generar el
documento original a partir de la ltima columna de
datos.
Julian Zapata Codificacin BWT
Recomposicin
Como ya hemos mencionado, al tener el vector I y F,
podemos saber todos los pares de letras encontrados
en C0. Para poder recomponer C0, primero nos
situamos en la fila indicada por el ndice primario. El
vector F en esta fila contiene la primera letra de C0, ya
que apunta a C1, el cual es C0 rotado una letra a la
izquierda. La siguiente letra est en I en la misma fila.
Para saber la siguiente letra, buscamos en F la fila en la
cual la letra en I aparece. Una vez encontrada la fila, la
letra en I en ella es el la siguiente letra. Repetimos el
proceso hasta finalizar la construccin de C0.
Julian Zapata Codificacin BWT
Recomposicin.
Julian Zapata Codificacin BWT
En el caso de que hayan letras repetidas, , la primera
letra repetida en I corresponde a la primera letra en F,
la segunda en I a la segunda en F, y as sucesivamente.
Por lo que la reconstruccin queda de la siguiente
manera.
Recomposicin.
Los pares tomados, iniciado por el ndice primario 3,
son los siguientes: wh, he, ee, el, le, er, formando la
palabra wheeler, o sea C0.
Julian Zapata Codificacin BWT
Compresin
Podemos tomar la salida de BWT y simplemente aplicar un compresor
convencional al mismo, pero Burrows y Wheeler sugieren un mejor
acercamiento. Ellos recomiendan utilizar un esquema de Mover al
Frente, seguido por un codificador entrpico.
Un codificador MAF es una pieza de trabajo relativamente trivial.
Simplemente mantiene en memoria todos los 256 cdigos posibles en
una lista. Cada vez que un carcter debe ser emitido, se enva su
posicin en la lista y luego se lo mueve al frente de la misma. Por
ejemplo, la cadena tttWtwttt, tiene una salida de enteros { 116, 0, 0,
88, 1, 119, 1, 0, 0 }.
Si la salida de la operacin BWT contiene una gran porcin de
caracteres repetidos, podemos esperar que aplicando el codificador
MTF nos dar un archivo lleno de muchos ceros, y muchos enteros
pequeos. En este punto, el archivo puede finalmente ser comprimido
por un codificador entrpico, tpicamente un codificador Huffman o un
codificador aritmtico.
Julian Zapata Codificacin BWT
Referencias
Algoritmos de Compresin Sin Prdida de Datos-
Roberto Gimnez- Universidad Catlica Nuestra
Seora de la Asuncin.
Estudio y Aplicacin de Nuevos Mtodos Compresin
de Texto Orientada a Palabras.- Tesis Doctoral- Miguel
ngel Martnez Prieto- Universidad de Valladolid.
Julian Zapata Codificacin BWT
