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

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 $\sum p_i \ell_i$ , onde $\ell_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) = -\sum_i \, p_i \log_2 p_i$ é 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 $\frac{1}{2}$ . 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 aproximando $0.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 $M \approx 2^k \ln 2$ . Aqui, você tem uma diferença de cerca de

\frac{1 + \ln \ln 2 - \ln 2}{\ln 2} \approx 0.08607.

$\frac{1 + \ln \ln 2 - \ln 2}{\ln 2} \approx 0.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 .

optimization it.information-theory coding-theory Peter Shor
fonte

Respostas:

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 , e é inferior a , se . Os limites melhores são conhecidos, você pode encontrá-los nos vários artigos que citam o trabalho do Gallager. $p$ $p\geq 1/2$ $p+0.086$ $p<1/2$

Ugo
fonte

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

Yuval Filmus

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) \leq \ldots \leq 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 que palavras de código têm comprimento e os restantes têm comprimento . Para a distribuição perfeitamente codificada por esse código, o comprimento médio se aproxima de , a menos que você também tenha um limite inferior para a probabilidade de um elemento, enquanto a entropia é $2^{-q}$ $q+k$ $2^{q-1}$ $q$ $2^{q+k-1}$ $q+k$ $q+k$ . $q+\frac{k}{2}$

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 para (Ao elemento final é atribuída qualquer probabilidade restante, mas não fará diferença assintoticamente). $p$ $2^{q\pm 1/2}$ $q \in {\mathbb Z}.$

Por exemplo, considere Então $q = 7.$

$A + B = 128, A\sqrt{2}+B/\sqrt{2}\leq 128, \max_{A \in {\mathbb Z}} A$ $A = 52, B = 76$ $52$ $2^{-6.5}$ $76$ $2^{-7.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) = (52\cdot 6.5 + 76 \cdot 7.5)/128 = 7.09375$ $(52 \cdot 0.5 - 76 \cdot 0.5)/128 \approx 0.99436$ $Q$ $D(P\Vert Q) = \sum p_i \log \frac{p_i}{q_i} + \sum (1-p_i) \log \frac{1-p_i}{1-q_i}$

Carl
fonte

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.

- \log_{2} p_{i}

$-\log_2 p_i$

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

$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 fornece

A

$A$

B

$B$

A \sqrt{2} + B / \sqrt{2}

$A\sqrt{2}+B/\sqrt{2}$

2^{k}

$2^k$

A + 2 B = 2^{k}

$A+2B=2^k$

A = \frac{2 - 1 / \sqrt{2}}{\sqrt{2} - 1} B .

$A = \frac{2-1/\sqrt{2}}{\sqrt{2}-1}B.$

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 ... #

2 A + B

$2A+B$

2

$2$

\sqrt{2}

$\sqrt{2}$

1 / \sqrt{2}

$1/\sqrt{2}$

(1 + x) / 2^{k}

$(1+x)/2^k$

(1 - x) / 2^{k + 1}

$(1-x)/2^{k+1}$

3 * 2^{k}

$3*2^k$

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 de

64

$64$

1 / 128

$1/128$

128

$128$

1 / 256

$1/256$

7.5

$7.5$

64

$64$

1 / 128 \sqrt{2}

$1/128\sqrt{2}$

128

$128$

1 / 256 (2 - 1 / \sqrt{2})

$1/256(2-1/\sqrt{2})$

1 / (2 \sqrt{2}) * 7.5 + (1 - 1 / (2 \sqrt{(} 2))) * 5.802

$1/(2\sqrt{2})*7.5+(1-1/(2\sqrt(2)))*5.802$

(1 - 2^{- 1.5}) * 7 + 2^{- 1.5} * 8 = 7.3535.

$(1-2^{-1.5})*7+2^{-1.5}*8 = 7.3535.$

0.95

$0.95$ .

Carl