Quelle est la qualité du code Huffman lorsqu'il n'y a pas de grandes lettres de probabilité?

Le code de Huffman pour une distribution de probabilité est le code de préfixe avec la longueur moyenne pondérée minimale du mot de code , où est la longueur du ème mot de code. C'est un théorème bien connu que la longueur moyenne par symbole du code Huffman est comprise entre et , où est l'entropie de Shannon de la distribution de probabilité. $p$ $\sum p_i \ell_i$ $\ell_i$ $i$ $H(p)$ $H(p)+1$ $H(p) = -\sum_i \, p_i \log_2 p_i$

Le mauvais exemple canonique, où la longueur moyenne dépasse l'entropie de Shannon de près de 1, est une distribution de probabilité telle que , où l'entropie est proche de 0 et la longueur moyenne des mots de code est 1. Cela donne un écart entre l'entropie et la longueur du mot de code de près de . $\{.999, .001\}$ $1$

Mais que se passe-t-il quand il y a une limite sur la plus grande probabilité dans la distribution de probabilité? Supposons, par exemple, que toutes les probabilités soient inférieures à . L'écart le plus important que j'ai pu trouver dans ce cas est pour une distribution de probabilité telle que , où l'entropie est légèrement supérieure à 1 et la longueur moyenne des mots de code est légèrement inférieure à 1,5, ce qui donne un écart approchant . Est-ce le mieux que vous puissiez faire? Pouvez-vous donner une limite supérieure sur l'écart strictement inférieur à 1 pour ce cas? $\frac{1}{2}$ $\{.499, .499, .002\}$ $0.5$

Maintenant, considérons le cas où toutes les probabilités sont très petites. Supposons que vous choisissez une distribution de probabilités sur lettres, chacune ayant la probabilité . Dans ce cas, l'écart le plus important se produit si vous choisissez . Ici, vous obtenez un écart d'environ Est-ce le mieux que vous puissiez faire dans une situation où toutes les probabilités sont faibles? $M$ $1/M$ $M \approx 2^k \ln 2$

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

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

Cette question est inspirée de cette question TCS Stackexchange .

optimization it.information-theory coding-theory Peter Shor
la source

Réponses:

Il existe de nombreux articles qui étudient exactement le problème que vous mentionnez. Le premier de la série est un article de Gallager, "Variations sur un thème de Huffman", IEEE-IT, vol. 24, 1978, p. 668-674. Il prouve que la différence entre la longueur moyenne des mots de code d'un code de Huffman et l'entropie (il appelle cette quantité "redondance") est toujours strictement inférieure à (= probabilité la plus élevée dans la distribution de probabilité), dans le cas , et il est inférieur à , si . De meilleures limites sont connues, vous pouvez les trouver dans les nombreux articles qui citent le travail de Gallager. $p$ $p\geq 1/2$ $p+0.086$ $p<1/2$

Ugo
la source

La limite optimale a été trouvée par Manstetten, Limites serrées sur la redondance des codes Huffman .

Yuval Filmus

À en juger par la limite , je crois que vous aviez l'intention de poser une question différente ... ou vous n'avez tout simplement pas précisé comment vous prenez la "moyenne". Je répondrai donc aux deux. La réponse est non aux deux questions. $H(p) \leq \ldots \leq H(p)+1$

Tout d'abord, si vous définissez la longueur moyenne du code en utilisant une distribution uniforme sur les mots de code et prenez comme limite supérieure de la probabilité d'un élément, alors considérez le code de longueur où mots de code ont une longueur et les restants ont une longueur . Pour la distribution parfaitement encodée par ce code, la longueur moyenne approche , sauf si vous avez également une borne inférieure pour la probabilité d'un élément, tandis que l'entropie est . $2^{-q}$ $q+k$ $2^{q-1}$ $q$ $2^{q+k-1}$ $q+k$ $q+k$ $q+\frac{k}{2}$

Considérons maintenant la «longueur moyenne» signifiant la longueur moyenne des mots de code lorsque le code Huffman est utilisé pour coder pour . Ici, la limite est étroite, et un exemple de distribution qui l'atteint dans la limite est celui dans lequel chaque élément se produit avec une probabilité pour(Le dernier élément se voit attribuer une probabilité résiduelle, mais cela ne fera aucune différence asymptotiquement). $p$ $2^{q\pm 1/2}$ $q \in {\mathbb Z}.$

Par exemple, considérons Ensuite, $q = 7.$

$A + B = 128, A\sqrt{2}+B/\sqrt{2}\leq 128, \max_{A \in {\mathbb Z}} A$ donne . Notre distribution a éléments avec une probabilité , avec une probabilité , et un élément obtient les restes. $A = 52, B = 76$ $52$ $2^{-6.5}$ $76$ $2^{-7.5}$

Alors , tandis que le code Huffman atteint perte d'entropie. (Par ailleurs, la perte d'entropie a un nom, que vous fassiez du codage Huffman ou du codage arbitraire pour : la divergence Kullback-Liebler . En l'utilisant, j'ai découvert il y a quelques jours, conduit à des limites de Chernoff à double face plus serrées, comme vous pouvez le voir sur Wikipédia pour les limites de 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
la source

Je suis quelque peu déconcerté par ce deuxième exemple. Si vous avez 128 mots de code, alors il y a un code avec une longueur moyenne de mot 7 (en fait, toutes les longueurs de mot en ont 7), ce qui contredit votre affirmation selon laquelle l'entropie est 7.09375. L'entropie de cette distribution (que vous obtenez en prenant une moyenne pondérée de et non une moyenne) est de 6,88, tandis que la longueur moyenne du code Huffman est de 7. Cela donne un écart (ou divergence Kullback-Liebler) de environ 0,12, ce qui semble être un peu mieux que mon exemple, mais pas près de 1.

- \log_{2} p_{i}

$-\log_2 p_i$

Peter Shor

Et en effet, vous avez raison. J'avais l'intention de poser des questions sur la longueur de mot de code attendue sous la distribution de probabilité .

p

$p$

Peter Shor

Oops, je mal calculé à propos vs . Nous voulons toujours que légèrement inférieur à , mais quelque chose comme , pour forcer les entrées les moins importantes dans la ligne inférieure. Cela donne

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

Carl

En fait, ce serait ... mais ce système d'équations n'a pas de solution positive - il semble que nous ne pouvons pas forcer tout à être des puissances demi-entières de . Ainsi, au lieu de et nous pouvons considérer, par exemple pour la moitié du code Huffman et pour le reste, donnant entrées ...

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$

Carl

Donc, essayez ceci (pas optimal - je suppose que cela dépend de la façon dont vous décidez d'arrondir vers le bas ou vers le haut). entrées avec probabilité et entrées avec probabilité ont l'entropie . Modifiez plutôt cela à entrées avec une probabilité et entrées avec une probabilité . L'entropie de cette distribution est ce qui donne 6,4023, tandis que l'entropie du code Huffman est 7,5 sous uniforme, etDonc, sauf si j'ai mal calculé (et je le fais souvent), cela donne un écart d'environ

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