Deux grandes familles de codeurs sans perte

Il s'agit d'expliquer simplement et de manière pratique quel est le principe des codeurs que l'on rencontre le plus souvent. Lors de nos recherches, nous en avons rencontré deux types: les codeurs statistiques, et les codeurs arithmétiques.

Codages statistiques

Ces méthodes s'appuient sur le fait que les données en entrée peuvent être compressées en utilisant un nombre variable de bits pour encoder les différents symboles. Les symboles les plus fréquents sont ainsi codés sur un nombre réduits de bits; les économies peuvent atteindre des taux de 50% voire plus (le pire cas étant le cas équiprobable...). En pratique, il faut également stocker une table de symboles.

Ce genre de codage peut s'effectuer statiquement (auquel cas deux passages sont nécessaires, ce qui ralentit le processus), ou bien dynamiquement (le codage devient adaptatif).

Le codage de HUFFMAN statique est celui qui a été choisi pour l'implémentation originelle de JPEG. Il est intégralement expliqué dans le chapître associé. Il a ensuite été amélioré, étant remplacé successivement par une version dynamique (décrite ci-après) puis un codage arithmétique (cf prochain paragraphe).

Voici l'algorithme de HUFFMAN dynamique:

// Table d'occurences
int NbOccurences[256];
// Actuel arbre -> table de correspondance des symboles
Arbre A;

// On lit le premier caractère
C=LireCaractere(Entree);

// Tant que la chaine n'est pas finie, on calcule...
TantQue(C!=eof) {
  // Si ce caractere est connu, on renvoie son code (stocké dans l'arbre)
  Si (NbOccurences[C]!=0) {
    EcrireCode(C, A);
  } Sinon {
    // Sinon, on insère un code symbolique 'phi' suivi du code du caractere
    EcrireCode('phi', A);
    // indique la presence d'un nouveau caractere supplementaire
    NbOccurences[phi]+=1;
    EcrireCode(C, A);
  }
  NbOccurrence[C]+=1;
  // A chaque iteration on recalcule l'arbre
  MettreAJour(A);
  C=LireCaractere();
}

On remarque qu'à l'étape n, l'arbre est identique à celui qu'on aurait construit en utilisant HUFFMAN statique avec le message contenant les n premiers symboles du message complet. Le symbole 'phi' (que nous notons dorénavant $\phi$) est un caractère symbolique signifiant l'initialisation (il est donc codé avec un code prédéfini, par exemple '0'). À chaque fois que l'on rencontre un nouveau caractère, on insère le code de $\phi$ suivi des n bits du nouveau caractère. Celui-ci est ensuite inséré dans l'arbre de HUFFMAN.

Pour le décodage, c'est l'algorithme suivant qui est utilisé:

// Table d'occurences
int NbOccurences[256];
// Actuel arbre -> table de correspondance des symboles
Arbre A;

// On lit le premier caractère
C=LireSuiteCode(Entree);

// Tant que la chaine n'est pas finie, on calcule...
// Nota Bene: a l'initialisation, le seul code connu est 'phi'
TantQue(C!=eof) {
  // On utilise la propriété du préfixe: on retire de C un code unique B
  // represente par les k premiers bits de C
  B=CodeAssocie(C);
  // Ce caractere est forcement connu, on renvoie son code (stocke dans l'arbre)
  D=Decoder(B, A);
  Si (D=='phi') {
    // On lit (et ecrit) les n bits associes au nouveau caractere
    // L'index sur C avance donc de n bits
    LireEcrire(C);
  } Sinon {
    NbOccurences[phi]+=1;
    Ecrire(D);
  }
  NbOccurrence[C]+=1;
  // A chaque iteration on recalcule l'arbre
  MettreAJour(A);
  C=LireSuiteCode();
}

Au début du décodage, le seul symbole connu est $\phi$! On lira donc son code, suivi du caractère qui suit que l'on insère alors dans l'arbre, et ainsi de suite. Le point-clé tient dans le fait que les arbres construits pour la compression et la décompression sont les mêmes.

Cette méthode dynamique est plus rapide et donne souvent de meilleurs résultats (à cause du stockage de l'arbre qui n'existe pas puisqu'il est construit au fur et à mesure). Certaines évolutions existent, et sont utilisées notamment dans JPEG2000, notamment le codage par contexte qui tient compte du fait qu'un document peut être hétérogène, et que la compression moyenne du fichier sera moins efficace que la compression séparée de chacune des zones homogènes.

Codages arithmétiques

Le codage de HUFFMAN a un défaut: si on considère un code possédant un symbole apparaissant avec une probabilité 0.9, le codage de HUFFMAN se limitera à 1 bit par symbole sans tenir compte de la quantité d'information contenu dans celui-ci. Le codage arithmétique permet de s'affranchir de cette limite et de coder les symboles sur un nombre non-entier de bits. Ceci parait à première vue surprenant; considérons donc un exemple pratique: la chaîne "compressee"

Symbole	Occurrences	Probabilité
c	1	$0,1$
e	3	$0,3$
m	1	$0,1$
o	1	$0,1$
p	1	$0,1$
r	1	$0,1$
s	2	$0,2$

NOTA BENE: le nombre de caractères de l'exemple ici est $10$, ce qui simplifie grandement les manipulations numériques de l'exemple puisque les nombres auront un nombre fini de décimales! Bien sûr, ce procédé s'applique à des chaînes de longueur quelconque car il repose sur des intervalles et non sur les représentations exactes de nombres.

On décide maintenant d'associer à chaque symbole 'd' un domaine dans l'espace des probabilités, le but étant d'associer un symbole à un domaine. La table d'associations sera transmise avec le message encodé (comme dans le cas de HUFFMAN statique):

Symbole	Probabilité	Domaine
c	$0,1$	$0,0 \leq \texttt{d} < 0,1$
e	$0,3$	$0,1 \leq \texttt{d} < 0,4$
o	$0,1$	$0,4 \leq \texttt{d} < 0,5$
m	$0,1$	$0,5 \leq \texttt{d} < 0,6$
p	$0,1$	$0,6 \leq \texttt{d} < 0,7$
r	$0,1$	$0,7 \leq \texttt{d} < 0,8$
s	$0,2$	$0,8 \leq \texttt{d} < 1,0$

L'algorithme servant à encoder est le suivant:

// Tableau contenant les bornes inferieures des intervalles
//  calcules ci-avant
Borne_Inf[];

// Idem pour la borne sup
Borne_Sup[];

// Initialisation
Inf=0.0;
Sup=1.0;

c = lireCaractere();

TantQue (c!= EOF) {
  Sup = Inf + (Sup - Inf) * Borne_Sup[c];
  Inf = Inf + (Sup - Inf) * Borne_Inf[c];
  c = lireCaractere();
}

Par exemple, le message original ("compresse") est encodé comme suit:

Symbole	Borne Inférieure	Borne Supérieure
	0	$1$
c	$0,0$	$0,1$
o	$0,04$	$0,05$
m	$0,045$	$0,046$
p	$0,0456$	$0,0457$
r	$0,04567$	$0,04568$
e	$0,045671$	$0,045674$
s	$0,0456718$	$0,0456720$
s	$0,0456726$	$0,0456728$
e	$0,04567262$	$0,04567268$
e	$0,045672626$	$0,045672644$

Ainsi $0,045672626$ est la représentation arithmétique du message "compressee". En pratique, n'importe quel nombre compris entre $0,045672626$ et $0,045672644$ représente le bon message.

Le décodage est quant à lui tout aussi simple: sachant que le message encodé est entre $0,0$ et $0,1$, la première lettre est un c. On soustrait ensuite la borne inférieure ($0,0$ pour c) et on divise par la probabilité ($0,1$ pour c); on obtient ainsi $0,45672626$ qui est compris entre $0,4$ et $0,5$ donc la prochaine lettre sera un o, etc.

Il est à noter que ce codage ne s'effectue pas en pratique sur des flottants, car pour des messages très longs, ce codage nécessiterait une précisison allant au-delà de celle de la machine. La convention adoptée note zéro 0x0000... et un 0xFFFF..., ces deux quantités n'étant pas limités en longueur.

Il existe également une version dynamique de ce codage, nommée Codage Arithmétique Adaptatif:

Figure: Schéma fonctionnel du codeur arithmétique adaptatif

c'est cette version, appliquée de manière astucieuse, qui équipe le nouveau format JPEG2000. Plus d'informations sont disponibles au chapître associé.