LABORATORIO DE ESTRUCTURAS DE DATOS PRÁCTICAS CURSO 1996-97 1º INGENIERÍA INFORMÁTICA

PRÁCTICA Nº 8: dos sesiones

(Semanas del 26 de Mayo al 6 de Junio de 1997)

CÓDIGOS DE HUFFMAN

OBJETIVO

• Manipulación de árboles mediante representaciones enlazadas.
• Integración de distintas tareas y estructuras en un mismo programa.

PLANTEAMIENTO DEL PROBLEMA

Supóngase que se tienen mensajes formados por secuencias de caracteres (un texto cualquiera tendría esta forma). En cada mensaje, los caracteres son independientes entre sí y aparecen con una determinada probabilidad conocida a priori. Se desea codificar cada carácter mediante una secuencia de ceros y unos, de manera que ningún código de un carácter sea prefijo del código de otro carácter, esta propiedad de prefijos evitará cualquier tipo de ambigüedad en el proceso de decodificación del mensaje.

El problema de codificación que se plantea sería: dado un conjunto de caracteres, en nuestro caso supongamos que todo el código ASCII (256 valores), y sus probabilidades de aparición en un texto (este dato no es conocido a priori y tendremos que hacer un estudio previo), encontrar un código para esos caracteres que cumpla la propiedad de prefijos y tal que la longitud media del código de un carácter sea mínima. La razón por la que se desea minimizar la longitud media de un código es que ello permitirá comprimir la longitud del mensaje codificado.

El algoritmo de Huffman permite encontrar un código con las propiedades especificadas. La idea del algoritmo consiste en llegar a formar un árbol binario que represente el código. En los nodos terminales (hojas) de este árbol se almacenarán los caracteres que se desea codificar junto con la probabilidad de aparición de cada uno de ellos, cumpliéndose que los caracteres más probables están más próximos a la raíz que los menos probables. De manera que el camino desde la raíz del árbol a cualquier hoja del mismo representará el código para el carácter de esa hoja, de acuerdo con el criterio de que los subárboles izquierdos se etiquetan con un 0 y los subárboles derechos lo hacen con un 1. Según este criterio, los caracteres con mayor probabilidad de aparición tendrán los códigos de menor longitud, mientras que los que tengan una probabilidad de aparición menor tendrán asociado un código de mayor longitud.

El algoritmo de Huffman consiste en lo siguiente:

Suponiendo conocida la probabilidad de aparición de un carácter en un texto (sea p_i) hacer:

1. Crear un bosque formado por tantos árboles independientes como caracteres se vayan a codificar. Cada carácter será la raíz de un árbol independiente, almacenándose junto a él su probabilidad de aparición.

2. Buscar en el bosque los dos árboles que presenten las menores probabilidades de aparición.

3. Agrupar los dos árboles encontrados en el paso 2) en un solo árbol que tenga como subárbol izquierdo el árbol que tenía menor valor p_i asociado y como subárbol derecho el otro árbol. En la raíz de este nuevo árbol no se almacena ningún carácter pero sí la probabilidad de aparición de los caracteres agrupados, que será la suma de sus dos probabilidades de aparición (p_i + p_j).

4. Repetir desde el paso 2) hasta que en el bosque sólo quede un árbol que agrupe a todos los caracteres.

REALIZACIÓN DE LA PRÁCTICA

• Codificación

• Tarea 1: Encontrar las probabilidades de aparición de los caracteres del código ASCII (ordinales desde 0 a 255) en el fichero de texto que se desea codificar.

  Para este proceso se incluirá en el programa un rutina que calcule el número de veces que aparece cada carácter en el fichero texto. Será necesario definir una tabla que almacene la frecuencia de aparición de cada carácter.

• Tarea 2: Generar el código de Huffman a partir de la tabla de frecuencias.

  Esta tarea se realizará después de la tarea 1 y su esquema será:

  1. ) Generar el árbol de Huffman según el algoritmo dado anteriormente, utilizando la tabla de la tarea 1 y sin considerar aquellos caracteres que no aparecen ninguna vez.
  2. ) Recorrer el árbol para guardar, en forma de matriz, el código que representa cada carácter, de manera que sea fácil consultarlo usando los caracteres como índices.
• Tarea 3: Codificar un fichero texto según el código generado en la tarea 2.

  En esta tarea, a partir del fichero texto original, se obtendrá un fichero "binario" (sólo ceros y unos, como caracteres (1 byte), no como bits) que haga corresponder a cada carácter del fichero original el código de Huffman correspondiente.

  La rutina correspondiente a esta tarea responderá al siguiente esquema:

  1. ) Almacenar el árbol de códigos como cabecera del fichero binario. Se utilizará para ello una ligera variación de la notación empleada en otros casos: Se recorre en orden prefijo el árbol, escribiendo en el archivo la siguiente información:
     • Si el nodo contiene un carácter, se guarda el carácter seguido de un espacio en blanco.
     • Si el nodo NO contiene un carácter, se guardan dos "sostenidos" ("##").
     • Si el puntero es NIL se guardan dos '.' (".."). (Este punto puede obviarse teniendo en cuenta que todos los nodos terminales u hojas van a ser nodos que almacenen un caracter o simbolo)
  2. ) Para cada carácter del fichero original hacer:
     • 2.1) Buscar en la matriz la cadena de 0 y 1 que tiene asociada.
     • 2.2) Almacenar en el fichero binario la secuencia de ceros y unos determina en el paso anterior.
  En ningún caso se realizarán saltos de línea, ya que no tienen sentido en este problema.

  En esta fase habrá que estimar cuanto ocuparía el fichero binario si cada `0' y `1' escrito en él fuese un bit, en vez de un carácter. ¿Se conseguiría comprimir el fichero original? ¿Y si consideramos lo que ocupa la cabecera con el árbol de códigos?

  Es conveniente, una vez realizada la codificación, liberar el espacio reservado para el árbol, ya que no vamos a utilizarlo más en el programa.

   CONST
      Primero = 0;
      Ultimo = 255;
{Estas dos constantes definen el rango del código ASCII que se
va a considerar. Si las rutinas las escribimos con referencia a estas
constantes, el programa se podrá adaptar fácilmente a otro
conjunto de caracteres sin más que modificar estos
valores}

   TYPE
      Posicion = Primero..Ultimo; {Establece el rango de caracteres válidos}

{Definición de la tabla de frecuencias de aparición de caracteres}
      Frecuencia = 0..MaxInt; {Para indicar el n1 de veces que aparece un carácter}
      Tabla_Frec = array [ Posicion ] of Frecuencia;

{Definición de la matriz que almacenará el código generado por el método de Huffman}
      Tabla_Codigos = array [ Posicion ] of String; { Las cadenas contendrán solo '0's o '1's }

{Definición del tipo árbol}
{Un nodo del árbol constará de la siguiente información:
      Frec    : Indica la frecuencia de aparición de los caracteres
                que forman el árbol del cual el nodo es raíz.
      simbolo : Indica si el nodo almacena un carácter o
                está formado por la agrupación de caracteres. Sólo los
                nodos terminales tendrán este campo puesto a true. En ese caso, se
                define un campo más, info que almacena el carácter.
}

      Valor = Record
                 Frec : Frecuencia;
                 case simbolo : boolean of
                                   true: (info: char);
                                   false: ();
               end;

      Arbol = ^Nodo;

      Nodo = Record
                Dato : Valor;
                Sub_Izq, Sub_Der : Arbol;
             end;

{Un bosque será una agrupación de árboles,
tantos como posibles caracteres tengamos}
      Bosque = array [ Posicion ] of Arbol;

{Tipos fichero que se utilizarán para manipular archivos de
disco}
      Ficheros = file of char;
{No se utiliza text porque sólo interesan los caracteres
individualmente, se usarán tanto para los ficheros codificados como para
los de texto}