Arbol De Huffman

Árbol de Huffman

Estructura de Datos

Estrutura de Datos 2009 - II - Renzo Loui Chavez Caycho - 08200088

2

Descripción del problema

n Tenemos un archivo de entrada.

n Asumiremos que el archivo está compuesto de bytes (enteros de 8 bits sin signo).

n El problema consiste en codificar(comprimir) el archivo de entrada utilizando el menor número posible de bits.

n Existe un algoritmo que resuelve el problema, y que es conocido como el algoritmo de Huffman.


3

Solución del problema

Se podría decir que la solución se obtiene aplicando cuatro fases:

1. Crear un vector de frecuencias de aparición de cada byte en el archivo de entrada.

2. Crear el árbol óptimo de codificación de Huffman a partir del vector de frecuencias.

3. Crear una tabla de codificación a partir del árbol de codificación.

4. La codificación propiamente dicha.


4

Vector de frecuencias

n Necesitamos conocer la frecuencia de aparición de cada byte en el archivo de entrada.

n Por tanto, tenemos que hacer una primera lectura del archivo de entrada.

n El objetivo es crear un vector de la forma:

5…53…0256

256255…9897…210-1

El índice es elvalor del byte

El contenido esla frecuencia

Si leemos un 255 …

6

Sumamos 1


5

Árbol óptimo de codificación (1)

n Se crea utilizando el algoritmo de Huffman.

n Este algoritmo se puede clasificar como algoritmo voraz.

n Las entradas del algoritmo son los bytes presentes en el archivo de entrada.

n Trabaja con un conjunto de árboles. Es decir, lo que se podría llamar un bosque.

n Nodo de un árbol de Huffman: índicepeso• Al enlace izquierdo se le asigna un valor 0

• Al enlace derecho se le asigna un valor 1

Es lo que se llama un trie binario (leido “trai”)0 1


6


n Los nodos hoja del árbol de Huffman serán los bytes leídos en el archivo de entrada. En ese caso:n índice = valor del byte (entre 0 y 255)n peso = frecuencia del byte

n A partir del vector de frecuencias construimos un bosque de árboles que sólo tienen un nodo. Cada nodo representará a un byte, con su índice (valor) y su peso (frecuencia).

n Un byte sólo está presente en este bosque inicial si aparece en el archivo de entrada con una frecuencia distinta de cero.


7


n Nuestro “bosque” inicial podría consistir, por ejemplo, en una lista de nodos.

índice = 97peso = 10




n Ahora debemos extraer los dos nodos con menor peso.

n Esto nos hace pensar que una lista no es la mejor opción posible, pero comentaremos esto más adelante.


8


n A partir de los dos nodos con menor peso extraídos se construye un nuevo nodo. Su peso será la suma de los pesos de sus hijos.

n El índice es indiferente por ahora. Sólo es importante para la construcción de la tabla de codificación. A partir de ahora tomará los valores 256, 257, 258, etc.






El nodo así creado se debeintroducir en el bosque pararealizar una nueva selección.


9


n El proceso es iterativo:








10


n Hasta que nos quedamos con un único nodo:








(Vacío)


11


n En la siguiente extracción, el bosque queda vacío y obtenemos el árbol de Huffman:








(Vacío)

¿Codificación de 97?

0

1

10 1

0

10


12


n Es posible que haya notado que son posibles varios árboles de codificación.

n Todos son óptimos en el sentido de que proporcionan una codificación con el menor número de bits.

n La mejor estructura para almacenar los nodos del bosque (conjunto de candidatos) es una cola de prioridad, donde la prioridades el peso del nodo.

n Esto nos permite extraer el mínimo de una manera eficaz.


13


n El estudio de Huffman nos dice que si el número de entradas es C, el número máximo de nodos del árbol de codificación es 2C – 1.

n Esto nos permite utilizar como cola de prioridad un montículo binario. Recordar que un montículo binario se implementa con un array.

n En nuestro caso C es, como máximo, igual a 256. El montículo binario puede tener un tamaño seguro de (2 * 256 – 1).


14

Tabla de codificación (1)

n La tabla de codificación es un paso intermedio entre el árbol de codificación y la verdadera codificación.

n Se construye para que la codificación sea más sencilla y rápida.

n Sin embargo, para construirla es necesario que cada nodo del árbol de Huffman pueda referenciar a su padre, y que almacene información sobre el tipo de hijo que es él mismo (0 ó 1).


15


n Un nodo de la tabla de codificación puede contener la información siguiente:

tipoHijoindicePadrepeso

n La tabla consiste en un array que sirve para indexar nodos de codificación.

n El tamaño de este array nos lo indica el índice del nodo raíz del árbol Huffman.


16


n Se crear el array para indexar.

n El árbol se recorre en preorden.

n Y así hasta recorrer todo el árbol …

257

256

255

72

32








0

1

10 1

0

-131

025711

02553

12558


17

Codificación

n La codificación a partir de la tabla de codificación es casi inmediata. Es necesaria una segunda lectura del archivo.

257

256

255

72

32

-131

025711

02553

12558

¿Codificación de 32?

1

0

fin

Por tanto, la codificación es …

0 1


18

Complejidad

n Estudiemos la complejidad del algoritmo que crea el árbol de Huffman, que es el que nos interesa por ser voraz.

n La extracción en una cola de prioridad tiene una complejidad O(logn).

n Por tanto, la complejidad de todo el algoritmo, que es iterativo, será O(n logn).


19

Algoritmo de Huffman (Pseudocódigo) (1)n {Precondición: C es el conjunto de caracteres

y f es el vector de frecuencias}.

n {Poscondición: z es el árbol de un código libre de prefijos óptimo para (C,f)}.

C

fz


20

Algoritmo de Huffman(Pseudocódigo) (2)Función Huffman(C:conjunto;f:vectFrec) devuelve árbol

//variables Q:colaPrioridades; i,fx,fy,fz: entero; z,x,y: árbolIniciocreaVacía(Q);para todox en C hacer

inserta(Q,<x,f[x]>)fpara;para i:=1 hasta|C|-1 hacer

<x,fx>:=primero(Q); borra(Q);<y,fy>:=primero(Q); borra(Q);fz:=fx+fy;z:=creaÁrbol(raíz=>fz,hijoIzq=>x;hijoDer=>y);inserta(Q,<z,fz>)

fpara;<z,fz>:=primero(Q); borra(Q)devuelve z

fin


21

Consideraciones finales

n Para conseguir la decodificación es necesario almacenar en el archivo codificado más información que los bits de los códigos.

n Evidentemente nos interesa que esa información ocupe el menor espacio posible.

n Enlace a la aplicación Aqui


22

Bibliografía

n Estructuras de datos en Java

Mark Allen Weiss

Editorial: Addison-Wesley

n Técnicas de Diseño de Algoritmos

Rosa Guerequeta y Antonio Vallecillo


23

Integrantes

n Renzo Loui Chávez Caycho 08200088

Arbol De Huffman

Documents

Transcript of Arbol De Huffman