Por que a codificação de Huffman elimina a entropia que Lempel-Ziv não faz?

13

O popular algoritmo DEFLATE usa a codificação Huffman em cima do Lempel-Ziv.

Em geral, se tivermos uma fonte aleatória de dados (= entropia de 1 bit / bit), nenhuma codificação, incluindo Huffman, provavelmente a compactará em média. Se Lempel-Ziv fosse "perfeito" (que se aproxima da maioria das classes de fontes, à medida que o comprimento chega ao infinito), a pós-codificação com Huffman não ajudaria. Obviamente, Lempel-Ziv não é perfeito, pelo menos com comprimento finito, e por isso resta alguma redundância.

É essa redundância restante que a codificação de Huffman elimina parcialmente e, assim, melhora a compactação.

Minha pergunta é: Por que essa redundância restante é eliminada com êxito pela codificação de Huffman e não pela LZ? Quais propriedades de Huffman versus LZ fazem isso acontecer? Simplesmente executar LZ novamente (ou seja, codificar os dados compactados LZ com LZ uma segunda vez) faria algo semelhante? Se não, por que não? Da mesma forma, primeiro comprimir com Huffman e depois com LZ funcionaria, e se não, por que?

ATUALIZAÇÃO: É claro que, mesmo após o LZ, alguma redundância permanecerá. Várias pessoas fizeram esse ponto. O que não está claro é: Por que a redundância restante é mais bem tratada por Huffman do que por LZ? O que há de exclusivo nisso, em contraste com a redundância de fonte original, onde o LZ funciona melhor que o Huffman?

ds.algorithms it.information-theory coding-theory encoding SRobertJames
fonte

Respostas:

13

Originalmente, isso era um comentário, mas demorou demais.

Se você observar DEFLATE, o que está sendo compactado por Huffman é a saída do LZ77; O LZ77 funciona (quando isso leva menos bits que os dados brutos) enviando um ponteiro anteriormente para a sequência que está sendo compactada e um comprimento de correspondência que informa quantos símbolos levar após o ponteiro. A teoria mostra que, mesmo sem compressão adicional, essa técnica finalmente converge para a entropia da fonte. No entanto, na compactação de dados, sempre que houver uma distribuição que não seja completamente aleatória, você poderá compactá-la. Não há razão para acreditar que a saída do LZ77 - os ponteiros e os comprimentos das correspondências - sejam completamente aleatórios. Eles precisam convergir para completar a aleatoriedade no limite assintótico, já que o LZ77 é assintoticamente ideal, mas na prática você usa apenas um dicionário finito, então, presumivelmente, eles ficam longe o suficiente de serem completamente aleatórios para ganhar, fazendo uma compressão adicional neles. Naturalmente, você usa um código Huffman para os ponteiros e outro para os comprimentos das correspondências, pois esses dois processos têm estatísticas diferentes.

Por que usar Huffman em vez de LZ para a segunda rodada de compactação? A grande vantagem que LZ tem sobre Huffman é no tratamento de dependências entre símbolos. Em inglês, se uma letra é um 'q', a próxima é extremamente provável que seja um 'u' e assim por diante. Se os símbolos são eventos independentes, Huffman é mais simples e funciona tão bem ou melhor para seqüências curtas. Para a saída do LZ77, minha intuição é que os símbolos sejam razoavelmente independentes, portanto Huffman deve funcionar melhor.

Peter Shor
fonte
Estou com você no seu primeiro parágrafo: o LZ ainda deixa alguma redundância para comprimir ainda mais. Mas o seu segundo parágrafo ainda parece estar pulando, se não com a mão. Existem duas afirmações: 1. A redundância restante após LZ é de ordem zero (ou seja, p (X_n) é aproximadamente independente de x_n-1; estou usando o termo ordem zero como no modelo de ordem zero, por exemplo, data-compression.com/theory.shtml ) e 2. Na redundância de ordem zero, Huffman funciona melhor que LZ; Em redundância de ordem superior, o LZ funciona melhor. Talvez essas afirmações são verdadeiras, mas você não ter justificado quer
SRobertJames
2
@ Robert: Correlações de ordem superior não têm nenhum efeito sobre a codificação de Huffman. O LZ funciona de forma assintoticamente ideal para redundância de ordem superior, mas a sobrecarga extra necessária significa que ele não funciona tão bem em fontes de ordem zero de comprimento finito. Isso deve ter sido estudado experimentalmente na literatura em algum lugar; talvez alguém possa apontar uma referência. Para o ponto 1, minha intuição é que qualquer redundância de ordem superior restante após LZ é muito complicada para ser usada em qualquer esquema de codificação simples, mas não tenho uma boa maneira de justificar isso.
Peter Shor
10

A compactação de dados é realmente sobre duas coisas: modelagem e codificação. Os algoritmos da família LZ modelam o texto como uma concatenação de repetições exatas, que é assintoticamente ideal para muitas fontes aleatórias e razoavelmente bom para muitos textos reais. Para algumas entradas, esse modelo pode ser bastante ruim, no entanto. Por exemplo, você não pode usar LZ para compactar diretamente uma matriz de sufixos, mesmo que a matriz de sufixos seja tão compressível quanto o texto original.

(p,ℓ,c)pℓc

registro⁡nn

Então, em resumo, Huffman vence LZ na compactação das tuplas, pois seu modelo (distribuição fixa versus repetições exatas) é uma melhor correspondência para os dados.

Jouni Sirén
fonte
Obrigado Jouni. Parece que a principal redundância restante é que os comprimentos de repetições geralmente são menores e não maiores (não distribuídos uniformemente por [0,2 ^ n]). Huffman se sai bem nessa assimetria de ordem zero, enquanto o LZ realmente precisa de recursos maiores para funcionar bem. Isso está correto? E por que não usar Huffman para começar - por que se preocupar com LZ?
precisa saber é o seguinte
3
Se compactarmos o texto diretamente com Huffman, não podemos obter melhor compactação do que a entropia de ordem zero. No entanto, a maioria dos textos reais possui fontes significativas de redundância que não podem ser modeladas adequadamente com entropia de ordem zero. Em muitos casos, o uso do LZ antes do Huffman nos permite compactar essa redundância.
Jouni Sirén
2

Eu acredito que a resposta está no tamanho do dicionário de pesquisa.

Os dados têm um senso de localidade (isto é, se um dado tiver sido usado, é provável que ele seja usado novamente em breve), e o algoritmo LZ tira proveito disso na construção do dicionário de pesquisa. Ele gera uma tentativa com uma quantidade finita de nós possíveis, para manter as pesquisas rápidas . Quando atinge o limite de tamanho, faz outro teste, "esquecendo" o anterior. Portanto, é necessário criar novamente a tabela de pesquisa para os caracteres mais simples, mas se algumas palavras não forem mais usadas, elas não serão mais mantidas na memória, para que uma codificação menor possa ser usada.

Portanto, uma saída LZ pode ser reduzida ainda mais com a codificação Huffman, pois essa redundância na criação das tentativas de pesquisa pode ser detectada por análise estatística.

Manuel Ferreria
fonte
Aceito o primeiro parágrafo: você explica por que o LZ deixa redundância. Mas o segundo parágrafo parece um salto: por que Huffman percebe essa redundância? Por que não LZ novamente? E, se Huffman é mais abrangente, por que não apenas para começar?
precisa saber é o seguinte
2

Talvez eu esteja errado aqui, mas a codificação de Huffman analisa toda a entrada para criar sua tabela de codificação (árvore), enquanto o Lempel-Ziv codifica à medida que avança. Isso é uma vantagem e uma desvantagem para Huffman. A desvantagem é óbvia, a saber, que precisamos ver toda a entrada antes que possamos começar. A vantagem é que Huffman levará em consideração as estatísticas que ocorrem em qualquer parte da entrada, enquanto Lempel-Ziv precisa aumentá-la progressivamente. Ou, de outra maneira, Lempel-Ziv tem uma "direção" que Huffman não tem.

Mas tudo isso é apenas minha maneira ingênua de imaginar como as coisas são. Precisamos de uma prova real aqui para ver como exatamente Huffman supera Lempel-Ziv.

Andrej Bauer
fonte
2
As pessoas definiram a codificação adaptativa de Huffman, que apenas analisa a entrada uma vez. Para os propósitos desta discussão, a codificação adaptativa e não adaptativa de Huffman se comportará de maneira semelhante.
quer
2

A resposta curta é: LZ é um algoritmo "universal", na medida em que não precisa saber a distribuição exata da fonte (apenas a suposição de que a fonte é estacionária e ergódica). Mas Huffman não é; ele precisa saber a distribuição exata da qual a fonte é amostrada (para criar a árvore Huffman). Essas informações adicionais fazem com que Huffman obtenha garantias de compactação rígidas. No entanto, para algoritmos práticos de compactação de arquivos, o Huffman pode ser menos favorável, pois primeiro será necessário reunir estatísticas empíricas do arquivo e, em seguida, realizar a compactação real no segundo semestre, enquanto o LZ pode ser implementado on-line.

Mais detalhes podem ser encontrados nos textos padrão da teoria da informação, por exemplo, Elementos da Teoria da Informação por Cover e Thomas.

MCH
fonte
Penso que a fonte ergódica estacionária é apenas uma suposição que facilita a análise de LZ. Afinal, a compactação é baseada nas propriedades combinatórias da entrada, que por coincidência coincidem muito bem com as propriedades estatísticas em muitos casos. Considere, por exemplo, uma coleção de textos em inglês em formato de texto sem formatação, seguidos pelos mesmos textos em formato HTML. O LZ compacta essa coleção bastante bem, mesmo que não pareça algo gerado por uma fonte ergódica estacionária.
Jouni Sirén
@ Jouni: Eu discordaria deste comentário; Penso que, em certo sentido, a linguagem inglesa em texto simples se parece muito com uma fonte ergódica estacionária, e essa semelhança é exatamente o que o LZ está aproveitando.
Peter Shor
@ Peter: Mas, neste caso, a fonte primeiro gera alguns textos em formato de texto sem formatação e, em seguida, exatamente os mesmos textos em formato HTML. Essa mudança de texto sem formatação para HTML em algum ponto arbitrário parece quebrar a propriedade estacionária ergódica. Por outro lado, os resultados da compactação são muito melhores do que ao compactar os textos sem formatação e os textos em HTML separadamente, pois há muitas informações mútuas entre um texto em formato de texto sem formatação e o mesmo texto em formato HTML.
Jouni Sirén