Codificação Huffman

A codificação de Huffman é um algoritmo de compressão de dados sem perdas . A codificação Huffman usa código de comprimento variável para representar um símbolo de origem (por exemplo, um caractere em um arquivo). O código é determinado a partir de uma estimativa das probabilidades de aparecimento dos símbolos fonte, sendo um código curto associado aos símbolos fonte mais frequentes.

Um código de Huffman é ótimo no sentido de menor comprimento para codificação de símbolo e uma distribuição de probabilidade conhecida. Métodos mais complexos de modelagem probabilística da fonte permitem obter melhores taxas de compressão.

Foi inventado por David Albert Huffman e publicado em 1952.

Princípio

O princípio da codificação de Huffman é baseado na criação de uma estrutura em árvore composta por nós.

Suponha que a frase a ser codificada seja " este é um exemplo de uma árvore Huffman ". Primeiro, procuramos o número de ocorrências de cada personagem. No exemplo anterior, a frase contém 2 vezes o caractere he 7 espaços. Cada personagem constitui uma das folhas da árvore à qual associamos um peso igual ao seu número de ocorrências.

A árvore é criada da seguinte forma, associamos a cada vez os dois nós de menor peso, para dar um novo nó cujo peso é equivalente à soma dos pesos de seus filhos. Reiteramos esse processo até que tenhamos apenas um nó restante: a raiz. Então, por exemplo, o código 0 é associado a cada ramificação rodando à esquerda e o código 1 à direita.

Para obter o código binário de cada personagem, voltamos a árvore da raiz às folhas adicionando cada vez ao código um 0 ou um 1 dependendo do ramo seguido. A frase " este é um exemplo de uma árvore huffman " é então codificada em 135 bits em vez de 288 bits (se a codificação de caractere inicial for de 8 bits). É necessário começar pela raiz para obter os códigos binários, porque caso contrário, ao descompactar, começar pelas folhas pode causar confusão na decodificação.

Para codificar a " Wikipedia ", obtemos, portanto, em binário: 101 11 011 11 100 010 001 11 000, ou 24 bits em vez de 63 (9 caracteres x 7 bits por caractere) usando códigos ASCII (7 bits).

Diferentes métodos de construção da árvore

Existem três variações do algoritmo de Huffman, cada uma das quais define um método para criar a árvore:

estático: cada byte possui um código predefinido pelo software. A árvore não precisa ser transmitida, mas a compressão só pode ser feita em um único tipo de arquivo (por exemplo: um texto em francês, onde as frequências de aparecimento do 'e' são enormes; portanto, terá um tamanho muito curto código, uma reminiscência do alfabeto Morse );
semi-adaptativo: primeiro se lê o arquivo, de modo a calcular as ocorrências de cada byte, depois a árvore é construída a partir dos pesos de cada byte. Esta árvore permanecerá a mesma até o final da compressão. Esta compressão causará um ganho de bits maior ou igual à codificação estática de Huffman mas será necessário, para a descompressão, transmitir a árvore, o que geralmente cancelará o ganho obtido;
adaptativo: este é o método que a priori oferece as melhores taxas de compressão porque usa uma árvore conhecida (e portanto não transmitida) que será então modificada dinamicamente à medida que o fluxo é comprimido de acordo com os símbolos encontrados anteriormente. Porém, este método representa a grande desvantagem de ter que modificar a árvore com freqüência, o que implica em um maior tempo de execução. Por outro lado, a compressão é sempre ótima e não é necessário que o arquivo seja conhecido antes de comprimir. Em particular, o algoritmo é capaz de trabalhar em fluxos de dados ( streaming ), porque não é necessário saber os símbolos que virão.

Propriedades

Um código Huffman é o código-fonte . Para uma fonte , representada por uma variável aleatória , de distribuição de probabilidade , a expectativa do comprimento de um código é dada por $S$ $X$ $p$ $VS$

L (C) = \ sum_ {x \ in \ Omega} p (x) \ cdot l (x)

Onde está o comprimento da palavra de código, o código associado ao símbolo de origem e é o conjunto de símbolos de origem. $l (x)$ $C (x)$ $x$ $\Ómega$

Um código Huffman é um código de prefixo com comprimento variável . É ideal, no sentido de comprimento mais curto, para codificação de símbolos . Ou seja, para um código Huffman e para qualquer código decodificável exclusivamente , então: $C ^ *$ $VS$

L (C ^ *) \ le L (C)

Limitações da codificação Huffman

Podemos mostrar que, para uma fonte , a entropia de Shannon, o comprimento médio de uma palavra de código obtida pela codificação de Huffman satisfaz: $X$ $H (X)$ $eu$

H (X) \ le L <H (X) +1

Esta relação mostra que a codificação de Huffman se aproxima da entropia da fonte, ou seja, do código ideal, mas isso pode de fato se revelar bastante desinteressante no caso em que a entropia da fonte é forte, e onde uma sobrecarga de 1 bit torna-se significativo. Além disso, a codificação de Huffman requer o uso de um número inteiro de bits para um símbolo de origem, o que pode ser ineficiente.

Uma solução para esse problema é trabalhar em blocos de símbolos. Em seguida, mostramos que podemos chegar mais perto da entropia: $não$

H (X) \ le L <H (X) + \ frac {1} {n}

mas o processo de estimar probabilidades torna-se mais complexo e caro.

Além disso, a codificação de Huffman não é adequada no caso de uma fonte cujas propriedades estatísticas mudam com o tempo, uma vez que as probabilidades dos símbolos mudam e a codificação se torna inadequada. A solução que consiste em re-estimar as probabilidades dos símbolos a cada iteração é impraticável devido à sua complexidade de tempo. A técnica então se torna a codificação Huffman adaptativa : para cada novo símbolo, a tabela de frequência é atualizada e a árvore de codificação modificada, se necessário. O descompressor fazendo o mesmo pelas mesmas causas ... permanece sincronizado com o que o compressor fez.

Na prática, quando queremos abordar a entropia, preferimos uma codificação aritmética que seja ótima no nível de bits.

Métodos mais complexos realizando uma modelagem probabilística da fonte e aproveitando esta redundância adicional tornam possível melhorar o desempenho de compressão deste algoritmo (ver LZ77 , predição por reconhecimento parcial , ponderação de contextos ).

Código canônico

Para que o mesmo conjunto de símbolos seja codificado, vários códigos de Huffman diferentes podem ser obtidos.

É possível transformar um código Huffman em um código Huffman canônico único para um determinado conjunto de símbolos de entrada. O princípio é inicialmente ordenar os símbolos em ordem lexical.

Nota: entre dois símbolos S1 e S2 que, em um código de Huffman específico, são codificados com o mesmo comprimento, são sempre codificados com o mesmo comprimento no código de Huffman canônico. No caso em que dois símbolos têm a mesma probabilidade e dois comprimentos de código diferentes, é possível que a passagem de um código de Huffman para um código de Huffman canônico modifique o comprimento desses códigos, a fim de garantir a atribuição do código. o primeiro símbolo em ordem lexicográfica.

Usos

A codificação Huffman é baseada apenas na frequência relativa dos símbolos de entrada (sequências de bits), sem distinção de sua origem (imagens, vídeos, sons, etc. ). Por isso, geralmente é utilizado no segundo estágio de compressão, uma vez que a redundância específica da mídia foi demonstrada por outros algoritmos. Pensa-se em particular na compressão JPEG para as imagens , MPEG para os vídeos e MP3 para o som , os quais podem remover os elementos supérfluos imperceptíveis aos humanos. Em seguida, falamos de compressão não conservadora (com perdas).

Outros algoritmos de compactação conservadores (sem perdas), como os usados para compactação de arquivos, também usam Huffman para compactar o dicionário resultante. Por exemplo, LZH ( Lha ) e deflate ( ZIP , gzip , PNG ) combinam um algoritmo de compressão de dicionário ( LZ77 ) e codificação de entropia de Huffman.

História

A codificação foi inventada por David Albert Huffman , durante sua tese de doutorado no MIT . O algoritmo foi publicado em 1952 no artigo Um Método para a Construção de Códigos de Redundância Mínima , nos Anais do Institute of Radio Engineers .

O primeiro Macintosh empresa Maçã usado um código com base Huffman para a representação de textos: os 15 caracteres mais frequentes de uma língua foram codificados em 4 bits, e o 16 th configuração serviu como um prefixo para a codificação de outro de byte único (que assim feito às vezes 4 bits, às vezes 12 bits por caractere, consulte UTF-8 ). Descobriu-se que esse método simples economiza 30% de espaço em um texto médio em um momento em que a RAM ainda era um componente caro.

Veja também

links externos

Bibliografia

(pt) DA Huffman, " Um método para a construção de códigos de redundância mínima " (PDF), Proceedings of the IRE,Setembro de 1952, pp 1098-1102
(en) Thomas M. Cover, Joy A. Thomas, Elements of Information Theory , Wiley-Interscience,2006( ISBN 978-0-471-24195-9 ) [ detalhe das edições ]

Notas e referências

(fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado " Huffman coding " ( veja a lista de autores ) .

Mark Nelson ( traduzido por Soulard Hervé), compressão de dados: texto, imagens, sons , França, Dunod ,1993, 420 p. ( ISBN 2-10-001681-4 ) , página 65.
Cover, Thomas (2006) , p. 123-127.
DA Huffman, Um método para a construção de códigos de redundância mínima , Proceedings of the IRE, setembro de 1952, pp. 1098-1102.