Quão bom é o código Huffman quando não há grandes letras de probabilidade?

21

O código de Huffman para uma distribuição de probabilidade p é o código de prefixo com a palavra de código ponderado média comprimento mínimo pii , onde i é o comprimento do i th codword. É um teorema bem conhecido que o comprimento médio por símbolo do código de Huffman está entre H(p) e H(p)+1 , onde H(p)=ipilog2pi é a entropia de Shannon da distribuição de probabilidade.

O mau exemplo canônico, em que o comprimento médio excede a entropia de Shannon em quase 1, é uma distribuição de probabilidade como {.999,.001} , onde a entropia é quase 0 e o comprimento médio da palavra de código é 1. Isso cria uma lacuna entre a entropia e o comprimento da palavra-código de quase 1 .

Mas o que acontece quando há um limite para a maior probabilidade na distribuição de probabilidade? Suponha, por exemplo, que todas as probabilidades sejam menores que 12 . A maior lacuna que eu pude encontrar neste caso é para uma distribuição de probabilidade como{.499,.499,.002}, em que a entropia é um pouco mais de 1 e o comprimento médio da palavra de código é um pouco menor que 1,5, dando uma lacuna se aproximando0.5. Isso é o melhor que pode fazer? Você pode definir um limite superior para o espaço estritamente menor que 1 neste caso?

Agora, vamos considerar o caso em que todas as probabilidades são muito pequenas. Suponha que você escolher uma distribuição de probabilidade sobre M letras, cada um com probabilidade 1/M . Nesse caso, a maior lacuna ocorre se você escolher M2kln2 . Aqui, você tem uma diferença de cerca de

1+lnln2ln2ln20.08607.
É o melhor que você pode fazer na situação em que todas as probabilidades são pequenas?

Esta pergunta foi inspirada nesta pergunta do TCS Stackexchange .

Peter Shor
fonte

Respostas:

19

Existem muitos trabalhos que estudam exatamente o problema que você menciona. O primeiro da série é um artigo de Gallager, "Variações sobre um tema de Huffman", IEEE-IT, vol. 24, 1978, pp. 668-674. Ele prova que a diferença entre o comprimento codeword média de um código de Huffman e a entropia (ele chama essa quantidade "redundância") é sempre estritamente menor que (= maior probabilidade na distribuição de probabilidade), no caso p 1 / 2 , e é inferior a P + 0,086 , se p < 1 / 2 . Os limites melhores são conhecidos, você pode encontrá-los nos vários artigos que citam o trabalho do Gallager.pp1/2p+0.086p<1/2

Ugo
fonte
2
O limite ideal foi encontrado por Manstetten, Limites apertados na redundância dos códigos Huffman .
Yuval Filmus
2

A julgar pelo limite de , acredito que você pretendia fazer uma pergunta diferente ... ou simplesmente não especificou como avalia a "média". Então eu vou responder as duas. A resposta é não às duas perguntas.H(p)H(p)+1

Primeiro, se você definir o tamanho médio do código usando uma distribuição uniforme sobre as palavras de código e considerar como o limite superior na probabilidade de qualquer elemento, considere o código de comprimento q + k, em que 2 q - 1 as palavras de código têm comprimento q e os restantes 2 q + k - 1 têm comprimento q + k . Para a distribuição perfeitamente codificada por esse código, o comprimento médio se aproxima de q + k , a menos que você também tenha um limite inferior para a probabilidade de um elemento, enquanto a entropia é2qq+k2q1q2q+k1q+kq+k .q+k2

Agora, vamos considerar o "comprimento médio", que significa o comprimento médio da palavra de código quando o código Huffman é usado para codificar . Aqui, o limite é apertado, e uma distribuição exemplo realizá-lo no limite é aquela em que cada elemento ocorre com probabilidade 2 q ± 1 / 2 para q Z . (Ao elemento final é atribuída qualquer probabilidade restante, mas não fará diferença assintoticamente).p2q±1/2qZ.

Por exemplo, considere Entãoq=7.

A=52,B=76522 - 6,5 762 - 7,5A+B=128,A2+B/2128,maxAZAA=52,B=765226.57627.5

Então , enquanto o código Huffman alcança perda de entropia. (Aliás, a perda de entropia tem um nome, seja você codificação Huffman ou codificação arbitrária para : a divergência Kullback-Liebler . Descobri isso alguns dias atrás, levando a limites Chernoff mais duplos, como você pode ver na Wikipedia para limites Chernoff.)H(X)=(526.5+767.5)/128=7.09375(520.5760.5)/1280.99436QD(PQ)=pilogpiqi+(1pi)log1pi1qi

Carl
fonte
11
Estou um pouco confuso com este segundo exemplo. Se você possui 128 palavras de código, existe um código com tamanho médio de palavra 7 (na verdade, todos os comprimentos de palavra têm 7), o que contradiz sua afirmação de que a entropia é 7.09375. A entropia dessa distribuição (que você obtém com uma média ponderada de e não uma média) é 6,88, enquanto o comprimento médio do código Huffman é 7. Isso fornece uma diferença (ou divergência Kullback-Liebler) de em torno de 0,12, o que parece ser um pouco melhor do que o meu exemplo, mas não perto de 1.log2pi
Peter Shor
E, de fato, você está certo. Pretendia perguntar sobre o comprimento esperado da palavra de código na distribuição de probabilidade . p
Peter Shor
Opa, eu calculei mal sobre vs . Ainda queremos um pouco menos que , mas algo como , para forçar as entradas menores na linha inferior. Isso forneceABA2+B/22kA+2B=2kA=21/221B.
2024 Carl
Na verdade, isso seria ... mas esse sistema de equações não tem uma solução positiva - parece que não podemos forçar tudo a ser potências de meio inteiro de . Portanto, em vez de e , podemos considerar, por exemplo, para metade do código Huffman e para o resto, dando entradas ... #2A+B221/2(1+x)/2k(1x)/2k+132k
202 Carl Carl
Portanto, tente isso (não é o ideal - suponho que depende de como você decide arredondar para baixo ou para cima). entradas com probabilidade e entradas com probabilidade possuem entropia . Em vez disso, altere para entradas com probabilidade e entradas com probabilidade . A entropia dessa distribuição é 5,802, o que fornece 6,4023, enquanto a entropia do código de Huffman é 7,5 sob uniforme, ePortanto, a menos que eu calcule mal (e o faço frequentemente), isso gera uma lacuna de cerca de641/1281281/2567.5641/12821281/256(21/2)(1-2 - 1,5 )7+2 - 1,581/(22)7.5+(11/(2(2)))5.8020,95(121.5)7+21.58=7.3535.0.95 .
Carl