Out-of-series #1 – Algoritmo de Huffman

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.

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.

4 comentários sobre “Out-of-series #1 – Algoritmo de Huffman

  1. leonardo disse:

    Oi amigo , tem um erro no cabeçalho . falta os includes, acho que seriam
    #include
    #include
    #include
    //#include

    e na funcao abaixo, faltou definir a ‘probabilidade’ e a relação dos IFs

    TSimbolo ordenar_lista(TSimbolo lista, TSimbolo novo)
    {
    if(lista->probabilidade probabilidade)
    ….
    if(aux2->probabilidade probabilidade)

    Estou precisando de código para um trabalho :/

    Curtir

  2. Walber Do Carmo Farias disse:

    Ola amigos estou com problemas com esta sequencia :

    // Exemplo.cpp

    #include

    #include

    void main( )

    {

    int numero1, numero2, soma;

    cout<> numero1;

    cin>> numero2;

    soma = numero1 + numero2;

    cout<< ” A soma dos dois números é: “ << soma;

    getch( );

    }

    Quando peço para copilar da erro na linha 2: #include o programa acusa erro dizendo que não há arquivo ou diretorio.O que faço?

    Curtir

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

Este site utiliza o Akismet para reduzir spam. Saiba como seus dados em comentários são processados.