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^[1]; 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^[2]) 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^[3]. 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, et 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 fatales lors de la décompression. Des techniques existent pour pallier ce problème^[4].

Articles connexes

Bibliographie

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

Références

↑ Mark Nelson (trad. Hervé Soulard), La Compression de données : textes, images et sons, Dunod, 1993, 421 p. (ISBN 2-10-001681-4)
↑ « COMPRESSION - compression arithmétique » (consulté le 17 janvier 2015)
↑ « La compression de données - Le codage Arithmétique » (consulté le 17 janvier 2015)
↑ « Chapitre 1 : Le codage arithmétique » (consulté le 18 janvier 2015)

Portail de l’informatique

[1] Mark Nelson (trad. Hervé Soulard), La Compression de données : textes, images et sons, Dunod, 1993, 421 p. (ISBN 2-10-001681-4)

[2] « COMPRESSION - compression arithmétique » (consulté le 17 janvier 2015)

[3] « La compression de données - Le codage Arithmétique » (consulté le 17 janvier 2015)

[4] « Chapitre 1 : Le codage arithmétique » (consulté le 18 janvier 2015)

[1]

[2]

[3]

[4]