Shannon-Fano, Huffman, Huffman adaptativo

Este artigo refere-se à demonstração dos algoritmos de compressão e descompressão de dados sem perdas Shannon-Fano, Huffman e Huffman adaptativo, para melhor se compreenderem os passos necessários para a codificação e descodificação da informação.

O algoritmo de Shannon-Fano trata-se de um algoritmo de codificação de entropia, uma vez que efetua uma compressão sem perdas, e corresponde ao melhoramento da eficiência de representação da informação digital, sendo independente do tipo de dados a comprimir, representando uma codificação da informação com códigos de comprimento variável. Baseia-se na construção de uma árvore binária, de acordo com uma abordagem top-down.

O algoritmo de Huffman é igualmente um algoritmo de codificação de entropia, uma vez que também efetua uma compressão sem perdas (melhoramento da eficiência de representação da informação binária), sendo igualmente independente do tipo de dados a comprimir, e codificando a informação de entrada recorrendo a códigos binários de comprimento variável.

Um dos codecs mais conhecidos que usa o algoritmo de Huffman é o mp3. O algoritmo de Huffman é igualmente utilizado no âmbito dos formatos JPEG e MPEG, embora com algumas modificações. Este algoritmo baseia-se igualmente na construção de uma árvore binária, mas desta vez acordo com uma abordagem bottom-up.

O método de Huffman Adaptativo é considerado um método de compressão simétrico, já que a complexidade e o tempo de execução do respetivo codificador são idênticos aos da descompressão. Este método insere-se na categoria dos codificadores de entropia (compressão sem perdas). Relativamente ao algoritmo de Huffman adaptativo, pretendemos demonstrar a eficiência do método e a sua diferença em termos de rácio de compressão com o método original no contexto do artigo completo a ser publicado brevemente.

O artigo completo sobre os algoritmos de Shannon-Fano, Huffman e Huffman Adaptativo irão ser publicados no Portal da Compressão Multimédia, em http://multimedia.ufp.pt , onde será disponibilizada uma applet java que ilustra o detalhadamente o funcionamento de cada um destes métodos de compressão.

Advertisements

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s