Como funciona a codificação adaptativa de Huffman?

A codificação de Huffman é um método amplamente usado de codificação de entropia usado para compactação de dados. Pressupõe que tenhamos conhecimento completo das estatísticas de um sinal. No entanto, existem versões da codificação Huffman que são usadas com mídia de streaming e não podem saber tudo sobre as estatísticas do sinal. Como esses codificadores Huffman adaptáveis funcionam?

O artigo da Wikipedia tem uma descrição muito boa do processo de codificação adaptável de Huffman usando uma das implementações notáveis, o algoritmo de Vitter. Como você observou, um codificador Huffman padrão tem acesso à função de massa de probabilidade de sua sequência de entrada, usada para construir codificações eficientes para os valores de símbolo mais prováveis. No exemplo prototípico de compactação de dados baseada em arquivo, por exemplo, essa distribuição de probabilidade pode ser calculada histogramando a sequência de entrada, contando o número de ocorrências de cada valor de símbolo (símbolos podem ser sequências de 1 byte, por exemplo). Este histograma é usado para gerar uma árvore Huffman, como esta (retirada do artigo da Wikipedia):

A árvore é organizada diminuindo o peso ou a probabilidade de ocorrência na sequência de entrada; nós de folha no topo representam os símbolos mais prováveis, que, portanto, recebem as representações mais curtas no fluxo de dados compactados. A árvore é então salva junto com os dados compactados e é subsequentemente usada pelo descompactador posteriormente para regenerar a sequência de entrada (não compactada) novamente. Como uma das primeiras implementações de código de entropia, a codificação padrão de Huffman é bastante direta.

A estrutura do codificador adaptativo de Huffman é bastante semelhante; ele usa uma representação semelhante em árvore das estatísticas da sequência de entrada para selecionar codificações eficientes para cada valor do símbolo de entrada. A principal diferença é que, como uma implementação de streaming do algoritmo, nenhum conhecimento a priori da função de massa de probabilidade da entrada está disponível; as estatísticas da sequência devem ser estimadas em tempo real. Se alguém usar o mesmo esquema de codificação Huffman, isso significa que a árvore usada para gerar a codificação de cada símbolo no fluxo compactado deve ser construída e mantida dinamicamente à medida que o fluxo de entrada é processado.

O algoritmo de Vitter é uma maneira de conseguir isso; À medida que cada símbolo de entrada é processado, a árvore é atualizada, mantendo sua característica de diminuir a probabilidade de ocorrência de símbolos à medida que você se move para baixo na árvore. O algoritmo define um conjunto de regras sobre como a árvore é atualizada ao longo do tempo e como os dados compactados resultantes são codificados no fluxo de saída. Conforme a sequência de entrada é consumida, a estrutura da árvore deve representar uma descrição cada vez mais precisa da distribuição de probabilidade da entrada. Em contraste com a abordagem de codificação padrão de Huffman, o descompressor não possui uma árvore estática para decodificar; deve executar as mesmas funções de manutenção em árvore continuamente durante o processo de descompressão.

Em resumo : o codificador adaptável de Huffman opera de maneira muito semelhante ao algoritmo padrão; no entanto, em vez de uma medição estática de todas as estatísticas da sequência de entrada (a árvore Huffman), uma estimativa dinâmica e cumulativa (ou seja, do primeiro símbolo ao símbolo atual) da distribuição de probabilidade da sequência é usada para codificar (e decodificar) cada símbolo . Em contraste com a abordagem de codificação padrão de Huffman, o algoritmo adaptável de Huffman requer essa análise estatística no codificador e no decodificador.