huffman.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION

  Calcula c\'odigos de Huffman. keywords: arbol binario

  FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: huffman.pas 2002/04/05 13:30 mstorti Exp jdelia   $ }
program huffman ;
uses u_arbbii, u_listpi, u_pilapi ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure INSERTA_ORD (         x: tipo_elemento;
                           bosque: Bosque_ArbBiI;
                       var      L: listpi);
var
   p  : posicion;
   px : tipo_etiqueta;
begin
   px := bosque.ETIQUETA (x);
   p := L.PRIMERO;
   while (p <> L.FIN) and
     (bosque.ETIQUETA (L.RECUPERA (p) ) <= px) do begin
     p := L.SIGUIENTE(p);
   end ; {while}
   L.INSERTA (x,p);
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
const
   MAX_CHAR = 100;
var
   arboles         : listpi;         {Lista de arboles }
   segundo, menor  : curs_nodo;      {cursores a nodos }
   m, n, p         : curs_nodo;      {cursores a nodos }
   bosque          : Bosque_ArbBiI ; {bosque de los arboles}
   k, nchar        : integer;
   psegundo, pmenor: integer;
   tabla : array [1..MAX_CHAR] of record
     c    : char;
     n    : curs_nodo;
     prob : real;
   end; {guarda las hojas para referencia }
   pl : pilapi; {necesaria para imprimir los codigos}
begin
   bosque.INICIALIZA_NODOS ;
   nchar := 4;  {numero de caracteres}
   arboles.ANULA ;
   for k := 1 to nchar do begin
     tabla [k].prob := RANDOM;  {probabilidades aleatorias}
     tabla [k].n    := bosque.
     {Crea arboles con cada caracter en la raiz
     las etiquetas del arbol contienen las
     probabilidades acumuladas en el subarbol.
     Para poder usar la estructura de arboles
     existente pone las probabilidades en forma
     entera (tomando TRUNC(10000*probabilidad))}
     CREA2 (TRUNC (tabla [k].prob*10000), Lambda, Lambda);
     tabla [k].c := chr ( ord ('A') + k - 1);
     writeln (tabla [k].c,':     prob: ',tabla [k].prob:10);
     INSERTA_ORD (tabla [k].n, bosque, arboles);
     {La lista se mantiene ordenada por probablidades}
   end ; {for}

   for k := 2 to nchar do begin
      {Como la lista esta ordenada los
      dos primeros son el menor y el segundo menor}
      menor := arboles.RECUPERA (arboles.PRIMERO);
      arboles.SUPRIME (arboles.PRIMERO);
      segundo := arboles.RECUPERA (arboles.PRIMERO);
      arboles.SUPRIME (arboles.PRIMERO);

      {Probabilidades correspondientes}
      pmenor := bosque.ETIQUETA (menor);
      psegundo := bosque.ETIQUETA (segundo);

      {Arma el nuevo arbol}
      n := bosque.CREA2 (pmenor + psegundo, menor, segundo);
      {lo inserta en la lista}
      INSERTA_ORD(n, bosque, arboles);
   end;

   {IMPRIME CODIGOS}
   writeln ('');
   writeln ('');
   writeln ('Codigos de Huffman:');
   writeln ('===================');
   for k := 1 to nchar do begin
      pl.ANULA;
      write (tabla[k].c,': ');
      m := tabla [k].n;
      {Sigue la cadena desde la hoja por el padre hasta
      la raiz. Lo pone en una pila para que al imprimirlo
      salga en el orden correcto}
      while (true) do begin
         p := bosque.PADRE (m);
         if (p = Lambda) then break;
         if m = bosque.HIJO_IZQ (p) then
            pl.METE (0)
         else begin
            pl.METE (1)
         end ; {if}
         m := p;
      end; {while}
      {Imprime el codigo de bits guardado en la pila}
      while not pl.VACIA do begin
         write (pl.TOPE);
         pl.SACA;
      end ; {while}
      writeln ('');
   end; {for}
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}