Codage arithmétique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

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) commençait à devenir populaire.

On notera son utilisation notable dans la compression des images aux normes JPEG 2000.

Principe[modifier | modifier le code]

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 encodage 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[modifier | modifier le code]

Compression[modifier | modifier le code]

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 s symboles que l'on peut rencontrer.
  • Les probabilités p de rencontrer le symbole s.
  • L'intervalle [0;1[ découpé en intervalles proportionnel à la probabilité p que le symbole s apparaisse (ex: si s à 50% de chance d'apparaitre, son intervalle ferra 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) affin 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 et représentant 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 seul nombre fini pourra donc stocker un plus grand nombre de caractères probables que de caractères "rares", 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[modifier | modifier le code]

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[modifier | modifier le code]

Compression[modifier | modifier le code]

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 chaine de caractère "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[modifier | modifier le code]

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

(On utilise évidement 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 corespondante 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[modifier | modifier le code]

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 misent à 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 palier 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 vaux 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[4].

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Références[modifier | modifier le code]

  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/01/2015)
  3. « La compression de données - Le codage Arithmétique » (consulté le 17/01/2015)
  4. « Chapitre 1 : Le codage arithmétique » (consulté le 18/01/2015)