COMPRESSION - code arithmétique

 

Introduction au Code Arithmétique à virgule flottante

Cet algorithme ne code pas les fichiers caractère par caractère mais par chaînes de caractères, plus ou moins longues suivant la capacité de la machine à coder des réels plus ou moins grands. Cette algorithme est tres performant. Si un caractère apparaît avec une probabilité de 90%, la taille optimale du code serait de 0.15 bit. En comparaison, en utilisant un algorithme du type Huffman, on coderait sûrement ce symbole sur 1 bit, soit 6 fois plus.

L’algorithme du code Arithmétique peut se decomposer en plusieurs étapes:

  • Etape 1 : L’initialisation: Lc = 0  ; Hc = 1
  • Etape 2 : Déterminer les longueurs des sous intervalles liés aux symboles
  • Etape 3 : Passer au codage sur le prochain symbole sk
  • Etape 4 : Déterminer, pour le sous-intervalle considéré, le raffinement en sous intervalles
  • Répéter les étapes 2, 3, et 4 jusqu’à obtenir le code de la séquence entière

Présentation du Code Arithmétique à virgule flottante

Le codage arithmétique permet, à partir de la probabilité d’apparition des symboles d’une source de créer un seul mot-code qui soit associé à la source.

Le code associé à une séquence de symboles est un nombre réel de l’intervalle [0, 1[. Ce code est construit par subdivisions récursives d’intervalles. A chaque étape, un intervalle est subdivisé en sous-intervalle en fonction de la probabilité de chaque symbole. On sélectionne le sous intervalles correspondant au symbole lu. On obtient, en définitive, un sous-intervalle [Lsk, Hsk [  de l’intervalle précédent [Lsk-1, Hsk-1 [ , tel que tout nombre réel Lsk appartenant à cet intervalle représente la séquence à coder.

Soit une source S = {s1, s2 …, sN} avec pk = P(sk)

[Lsk, Hsk[ est l’intervalle « assigné » au symbole sk avec: Hsk- Lsk = pk

Pour coder la séquence S = {s1, …, sN} d’une source pouvant délivrer N symboles et munie des probabilités suivantes, P{sk} = pk, l’algorithme utilise les étapes suivantes :

  • Étape 1 :

On initialise un premier intervalle avec deux bornes : la borne inférieure Lc = 0 et la borne supérieure Hc = 1 (correspondant à la probabilité de choisir un premier symbole sα1 parmi tous les symboles sk de la source).

La taille de cet intervalle est donc définie par : dim = Hc – Lc = 1.

  • Étape 2 :

Cet intervalle est partitionné en N sous-intervalles [Lsk, Hsk [ en fonction des probabilités initiales de chaque symbole sk de la source. La longueur ( Hsk - Lsk ) de ces sous intervalles est donnée par : Lsk - Hsk = pk, on a donc

  • Étape 3 :

On choisit le sous-intervalle correspondant au prochain symbole sk qui apparaît dans la séquence. On redéfinit alors l’intervalle initial [Lc, Hc[. La taille de l’intervalle initiale est donc réduit.

  • Étape 4 :

Cet intervalle est subdivisé à nouveau, selon le même procédé que celui utilisé dans l’étape 2.

  • Étape 5 :

Les étapes 2, 3, et 4 sont répétées jusqu’à obtenir le mot-code représentant la séquence complète des symboles sources.

Exemple de code Arithmétique

Nous prenons la chaîne de caractère suivante : "l'encodage"

Avec cette exemple nous obtenons le tableau de probabilités suivants :


Ce qui nous donne les codes suivants :


Décodage du code Aritmétique

La dernière borne inférieure code de maniére unique notre chaîne. Notre code étant compris entre 0,6 et 0,7 on déduit que la première lettre est le 'l'. Pour le décodage, on prend le symbole correspondant à l'intervalle auquel appartient notre code, on le soustrait à la limite basse, et on divise par l'intervalle pour avoir le code suivant.


Conclusion

Cet algorithme est limité au codage de chaînes relativement courtes. En effet, la précision des ordinateurs (et autres matériels utilisant cette compression) a une limite. La compression devra être arrêtée avant d’atteindre la limite de résolution des machines (soit en moyenne pour une quinzaine de symbole).