Compression

La première série d'exercices vous a présenté une première méthode simple permettant de tenir compte de la présence de répétitions d'un même code dans un fichier.

Le principe présenté ici a le même objectif : tenir compte de la répétition de symboles pour réduire. Mais le principe est différent : on tient compte ici de la proportion de chaque symbole relativement aux autres symboles du fichier.

Le principe exposé est souvent utilisé dans les algorithmes de compression (voir par exemple ici le descriptif bref du format bzip2).

Le principe exposé ici est du à David Huffman.

Un codage.

A l'aide de l'arbre ci-dessous, on peut définir un code pour chacune des lettres apparaissant comme feuille de l'arbre (on appelle feuille d'un arbre tout sommet sans descendant).

arbre1

Le principe de codage est le suivant :

  • On part de la racine (le sommet du haut).
  • Lorsqu'on prend une arête gauche, on marque 0.
  • Lorsqu'on prend une arête droite, on marque 1.

E est par exemple codé 010 dans l'arbre précédent.

Seules les feuilles de l'arbre sont codées (ce sont les seuls sommets contenant une lettre).

  1. Coder le mot SAGE.
  2. Décoder 00111011

SAGE : 11111001101010.

00111011 : ISN.

Code préfixe.

Dans l'exercice précédent, on a associé les codes suivants aux lettres S, A, G, E :

SAGE
11111001101010

Décidons ici l'association suivante :

SAGE
010001

Expliquer en quoi ce nouveau codage des lettres ne convient pas pour coder le mot SAGE ? Quelle différence avec le code précédent ?

SAGE serait codé comme suit avec ce nouveau codage des lettres : 010001.

On a alors un problème au décryptage. Le 01 de départ est-il S suivi de A ou E ?
Les mots SA et E sont codés de la même façon. Ce système de codage ne permet donc pas de retrouver le mot initial.

De façon générale, on appelle code préfixe un code pour lequel aucun mot n'a pour préfixe un autre mot.

Par exemple, le code

SAGE
010001

n'est pas préfixe puisque 0 est un mot du code et est préfixe du mot 01 autre mot du code.

Avec un code préfixe, on pourra toujours décrypter sans ambiguïté : deux mots donnés n'auront jamais le même code.

On se persuadera aisément que le code utilisé dans le premier exercice est préfixe : aucune lettre n'a un code constituant un préfixe du code d'une autre lettre. En effet, si un mot m1 du code était préfixe d'un autre mot m2 du code, cela signifierait que le chemin dans l'arbre correspondant à m1 serait le début du chemin menant à la lettre codée par m2. Mais, dans ce cas, la lettre correspondant à m1 ne serait pas une feuille de l'arbre -- ce qui est absurde (seules les feuilles de l'arbre contiennent une lettre dans le codage à la Huffman présenté dans l'exercice 1).

Code de Huffman.

L'objectif de cet exercice est de découvrir le fonctionnement du codage de Huffman pour la compression d'un texte.

  1. On commence par relever les fréquences de chaque symbole dans le texte à compresser. Nous supposerons ici disposer d'un fichier dans lequel se trouvent uniquement les lettres a, b, c, d, e, i suivant les fréquences suivantes :
    abcdei
    0.250.050.060.100.350.19
  2. On ordonne ensuite par ordre croissant des fréquences et on crée un noeud racine pour chaque symbole.
  3. On crée ensuite un noeud, père des deux noeuds de pondération les plus faibles. Ce nouveau noeud est pondéré par la somme des fréquences associées à ses deux fils.
    On réordonne les racines des arbres :
  4. On recommence le travail sur les racines :
  5. On continue jusqu'à obtenir un seul arbre.
  1. Terminer la construction de l'arbre.
  2. Donner le code du mot baida avec cet arbre.
  3. On suppose que le texte initial était codé en ASCII (1 octet par caractère). Quel est le gain en codant ce même texte avec le code de Huffman correspondant à l'arbre construit ?
  4. Lorsqu'on transmet un texte codé par cette méthode, on doit également transmettre le dictionnaire de décryptage.
    • Expliquer ce que cela peut signifier.
    • Quelles conséquences sur le taux de compression ?

Finalisation de l'arbre

L'étape suivante :

puis :

et :

Code du mot baida

0110100001010

Taux de compression

En ascii, pour 100 caractères, on utilise 100*8=800 bits.

Caractèreabcdei
fréquence0.250.050.060.100.350.19
nombre de bits244322

Avec le code obtenu par l'arbre, pour 100 caractères, les fréquences annoncées étant respectées, on utilise 232 bits (car : 2*0.25+4*0.05+4*0.06+3*0.10+2*0.35+2*0.19=2.32).

Soit un gain de (800-232)/800= 71 %.

Si l'on parle en terme de quotient de compression : 800/232 ≅ 3.45.

Avec un dictionnaire

Le code utilisé pour chaque lettre dépend du texte compressé puisque les fréquences dans le texte à compresser interviennent.

Pour pouvoir retrouver le texte initial, il faut donc également transmettre la correspondance entre les symboles et leurs codes.

Cela alourdit bien entendu un peu le fichier. Si le texte initial est très court, le gain pourra donc être faible, voire négatif. Par contre pour un texte conséquent (par exemple un roman), l'ajout du dictionnaire ne pénalise que très peu la performance.