Out-of-series #1 – Algoritmo de Huffman

Padrão

Fugindo um pouco do padrão de posts que estou tendo aqui no blog, resolvi compartilhar duas implementações bastante interessantes que fiz no ano passado para a disciplina de Fundamentos Matemáticos da Computação. Sobre o algoritmo de Huffman, segue uma breve explanação, feita pelo prof Edson J. C. Gimenez:

“O código de Huffman é um código de fonte cujo comprimento médio das palavras códigos aproxima-se do limite fundamental, dado pela entropia da fonte, de forma a nenhum outro código ter um comprimento médio menor. Por isso, o código de Huffman é denominado ótima para uma fonte discreta sem memória.

Algoritmo de codificação:

1. Liste em ordem decrescente de probabilidade os símbolos da fonte, atribuindo as duas menores probabilidades os bits 0 e 1.

2. Some as duas menores probabilidades da lista, gerando uma nova probabilidade.

3. Repita os passos anteriores, até que tenhamos apenas duas únicas probabilidades na lista.

4. A palavra código correspondente a cada símbolo é determinada pela sequência de bits correspondentes ao caminho do último estágio de codificação até cada símbolo específico.”

Segue, então a implementação feita por mim, utilizando a linguagem C. Fiz utilizando o MingW, no ambiente Windows, mas ele pode ser facilmente adaptado para outras plataformas.

//////////////////////////////////////////////////////////////////////////////<br />
//                                                                          //<br />
//  IMPLEMENTAÇÃO DO ALGORITMO DE HUFFMAN                                   //<br />
//  AUTOR: Rafael D. Toledo (rafaeldtoledo@gmail.com)                       //<br />
//  WEB: www.rafaeltoledo.net                                               //<br />
//                                                                          //<br />
//////////////////////////////////////////////////////////////////////////////</p>
<p>#include &lt;stdio.h&gt;<br />
#include &lt;stdlib.h&gt;<br />
#include &lt;conio.h&gt;<br />
#include &lt;windows.h&gt;</p>
<p>//----------------------------------------------------------------------------</p>
<p>typedef struct SIMBOLO *TSimbolo;<br />
typedef struct CODIGO  *TCodigo;</p>
<p>struct SIMBOLO<br />
{<br />
   int      simbolo;<br />
   float    probabilidade;<br />
   TSimbolo rlink;<br />
   TSimbolo llink;<br />
   TSimbolo mother;<br />
   TSimbolo lista;<br />
};</p>
<p>struct CODIGO<br />
{<br />
   TSimbolo endereco;<br />
   int      simbolo;<br />
   float    probabilidade;<br />
   char     codigo[20];<br />
   TCodigo  link;<br />
};</p>
<p>//----------------------------------------------------------------------------</p>
<p>void     huffman(void);<br />
TSimbolo inserir_simbolo(TSimbolo, int, float);<br />
void     listar_lista(TSimbolo);<br />
int      contar_lista(TSimbolo);<br />
TSimbolo agrupar_ultimos(TSimbolo);<br />
TSimbolo ordenar_lista(TSimbolo, TSimbolo);<br />
TSimbolo agrupar_ultimos2(TSimbolo);<br />
TCodigo  armazenar_simbolos(TSimbolo);<br />
void     gerar_simbolos(TCodigo);<br />
void     exibir_resultado(TCodigo);<br />
void     inverter_codigos(TCodigo);<br />
void     inverter_string(char*);<br />
void     ordenar_codigos(TCodigo);</p>
<p>//----------------------------------------------------------------------------</p>
<p>int main(void)<br />
{<br />
   int opcao;</p>
<p>   do<br />
   {<br />
      system(&quot;cls&quot;);<br />
      printf(&quot;\tIMPLEMENTACAO DO ALGORITMO DE HUFFMAN\n\n&quot;);<br />
      printf(&quot; 1. Inserir Probabilidades dos Simbolos\n&quot;);<br />
      printf(&quot; 2. Encerrar Aplicativo\n\n&quot;);<br />
      printf(&quot; Opcao: &quot;);<br />
      scanf(&quot;%d&quot;, &amp;opcao);</p>
<p>      switch(opcao)<br />
      {<br />
         case 1 : huffman();<br />
                  break;<br />
         case 2 : printf(&quot;\n Aplicativo finalizado com sucesso. . .&quot;);<br />
                  Sleep(2000);<br />
                  break;<br />
         default: printf(&quot;\n Opcao invalida. . .&quot;);<br />
                  Sleep(2000);<br />
      }<br />
   }while(opcao != 2);</p>
<p>   return 0;<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void huffman(void)<br />
{<br />
   TSimbolo arvore = NULL; // Originalmente uma lista, depois uma árvore<br />
   TSimbolo ultimo;<br />
   TCodigo  codigos = NULL; // Irá armazenar o resultado final<br />
   float prob_total = 0.0, prob;<br />
   int   contador = 0;</p>
<p>   system(&quot;cls&quot;);<br />
   printf(&quot;\tIMPLEMENTACAO DO ALGORITMO DE HUFFMAN\n\n&quot;);</p>
<p>   do<br />
   {<br />
      printf(&quot; Probabilidade de S%d: &quot;, contador);<br />
      scanf(&quot;%f&quot;, &amp;prob);<br />
      arvore = inserir_simbolo(arvore, contador, prob);<br />
      contador++;<br />
      prob_total += prob;<br />
   }while(prob_total &lt; 1.0);</p>
<p>   codigos = armazenar_simbolos(arvore);</p>
<p>   while(contar_lista(arvore) &gt; 2)<br />
   {<br />
      ultimo = agrupar_ultimos(arvore);<br />
      arvore = ordenar_lista(arvore, ultimo);<br />
   }</p>
<p>   arvore = agrupar_ultimos2(arvore);<br />
   gerar_simbolos(codigos);<br />
   inverter_codigos(codigos);<br />
   ordenar_codigos(codigos);<br />
   exibir_resultado(codigos);<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>TSimbolo inserir_simbolo(TSimbolo lista, int simbolo, float probabilidade)<br />
{<br />
   TSimbolo novo = (TSimbolo) malloc(sizeof(struct SIMBOLO));<br />
   novo-&gt;simbolo = simbolo;<br />
   novo-&gt;probabilidade = probabilidade;<br />
   novo-&gt;rlink = NULL;<br />
   novo-&gt;llink = NULL;<br />
   novo-&gt;mother = NULL;</p>
<p>   if(lista == NULL)<br />
   {<br />
      lista = novo;<br />
      novo-&gt;lista = NULL;<br />
   }<br />
   else<br />
   {<br />
      if(lista-&gt;probabilidade &lt; novo-&gt;probabilidade)<br />
      {<br />
         novo-&gt;lista = lista;<br />
         lista = novo;<br />
      }<br />
      else<br />
      {<br />
         TSimbolo aux1 = lista, aux2 = lista-&gt;lista;<br />
         int      alocado = 0;<br />
         while(aux2 != NULL)<br />
         {<br />
            if(aux2-&gt;probabilidade &lt; novo-&gt;probabilidade)<br />
            {<br />
               novo-&gt;lista = aux2;<br />
               aux1-&gt;lista = novo;<br />
               alocado = 1;<br />
               break;<br />
            }<br />
            aux1 = aux2;<br />
            aux2 = aux2-&gt;lista;<br />
         }</p>
<p>         if(!alocado)<br />
         {<br />
            aux1-&gt;lista = novo;<br />
            novo-&gt;lista = NULL;<br />
         }<br />
      }<br />
   }</p>
<p>   return lista;<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void listar_lista(TSimbolo lista)<br />
{<br />
   while(lista != NULL)<br />
   {<br />
      printf(&quot;\n S%d: %.2f&quot;, lista-&gt;simbolo, lista-&gt;probabilidade);<br />
      lista = lista-&gt;lista;<br />
   }</p>
<p>   getch();<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>int contar_lista(TSimbolo lista)<br />
{<br />
   int contador = 0;</p>
<p>   while(lista != NULL)<br />
   {<br />
      contador++;<br />
      lista = lista-&gt;lista;<br />
   }</p>
<p>   return contador;<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>TSimbolo agrupar_ultimos(TSimbolo lista)<br />
{<br />
   TSimbolo agrup = (TSimbolo) malloc(sizeof(struct SIMBOLO));</p>
<p>   while(lista-&gt;lista-&gt;lista-&gt;lista != NULL)<br />
      lista = lista-&gt;lista;</p>
<p>   agrup-&gt;simbolo = -1;<br />
   agrup-&gt;probabilidade = lista-&gt;lista-&gt;probabilidade + lista-&gt;lista-&gt;lista-&gt;probabilidade;<br />
   agrup-&gt;lista = NULL;<br />
   agrup-&gt;rlink = lista-&gt;lista-&gt;lista;<br />
   agrup-&gt;llink = lista-&gt;lista;<br />
   lista-&gt;lista-&gt;lista-&gt;mother = agrup;<br />
   lista-&gt;lista-&gt;mother = agrup;<br />
   lista-&gt;lista = NULL;</p>
<p>   return agrup;<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>TSimbolo ordenar_lista(TSimbolo lista, TSimbolo novo)<br />
{<br />
   if(lista-&gt;probabilidade &lt;= novo-&gt;probabilidade)<br />
   {<br />
      novo-&gt;lista = lista;<br />
      lista = novo;<br />
   }<br />
   else<br />
   {<br />
      TSimbolo aux1 = lista, aux2 = lista-&gt;lista;<br />
      int      alocado = 0;<br />
      while(aux2 != NULL)<br />
      {<br />
         if(aux2-&gt;probabilidade &lt;= novo-&gt;probabilidade)<br />
         {<br />
            novo-&gt;lista = aux2;<br />
            aux1-&gt;lista = novo;<br />
            alocado = 1;<br />
            break;<br />
         }<br />
         aux1 = aux2;<br />
         aux2 = aux2-&gt;lista;<br />
      }</p>
<p>      if(!alocado)<br />
      {<br />
         aux1-&gt;lista = novo;<br />
         novo-&gt;lista = NULL;<br />
      }<br />
   }</p>
<p>   return lista;<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>TSimbolo agrupar_ultimos2(TSimbolo lista)<br />
{<br />
   TSimbolo agrup = (TSimbolo) malloc(sizeof(struct SIMBOLO));<br />
   agrup-&gt;lista = NULL;<br />
   agrup-&gt;simbolo = -1;<br />
   agrup-&gt;probabilidade = lista-&gt;probabilidade + lista-&gt;lista-&gt;probabilidade;<br />
   agrup-&gt;rlink = lista-&gt;lista;<br />
   agrup-&gt;llink = lista;<br />
   lista-&gt;mother = agrup;<br />
   lista-&gt;lista-&gt;mother = agrup;<br />
   lista = agrup;<br />
   lista-&gt;mother = NULL;</p>
<p>   return agrup;<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>TCodigo armazenar_simbolos(TSimbolo lista)<br />
{<br />
   TCodigo codigos = NULL, item;</p>
<p>   while(lista != NULL)<br />
   {<br />
      item = (TCodigo) malloc(sizeof(struct CODIGO));<br />
      item-&gt;endereco = lista;<br />
      item-&gt;simbolo = lista-&gt;simbolo;<br />
      item-&gt;probabilidade = lista-&gt;probabilidade;<br />
      item-&gt;link = codigos;<br />
      codigos = item;<br />
      lista = lista-&gt;lista;<br />
   }</p>
<p>   return codigos;<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void gerar_simbolos(TCodigo lista)<br />
{<br />
   TSimbolo aux1, aux2;<br />
   int      indice = 0;</p>
<p>   while(lista != NULL)<br />
   {<br />
      aux1 = lista-&gt;endereco;<br />
      aux2 = aux1-&gt;mother;<br />
      while(aux2 != NULL)<br />
      {<br />
         if(aux1 == aux2-&gt;llink)<br />
            lista-&gt;codigo[indice] = '0';<br />
         else if(aux1 == aux2-&gt;rlink)<br />
            lista-&gt;codigo[indice] = '1';<br />
         aux1 = aux2;<br />
         aux2 = aux2-&gt;mother;<br />
         indice++;<br />
      }<br />
      lista-&gt;codigo[indice] = '&#92;&#48;';<br />
      lista = lista-&gt;link;<br />
      indice = 0;<br />
   }<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void exibir_resultado(TCodigo lista)<br />
{<br />
   system(&quot;cls&quot;);<br />
   printf(&quot;\t IMPLEMENTACAO DO ALGORITMO DE HUFFMAN\n\n&quot;);</p>
<p>   while(lista != NULL)<br />
   {<br />
      printf(&quot; S%d - Prob: %.2f - %s\n&quot;, lista-&gt;simbolo, lista-&gt;probabilidade,<br />
                                         lista-&gt;codigo);<br />
      lista = lista-&gt;link;<br />
   }</p>
<p>   printf(&quot;\n Faltando ordenar os simbolos. . .&quot;);</p>
<p>   getch();<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void inverter_codigos(TCodigo lista)<br />
{<br />
   while(lista != NULL)<br />
   {<br />
      inverter_string(lista-&gt;codigo);<br />
      lista = lista-&gt;link;<br />
   }<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void inverter_string(char *string)<br />
{<br />
   int  i, j;<br />
   char temp[20];</p>
<p>   for(i = 0, j = strlen(string) - 1; j &gt;= 0; ++i, --j)<br />
      temp[i] = string[j];</p>
<p>   temp[i] = '&#92;&#48;';<br />
   strcpy(string, temp);<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void ordenar_codigos(TCodigo lista)<br />
{<br />
   TCodigo  nav;<br />
   TSimbolo auxE;<br />
   char     auxC[20];<br />
   int      auxS, chave;<br />
   float    auxP;</p>
<p>   do<br />
   {<br />
      chave = 0;<br />
      nav = lista;<br />
      while(nav-&gt;link != NULL)<br />
      {<br />
         if(nav-&gt;simbolo &gt; nav-&gt;link-&gt;simbolo)<br />
         {<br />
            auxE = nav-&gt;endereco;<br />
            strcpy(auxC, nav-&gt;codigo);<br />
            auxS = nav-&gt;simbolo;<br />
            auxP = nav-&gt;probabilidade;</p>
<p>            nav-&gt;endereco = nav-&gt;link-&gt;endereco;<br />
            strcpy(nav-&gt;codigo, nav-&gt;link-&gt;codigo);<br />
            nav-&gt;simbolo = nav-&gt;link-&gt;simbolo;<br />
            nav-&gt;probabilidade = nav-&gt;link-&gt;probabilidade;</p>
<p>            nav-&gt;link-&gt;endereco = auxE;<br />
            strcpy(nav-&gt;link-&gt;codigo, auxC);<br />
            nav-&gt;link-&gt;simbolo = auxS;<br />
            nav-&gt;link-&gt;probabilidade = auxP;</p>
<p>            chave = 1;<br />
         }<br />
         nav = nav-&gt;link;<br />
      }<br />
   }while(chave);<br />
}</p>
<p>//----------------------------------------------------------------------------

Não precisa assustar não… deu trabalho, mas funcionou. Nele, você insere as probabilidades dos símbolos e ele calcula o código de comprimento variável correspondente a cada símbolo.