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:

//////////////////////////////////////////////////////////////////////////////
//                                                                          //
//  IMPLEMENTAÇÃO DO ALGORITMO DE HUFFMAN                                   //
//  AUTOR: Rafael D. Toledo (rafaeldtoledo@gmail.com)                       //
//  WEB: www.rafaeltoledo.net                                               //
//                                                                          //
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <windows.h>

//----------------------------------------------------------------------------

typedef struct SIMBOLO *TSimbolo;

struct SIMBOLO
{
   int      numeracao;
   char     simbolo[20];
   char     codigo[20];
   TSimbolo link;
};

//----------------------------------------------------------------------------

void     lempel_ziv(char*);
int      conferir_existencia(TSimbolo, char*);
TSimbolo inserir(TSimbolo, char*);
void     numerar_simbolos(TSimbolo);
void     converter_binario(int, char*);
void     inverter_string(char*);
void     aplicar_numeracao(TSimbolo);
void     aplicar_algoritmo(TSimbolo);
int      buscar_indice(TSimbolo, char*);
void     igualar_casas_binarias(TSimbolo);
void     exibir_resultado(TSimbolo);

//----------------------------------------------------------------------------

int main(void)
{
   int  opcao;
   char arquivo[25];

   do
   {
      system("cls");
      printf("\tIMPLEMENTACAO DO ALGORITMO DE LEMPEL-ZIV\n\n");
      printf(" 1. Selecionar arquivo de entrada\n");
      printf(" 2. Finalizar aplicativo\n\n");
      printf(" Selecione a opcao desejada: ");
      scanf("%d", &opcao);

      switch(opcao)
      {
         case 1 : printf("\n Digite o nome do arquivo de entrada: ");
                  fflush(stdin);
                  gets(arquivo);
                  lempel_ziv(arquivo);
                  break;
         case 2 : printf("\n Aplicativo encerrado com sucesso. . .");
                  Sleep(2000);
                  break;
         default: printf("\n Opcao invalida. . .");
                  Sleep(2000);
      }
   }while(opcao != 2);

   return 0;
}

//----------------------------------------------------------------------------

void lempel_ziv(char *nome_arquivo)
{
   TSimbolo lista = NULL;
   FILE *arquivo;
   char simbolo[20];
   int  indice = 0;

   arquivo = fopen(nome_arquivo, "rt");

   if(arquivo != NULL)
   {
      simbolo[indice] = getc(arquivo);
      while(!feof(arquivo))
      {
         simbolo[indice + 1] = '\0';
         while(conferir_existencia(lista, simbolo))
         {
            indice++;
            simbolo[indice] = getc(arquivo);
            if(feof(arquivo))
               simbolo[indice] = '0';
            simbolo[indice + 1] = '\0';
         }
         lista = inserir(lista, simbolo);
         indice = 0;
         simbolo[indice] = getc(arquivo);
      }
      fclose(arquivo);
      aplicar_numeracao(lista);
      aplicar_algoritmo(lista);
      igualar_casas_binarias(lista);
      exibir_resultado(lista);
   }
   else
   {
      printf("\n Erro na abertura do arquivo %s. . .", nome_arquivo);
      Sleep(2000);
   }
}

//----------------------------------------------------------------------------

int conferir_existencia(TSimbolo lista, char *simbolo)
{
   TSimbolo aux = lista;
   int encontrado = 0;

   while(aux != NULL && !encontrado)
   {
      if(strcmp(aux->simbolo, simbolo) == 0)
         encontrado = 1;
      aux = aux->link;
   }

   return encontrado;
}

//----------------------------------------------------------------------------

TSimbolo inserir(TSimbolo lista, char *simbolo)
{
   TSimbolo aux2 = lista, aux = (TSimbolo) malloc(sizeof(struct SIMBOLO));
   strcpy(aux->simbolo, simbolo);
   aux->link = NULL;

   if(lista == NULL)
      lista = aux;
   else
   {
      while(aux2->link != NULL)
         aux2 = aux2->link;
      aux2->link = aux;
   }

   return lista;
}

//----------------------------------------------------------------------------

void numerar_simbolos(TSimbolo lista)
{

   int contador = 1;

   while(lista != NULL)
   {
      lista->numeracao = contador;
      contador++;
      lista = lista->link;
   }
}

//----------------------------------------------------------------------------

void converter_binario(int decimal, char *binario)
{
   int indice = 0, quociente, resto;

   do
   {
      quociente = decimal / 2;
      resto = decimal % 2;
      binario[indice] = resto + 48;
      indice++;
      decimal = quociente;
   }while(quociente > 0);

   binario[indice] = '\0';

   inverter_string(binario);
}

//----------------------------------------------------------------------------

void inverter_string(char *string)
{
   int  i, j;
   char temp[20];

   for(i = 0, j = strlen(string) - 1; j >= 0; ++i, --j)
      temp[i] = string[j];

   temp[i] = '\0';
   strcpy(string, temp);
}

//----------------------------------------------------------------------------

void aplicar_numeracao(TSimbolo lista)
{
   int num = 1;

   while(lista != NULL)
   {
      lista->numeracao = num;
      num++;
      lista = lista->link;
   }
}

//----------------------------------------------------------------------------

void aplicar_algoritmo(TSimbolo lista)
{
   TSimbolo aux = lista;
   char     temp[20], codigo[20];
   int      tamanho, numeracao, tam;

   while(aux != NULL)
   {
      strcpy(temp, aux->simbolo);
      if(strlen(temp) == 1)
         strcpy(aux->codigo, aux->simbolo);
      else
      {
         temp[strlen(temp) - 1] = '\0';
         numeracao = buscar_indice(lista, temp);
         converter_binario(numeracao, codigo);
         tam = strlen(codigo);
         codigo[tam] = aux->simbolo[strlen(aux->simbolo) - 1];
         codigo[tam + 1] = '\0';
         strcpy(aux->codigo, codigo);
      }
      aux = aux->link;
   }
}

//----------------------------------------------------------------------------

int buscar_indice(TSimbolo lista, char *simbolo)
{
   while(lista != NULL)
   {
      if(!strcmp(lista->simbolo, simbolo))
         break;
      lista = lista->link;
   }

   if(lista == NULL)
      return -1;

   return lista->numeracao;
}

//----------------------------------------------------------------------------

void igualar_casas_binarias(TSimbolo lista)
{
   TSimbolo aux = lista;
   unsigned int maior_tamanho = 0; // por causa dos warnings. . .
   int repeticoes, i, j;

   while(aux != NULL)
   {
      if(strlen(aux->codigo) > maior_tamanho)
         maior_tamanho = strlen(aux->codigo);
      aux = aux->link;
   }

   aux = lista;
   while(aux != NULL)
   {
      repeticoes = maior_tamanho - strlen(aux->codigo);
      for(i = 1; i codigo) + 1; j >= 1; --j)
            aux->codigo[j] = aux->codigo[j - 1];
         aux->codigo[0] = '0';
      }
      aux = aux->link;
   }
}

//----------------------------------------------------------------------------

void exibir_resultado(TSimbolo lista)
{
   system("cls");
   printf("\tIMPLEMENTACAO DO ALGORITMO DE LEMPEL-ZIV\n\n ");

   while(lista != NULL)
   {
      printf("%5.d \t\t- %s \t\t- %s\n ", lista->numeracao, lista->simbolo, lista->codigo);
      lista = lista->link;
   }

   system("pause");
}

//----------------------------------------------------------------------------

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!

3 comentários sobre “Out-of-series #2 – Algoritmo de Lempel-Ziv

  1. Plinio

    Muito bacana este post, gostaria de saber como fazer para ele ler o txt, como devo proceder p ele ler a sequência de binários ?

    Cordialmente grato pela vossa atenção.

    • Rafael

      Basta criar um arquivo txt e colocar nele a sequência binária (ex):
      10010010001001010101000110101010101
      E salvar com um nome qualquer. Coloque ele na mesma pasta do executável e indique o nome dele ao executar. =)

Deixe uma resposta