Codage arithmétique

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

• La totalité des ${\displaystyle s}$ symboles que l'on rencontre dans le message à compresser.
• Les probabilités ${\displaystyle p}$ de rencontrer le symbole ${\displaystyle s}$ dans le message.
• L'intervalle ${\displaystyle [0;1[}$ découpé en intervalles proportionnel à la probabilité ${\displaystyle p}$ que le symbole ${\displaystyle s}$ apparaisse dans le message (ex: si ${\displaystyle 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 ${\displaystyle [0;1[}$ qui est choisi) afin de modifier ses bornes à chaque ajout d'un symbole ${\displaystyle 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 ${\displaystyle 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.

Pour décompresser un fichier (représenté par un nombre ${\displaystyle 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 ${\displaystyle s}$ se trouve le nombre, ajouter ${\displaystyle s}$ au fichier décompressé et garder en mémoire la probabilité ${\displaystyle p}$ de ${\displaystyle s}$ ainsi que sa BI.
• ${\displaystyle n}$ prend la valeur ${\displaystyle 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é.

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

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.

Donc, tout nombre compris dans intervalle ${\displaystyle [0,1640625;0,1796875[}$ sera une version compressée de la chaîne 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.

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

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