Codage arithmétique

Le codage arithmétique est un codage entropique utilisé en compression de données sans perte. Il permet une meilleure compression que le codage de Huffman, sauf lorsque tous les poids pour les feuilles/nœuds/racines de l'arbre de Huffman sont des puissances de 2, auquel cas les deux méthodes sont équivalentes.^{[réf. nécessaire]}

Malgré cet avantage, il ne fut que peu utilisé car son implémentation était trop complexe; des méthodes d'implémentation furent finalement trouvées alors que la compression par dictionnaire (bien meilleure que le codage de Huffman ou arithmétique^{[réf. nécessaire]}) commençait à devenir populaire.

On notera cependant son utilisation dans la compression des images aux normes JPEG 2000 et JBIG2.

Principe

Le codage arithmétique (au même titre que le Codage de Huffman) est un code à longueur variable, c'est-à-dire qu'un symbole de taille fixe (en bits) sera codé par un nombre variable de bits, de préférence inférieur ou égal à sa taille originale. On ne modifie donc pas la densité de symboles mais leur codage afin de réduire l'espace qu'ils occupent.

Ce qui différencie le codage arithmétique des autres codages sources est qu'il code le message par morceaux (théoriquement il peut coder un message entier de taille quelconque mais dans la pratique on ne peut coder que des morceaux d'une quinzaine de symboles en moyenne) et représente chacun de ces morceaux par un nombre $n$ (flottant) là où Huffman code chaque symbole par un code précis. Le problème qui en résulte pour le codage Huffman est qu'un caractère ayant une probabilité très forte d'apparition sera codé sur au moins un bit. Par exemple, si on cherche à coder un caractère représenté à 90 %, la taille optimale du code du caractère sera de 0,15 bit alors que Huffman codera ce symbole sur au moins 1 bit, soit 6 fois trop. C'est cette lacune que le codage arithmétique comble grâce à un algorithme proche du codage par intervalle.

Propriétés

Compression

La compression demande un tableau statistique (se rapprochant au maximum des statistiques observables sur le fichier $Fn$ contenant $n$ symboles à compresser) qui comprend :

• La totalité des symboles que l'on rencontre dans le message à compresser.
• Les probabilités $p$ de rencontrer le symbole $s$ dans le message.
• L'intervalle $[0;1[$ découpé en intervalles proportionnel à la probabilité $p$ que le symbole $s$ apparaisse dans le message (ex: si $s$ a 50 % de chance d'apparaître, son intervalle sera de longueur 0,5).

Le but va maintenant être d'appliquer une suite d'opérations à un intervalle donné (couramment c'est l'intervalle $[0;1[$ qui est choisi) afin de modifier ses bornes à chaque ajout d'un symbole $s$ et de restreindre au maximum le nombre de possibilités du nombre de sortie.

Voici les opérations à effectuer lors de l'ajout d'un symbole $s$:

• On enregistre la différence entre la borne supérieure (BS) et la borne inférieure (BI). On notera cette valeur BB.
• La BS prend la valeur suivante : BI + BB * (BS_du_symbole_s)
• La BI prend la valeur suivante : BI + BB * (BI_du_symbole_s)

Après l'ajout du premier symbole, l'intervalle aura les mêmes limites que l'intervalle du symbole ajouté, puis chaque ajout fera converger ses limites. Lorsqu'un nombre suffisant de symboles auront été stockés, l’algorithme renverra un nombre flottant se trouvant dans cet intervalle. Ce nombre représente la totalité du fichier d'entrée.

On remarque qu'une suite de symboles ayant une forte probabilité d'apparaitre fera converger l'intervalle bien plus lentement que si on a affaire à une suite de symbole apparaissant peu. Un nombre dans un intervalle ayant convergé lentement sera donc codé avec moins de chiffres significatifs qu'un nombre dans un intervalle extrêmement précis, d'où le gain.

Il faut aussi penser à ajouter un symbole qui servira uniquement à indiquer la fin du fichier, sans quoi l’algorithme de décompression risque de tourner indéfiniment, produisant le fichier suivi d'une suite pseudo-aléatoire de bits.

Décompression

Pour décompresser un fichier (représenté par un nombre $n$), il faut utiliser la même table qui a été utilisée pour la compression puis effectuer les étapes suivantes jusqu'à la fin du fichier :

• Observer dans l'intervalle de quel symbole $s$ se trouve le nombre, ajouter $s$ au fichier décompressé et garder en mémoire la probabilité $p$ de $s$ ainsi que sa BI.
• $n$ prend la valeur $n=(n-BI)/p$.

Une fois le marqueur de fin atteint, l'algorithme s'arrête et le fichier est considéré comme décompressé.

Exemple

Compression

On appliquera ici l’algorithme de compression arithmétique sur le texte « WIKI ». On obtient dès lors le tableau suivant :

Lettre	Probabilité	Intervalle
W	1/4	[0;0,25[
I	2/4	[0,25;0,75[
K	1/4	[0,75;1[

Par convention on initialise l'algorithme avec une borne inférieure valant 0 et une borne supérieure valant 1. Il ne reste plus qu'à appliquer la suite d'opérations vue précédemment à chaque ajout d'un caractère.

Caractère ajouté	Borne inférieure	Borne supérieure
	0	1
W	0	0,25
I	0,0625	0,1875
K	0,15625	0,1875
I	0,1640625	0,1796875

Donc, tout nombre compris dans intervalle $[0,1640625;0,1796875[$ sera une version compressée de la chaîne de caractères « WIKI ». Le nombre 0,17 étant compris dans cet intervalle, il peut convenir pour représenter « WIKI » compressé. À l'inverse, 0,16 ou 0,1796875 n'étant pas dans l'intervalle, ils ne conviendront pas et entraineront des erreurs lors du décodage.

Décompression

Supposons que l'on reçoive le message compressé 0,17, voici comment il serait décodé :

(On utilise évidemment le même tableau que précédemment pour connaitre les intervalles de chaque lettre et leurs probabilités d'apparition).

Code compressé	Intervalle	Lettre correspondante	Texte récupéré
0,17	[0;0,25[	W	W
0,68	[0,25;0,75[	I	WI
0,86	[0,75;1[	K	WIK
0,44	[0,25;0,75[	I	WIKI

On retrouve donc la bonne chaine de caractères auparavant compressée.

Faiblesses

Cette méthode de compression rencontre deux principaux défauts qui sont maintenant connus et corrigés :

• Le premier est le fait d'utiliser un tableau de statistiques fixe, entrainant les mêmes problèmes que pour le codage Huffman, c'est-à-dire que la compression d'un fichier avec des statistiques atypiques (des symboles devant être peu présents se retrouvent avec une forte probabilité d'apparition) sera plus volumineux après compression qu'avant. La solution la plus efficace est donc, là aussi, d'utiliser un tableau adaptatif dont toutes les fréquences débutent égales puis, à chaque rencontre d'un symbole, dont les statistiques sont mises à jour et les intervalles adaptés.

• Le second problème majeur est qu'en terme informatique les nombres à virgule sont plus complexes à manipuler, mais peuvent produire des erreurs d’arrondi (dû au nombre fini de chiffres après la virgule que peut supporter un ordinateur) qui pourront s'avérer fatals lors de la décompression. Pour pallier ce problème, il est possible d'initialiser l'intervalle de départ par une borne inférieure valant 00000... et une borne supérieure valant 99999... Les calculs sont ensuite les mêmes que pour des nombres à virgule mais sur des nombres entiers. Un nouveau problème peut néanmoins apparaitre lorsque les deux bornes deviennent trop proches, par exemple : $[6999...;7000...[$. Cet intervalle ne contient en effet aucune valeur entière et aucun ajout de nouveaux symboles ne le modifiera. Lorsque l'on en arrive à ce point, il faut soit arrêter l’algorithme avant soit, si les premiers chiffres n'ont une différence entre eux que de 1 et que le chiffre suivant vaut 9 pour la borne inférieure et 0 pour celle supérieure, supprimer ces premiers chiffres et décaler les chiffres suivants vers la gauche. Les derniers chiffres vaudront alors 0 pour la borne inférieure et 9 pour la borne supérieure, permettant de trouver un nouveau nombre dans cet intervalle.

Articles connexes

• Codage entropique
• Compression de données
• Entropie de Shannon

Bibliographie

• (en) David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 (ISBN 0-521-64298-1) [détail des éditions]