Y a-t-il une généralisation du codage de Huffman au codage arithmétique?

En essayant de comprendre les relations entre le codage Huffman, le codage arithmétique et le codage par plage, j'ai commencé à penser que les défauts du codage Huffman étaient liés au problème de la compression fractionnaire des bits .

Autrement dit, supposons que vous ayez 240 valeurs possibles pour un symbole et que vous deviez les coder en bits, vous seriez bloqué avec 8 bits par symbole, même si vous n'avez pas besoin d'un 8 "complet", car 8 peut exprimer 256 valeurs possibles par symbole. Une solution à ce problème est quelque chose que j'ai vu appelé "emballage de bits fractionnel", où vous pouvez "bitshift" par une non-puissance de deux en utilisant la multiplication. Tout comme la multiplication des puissances de deux se déplace x * 2 == x << 1et x * 4 == x << 2ainsi de suite pour toutes les puissances de deux, vous pouvez également "décaler" avec une non-puissance de 2 en multipliant à la place et emballer dans des symboles de taille fractionnaire. .

Le problème est similaire avec le codage Huffman: vous vous retrouvez avec des codes qui doivent être de longueur non fractionnaire et donc il présente cette inefficacité de compression. Cependant, vous ne pouvez pas simplement utiliser la solution de compression de bits fractionnée, car cette solution suppose des symboles de taille fixe.

La question est, existe-t-il des articles ou des solutions pour améliorer le codage de Huffman avec une idée similaire à la compression de bits fractionnaire pour obtenir quelque chose de similaire au codage arithmétique? (ou tout résultat contraire).

Examinons une façon légèrement différente de penser le codage Huffman.

Supposons que vous ayez un alphabet de trois symboles, A, B et C, avec des probabilités de 0,5, 0,25 et 0,25. Parce que les probabilités sont toutes des puissances inverses de deux, cela a un code de Huffman qui est optimal (c'est-à-dire qu'il est identique au codage arithmétique). Nous utiliserons le code canonique 0, 10, 11 pour cet exemple.

Supposons que notre état soit un grand entier, que nous appellerons . Vous pouvez penser à l'encodage comme une fonction qui prend l'état actuel, et un symbole à encoder, et retourne le nouvel état:$s$

$$\begin{align*} \hbox{encode}(s, A) &= 2s\\ \hbox{encode}(s, B) &= 4s + 2\\ \hbox{encode}(s, C) &= 4s + 3\\ \end{align*}$$

Commençons donc par l'état 11 (qui est 1011 en binaire), encodons le symbole B. Le nouvel état est 46, qui est 101110 en binaire. Comme vous pouvez le voir, c'est "l'ancien" état avec la séquence 10 ajoutée à la fin. Nous avons essentiellement "sorti" la séquence de bits 10.

Jusqu'ici tout va bien.

Réfléchissez maintenant un instant au fonctionnement du codage arithmétique. Si vous placez les probabilités sur un dénominateur commun, le symbole A représente en fait la plage , le symbole B représente la plage[$[\frac{0}{4},\frac{2}{4})$et le symbole C représente la plage[$[\frac{2}{4},\frac{3}{4})$.$[\frac{3}{4},\frac{4}{4})$

Fondamentalement, ce que nous faisons ici est de tout multiplier par le dénominateur commun. Imaginez que l'état était en fait dans la base 4. L'encodage d'un symbole B génère réellement le chiffre 2 dans cette base, et l'encodage d'un symbole C génère le chiffre 3 dans cette base.

Cependant, le symbole A est un peu différent, car il ne s'agit pas d'un chiffre entier dans la base 4.

Au lieu de cela, nous pouvons considérer l'alphabet comme l'ensemble des symboles A_0, A_1, B, C, avec une probabilité égale. Ceci, encore une fois, a un code Huffman optimal 00, 01, 10, 11. Ou, encore une fois, nous pouvons penser à cela dans la base 4. Pour coder un symbole, nous faisons simplement:

$$\begin{align*} \hbox{encode}(s, A_0) &= 4s + 0\\ \hbox{encode}(s, A_1) &= 4s + 1\\ \hbox{encode}(s, B) &= 4s + 2\\ \hbox{encode}(s, C) &= 4s + 3 \end{align*}$$

$A_0$$A_1$

$s$

$$s' = \left\lfloor \frac{s}{2} \right\rfloor$$ $$i = s \bmod 2$$

$\hbox{encode}(s', A_i)$

$s=11$$s'=5$$i=1$$\hbox{encode}(5, A_1) = 4\times 5+1 = 21$

Maintenant, cela ne produit pas exactement la même sortie binaire que le codage Huffman, mais cela génère une sortie qui a la même longueur. Et ce que j'espère que vous pouvez voir, c'est que c'est également uniquement décodable. Pour décoder un symbole, nous prenons le reste divisé par 4. Si la valeur est 2 ou 3, alors le symbole est B ou C respectivement. Si c'est 0 ou 1, alors le symbole est A, puis nous pouvons remettre le bit d'information en multipliant l'état par 2 et en ajoutant 0 ou 1.

$\frac{3}{5}$$\frac{2}{5}$

$$\begin{align*} \hbox{encode}(s, A_0) &= 5s + 0\\ \hbox{encode}(s, A_1) &= 5s + 1\\ \hbox{encode}(s, A_2) &= 5s + 2\\ \hbox{encode}(s, B_0) &= 5s + 3\\ \hbox{encode}(s, B_1) &= 5s + 4 \end{align*}$$

$s' = \left\lfloor \frac{s}{3} \right\rfloor$$i = s \bmod 3$$\hbox{encode}(s', A_i)$

$\frac{p}{q}$

La raison pour laquelle il s'agit d'une famille de méthodes de codage est que ce que nous avons vu ici n'est pas pratique en soi; il a besoin de quelques modifications pour faire face au fait que vous n'avez probablement pas d'entiers de précision infinie pour manipuler efficacement la variable d'état, et il existe différentes façons d'y parvenir. Le codage arithmétique, bien sûr, a un problème similaire avec la précision de son état.

Les variantes pratiques incluent rANS (le "r" signifie "ratio") et tANS ("piloté par table").

Le SNA présente quelques avantages intéressants par rapport au codage arithmétique, à la fois pratique et théorique:

• Contrairement au codage arithmétique, "l'état" est un seul mot, plutôt qu'une paire de mots.
• Non seulement cela, mais un codeur ANS et son décodeur correspondant ont des états identiques et leurs opérations sont complètement symétriques. Cela soulève des possibilités intéressantes, telles que vous pouvez entrelacer différents flux de symboles codés et tout se synchronise parfaitement.
• Les implémentations pratiques doivent, bien sûr, «produire» des informations au fur et à mesure, et pas seulement les collecter dans un grand entier pour les écrire à la fin. Cependant, la taille de la "sortie" peut être configurée en échange d'une perte de compression (généralement modeste). Ainsi, lorsque les codeurs arithmétiques doivent produire un bit à la fois, ANS peut produire un octet ou un nybble à la fois. Cela vous donne un compromis direct entre la vitesse et la compression.
• Il semble être à peu près aussi rapide sur le matériel de génération actuelle que le codage arithmétique binaire, et donc compétitif avec le codage Huffman. Cela le rend beaucoup plus rapide que le codage arithmétique en gros alphabet et ses variantes (par exemple le codage par plage).
• Il semble être sans brevet.

Je ne pense pas que je vais recommencer le codage arithmétique.

À titre d'exemple simple, si vous aviez trois symboles avec une probabilité 1/3 chacun, votre encodage Huffman optimal utiliserait les trois symboles 0, 10 et 11 avec une moyenne de 5 / 3e bits.

Il y a 243 symboles créés en concaténant 5 des symboles originaux, chacun avec une probabilité 1/243. Ce qui est beaucoup plus proche du 1/256. L'encodage Huffman optimal encodera 13 de ces groupes en 7 bits et 230 groupes en 8 bits, pour une moyenne de 7,9465 bits par groupe ou 1,5893 bits par symbole d'origine, contre 1,6667 bits pour le codage Huffman original, le codage arithmétique prenant 1,5850 morceaux.

Donc, en théorie, vous pouvez simplement combiner deux symboles chacun en un seul symbole plus grand, ou trois symboles chacun en un seul symbole plus grand, et utiliser le codage Hufman pour les combinaisons.