Codificação de Huffman

Esta calculadora online gera codificação de Huffman baseada em um conjunto de símbolos e suas probabilidades

Esta calculadora online gera codificação de Huffman baseada em um conjunto de símbolos e suas probabilidades.
Uma descrição breve da codificação de Huffman está abaixo da calculadora.

PLANETCALC, Codificação de Huffman

Codificação de Huffman

Tabela de probabilidade de símbolos

NomeValor
Itens por página:

Dígitos após o ponto decimal: 2
Comprimento do percurso ponderado
 
Entropia da informação
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.

Extraído da Wikipédia

A codificação de Huffman é um método de compressão que usa as probabilidades de ocorrência dos símbolos no conjunto de dados a ser comprimido para determinar códigos de tamanho variável para cada símbolo. Ele foi desenvolvido em 1952 por David A. Huffman que era, na época, estudante de doutorado no MIT, e foi publicado no artigo "A Method for the Construction of Minimum-Redundancy Codes".

A codificação de Huffman use um método específico para escolher a representação para cada símbolo, resultando em um código prefixo (às vezes chamado de "códigos sem prefixo", ou seja, a cadeia de bit representando um símbolo particular nunca é um prefixo da cadeia de bit representando qualquer outro símbolo) que expressa os mais comuns símbolos de fonte utilizando cadeias mais curtas de bits que são usados para símbolos de fonte menos comuns. Huffman foi capaz de desenvolver o método de compressão mais eficiente deste tipo: nenhum outro mapeamento de símbolos de fonte individual para cadeias únicas de bits produzirá um tamanho menor de resultado médio quando as atuais frequências de símbolo concordam com aquelas utilizadas para criar o código.

A codificação de Huffman é um método tão amplamente utilizado para criar códigos prefixos que o termo "codificação de Huffman" é bastante utilizado como sinônimo de "código prefixo" mesmo quando este código não é produzido pelo algoritmo de Huffman.

A técnica se dá ao criar uma árvore binária de nós. Inicialmente, todos os nós são nós de folha, que contém o próprio símbolo, o peso (frequência de aparecimento) do símbolo e opcionalmente, uma ligação a um nó-pai que torna fácil a leitura do código (em reverso) começando pelo nó da folha. Nós internos contém peso do símbolo, ligações aos dois nós-filhos e uma ligação opcional a um nó-pai. Como convenção comum, o bit '0' representa seguindo o filho da esquerda e o bit '1' representa seguindo o filho da direita. Uma árvore finalizada tem até n nós de folha e n-1 nós internos. Uma árvore de Huffman que omite símbolos não utilizados produz comprimentos de código mais otimizados.

O processo essencialmente começa com os nós de folha contendo as probabilidades do símbolo que eles representam, então um novo nó cujos filhos são os 2 nós com a menor probabilidade é criado, de tal maneira que a probabilidade do novo nó é igual à soma da probabilidade dos filhos. Com os 2 nós prévios fundidos em um nó (logo não os considerando mais), e com o novo nó sendo agora considerado, o procedimento é repetido até que apenas um nó permaneça, a árvore de Huffman.

URL copiado para a área de transferência
PLANETCALC, Codificação de Huffman

Comentários