Out-of-series #2 – Algoritmo de Lempel-Ziv

Padrão

Prosseguindo, ou melhor, não prosseguindo, já que este post não está na ordem “didática” do blog, vou postar aqui a outra implementação que fiz no final do ano passado para a disciplina de Fundamentos Matemáticos da Computação. Dessa vez, é o algoritmo de Lempel-Ziv. O professor Edson J. C. Gimenez suscintamente define o algoritmo de Lempel-Ziv:

“O algoritmo de Lempel-Ziv produz um código sem conhecer a estatística da fonte, e por isso é denominado Algoritmo de Codificação de Fonte Universal. (…)”

Também conhecido como LZ77, foi publicado em 1977 por Abraham Lempel e Jacob Ziv (taí o nome do algoritmo).

Bom, então segue a implementação do algoritmo utilizando a linguagem C. Assim como a implementação do algoritmo de Huffman, foi desenvolvido em ambiente Windows, com o mingW, mas pode ser facilmente adaptado para outras plataformas:

<br />
//////////////////////////////////////////////////////////////////////////////<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;</p>
<p>struct SIMBOLO<br />
{<br />
   int      numeracao;<br />
   char     simbolo[20];<br />
   char     codigo[20];<br />
   TSimbolo link;<br />
};</p>
<p>//----------------------------------------------------------------------------</p>
<p>void     lempel_ziv(char*);<br />
int      conferir_existencia(TSimbolo, char*);<br />
TSimbolo inserir(TSimbolo, char*);<br />
void     numerar_simbolos(TSimbolo);<br />
void     converter_binario(int, char*);<br />
void     inverter_string(char*);<br />
void     aplicar_numeracao(TSimbolo);<br />
void     aplicar_algoritmo(TSimbolo);<br />
int      buscar_indice(TSimbolo, char*);<br />
void     igualar_casas_binarias(TSimbolo);<br />
void     exibir_resultado(TSimbolo);</p>
<p>//----------------------------------------------------------------------------</p>
<p>int main(void)<br />
{<br />
   int  opcao;<br />
   char arquivo[25];</p>
<p>   do<br />
   {<br />
      system(&quot;cls&quot;);<br />
      printf(&quot;\tIMPLEMENTACAO DO ALGORITMO DE LEMPEL-ZIV\n\n&quot;);<br />
      printf(&quot; 1. Selecionar arquivo de entrada\n&quot;);<br />
      printf(&quot; 2. Finalizar aplicativo\n\n&quot;);<br />
      printf(&quot; Selecione a opcao desejada: &quot;);<br />
      scanf(&quot;%d&quot;, &amp;opcao);</p>
<p>      switch(opcao)<br />
      {<br />
         case 1 : printf(&quot;\n Digite o nome do arquivo de entrada: &quot;);<br />
                  fflush(stdin);<br />
                  gets(arquivo);<br />
                  lempel_ziv(arquivo);<br />
                  break;<br />
         case 2 : printf(&quot;\n Aplicativo encerrado 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 lempel_ziv(char *nome_arquivo)<br />
{<br />
   TSimbolo lista = NULL;<br />
   FILE *arquivo;<br />
   char simbolo[20];<br />
   int  indice = 0;</p>
<p>   arquivo = fopen(nome_arquivo, &quot;rt&quot;);</p>
<p>   if(arquivo != NULL)<br />
   {<br />
      simbolo[indice] = getc(arquivo);<br />
      while(!feof(arquivo))<br />
      {<br />
         simbolo[indice + 1] = '&#92;&#48;';<br />
         while(conferir_existencia(lista, simbolo))<br />
         {<br />
            indice++;<br />
            simbolo[indice] = getc(arquivo);<br />
            if(feof(arquivo))<br />
               simbolo[indice] = '0';<br />
            simbolo[indice + 1] = '&#92;&#48;';<br />
         }<br />
         lista = inserir(lista, simbolo);<br />
         indice = 0;<br />
         simbolo[indice] = getc(arquivo);<br />
      }<br />
      fclose(arquivo);<br />
      aplicar_numeracao(lista);<br />
      aplicar_algoritmo(lista);<br />
      igualar_casas_binarias(lista);<br />
      exibir_resultado(lista);<br />
   }<br />
   else<br />
   {<br />
      printf(&quot;\n Erro na abertura do arquivo %s. . .&quot;, nome_arquivo);<br />
      Sleep(2000);<br />
   }<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>int conferir_existencia(TSimbolo lista, char *simbolo)<br />
{<br />
   TSimbolo aux = lista;<br />
   int encontrado = 0;</p>
<p>   while(aux != NULL &amp;&amp; !encontrado)<br />
   {<br />
      if(strcmp(aux-&gt;simbolo, simbolo) == 0)<br />
         encontrado = 1;<br />
      aux = aux-&gt;link;<br />
   }</p>
<p>   return encontrado;<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>TSimbolo inserir(TSimbolo lista, char *simbolo)<br />
{<br />
   TSimbolo aux2 = lista, aux = (TSimbolo) malloc(sizeof(struct SIMBOLO));<br />
   strcpy(aux-&gt;simbolo, simbolo);<br />
   aux-&gt;link = NULL;</p>
<p>   if(lista == NULL)<br />
      lista = aux;<br />
   else<br />
   {<br />
      while(aux2-&gt;link != NULL)<br />
         aux2 = aux2-&gt;link;<br />
      aux2-&gt;link = aux;<br />
   }</p>
<p>   return lista;<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void numerar_simbolos(TSimbolo lista)<br />
{</p>
<p>   int contador = 1;</p>
<p>   while(lista != NULL)<br />
   {<br />
      lista-&gt;numeracao = contador;<br />
      contador++;<br />
      lista = lista-&gt;link;<br />
   }<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void converter_binario(int decimal, char *binario)<br />
{<br />
   int indice = 0, quociente, resto;</p>
<p>   do<br />
   {<br />
      quociente = decimal / 2;<br />
      resto = decimal % 2;<br />
      binario[indice] = resto + 48;<br />
      indice++;<br />
      decimal = quociente;<br />
   }while(quociente &gt; 0);</p>
<p>   binario[indice] = '&#92;&#48;';</p>
<p>   inverter_string(binario);<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 aplicar_numeracao(TSimbolo lista)<br />
{<br />
   int num = 1;</p>
<p>   while(lista != NULL)<br />
   {<br />
      lista-&gt;numeracao = num;<br />
      num++;<br />
      lista = lista-&gt;link;<br />
   }<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void aplicar_algoritmo(TSimbolo lista)<br />
{<br />
   TSimbolo aux = lista;<br />
   char     temp[20], codigo[20];<br />
   int      tamanho, numeracao, tam;</p>
<p>   while(aux != NULL)<br />
   {<br />
      strcpy(temp, aux-&gt;simbolo);<br />
      if(strlen(temp) == 1)<br />
         strcpy(aux-&gt;codigo, aux-&gt;simbolo);<br />
      else<br />
      {<br />
         temp[strlen(temp) - 1] = '&#92;&#48;';<br />
         numeracao = buscar_indice(lista, temp);<br />
         converter_binario(numeracao, codigo);<br />
         tam = strlen(codigo);<br />
         codigo[tam] = aux-&gt;simbolo[strlen(aux-&gt;simbolo) - 1];<br />
         codigo[tam + 1] = '&#92;&#48;';<br />
         strcpy(aux-&gt;codigo, codigo);<br />
      }<br />
      aux = aux-&gt;link;<br />
   }<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>int buscar_indice(TSimbolo lista, char *simbolo)<br />
{<br />
   while(lista != NULL)<br />
   {<br />
      if(!strcmp(lista-&gt;simbolo, simbolo))<br />
         break;<br />
      lista = lista-&gt;link;<br />
   }</p>
<p>   if(lista == NULL)<br />
      return -1;</p>
<p>   return lista-&gt;numeracao;<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void igualar_casas_binarias(TSimbolo lista)<br />
{<br />
   TSimbolo aux = lista;<br />
   unsigned int maior_tamanho = 0; // por causa dos warnings. . .<br />
   int repeticoes, i, j;</p>
<p>   while(aux != NULL)<br />
   {<br />
      if(strlen(aux-&gt;codigo) &gt; maior_tamanho)<br />
         maior_tamanho = strlen(aux-&gt;codigo);<br />
      aux = aux-&gt;link;<br />
   }</p>
<p>   aux = lista;<br />
   while(aux != NULL)<br />
   {<br />
      repeticoes = maior_tamanho - strlen(aux-&gt;codigo);<br />
      for(i = 1; i codigo) + 1; j &gt;= 1; --j)<br />
            aux-&gt;codigo[j] = aux-&gt;codigo[j - 1];<br />
         aux-&gt;codigo[0] = '0';<br />
      }<br />
      aux = aux-&gt;link;<br />
   }<br />
}</p>
<p>//----------------------------------------------------------------------------</p>
<p>void exibir_resultado(TSimbolo lista)<br />
{<br />
   system(&quot;cls&quot;);<br />
   printf(&quot;\tIMPLEMENTACAO DO ALGORITMO DE LEMPEL-ZIV\n\n &quot;);</p>
<p>   while(lista != NULL)<br />
   {<br />
      printf(&quot;%5.d \t\t- %s \t\t- %s\n &quot;, lista-&gt;numeracao, lista-&gt;simbolo, lista-&gt;codigo);<br />
      lista = lista-&gt;link;<br />
   }</p>
<p>   system(&quot;pause&quot;);<br />
}</p>
<p>//----------------------------------------------------------------------------<br />

O aplicativo lê de um arquivo .txt uma sequência de 0 e 1, apresentando ao final os códigos de largura fixa correspondentes.

Abraço e bons estudos!