L'ALGORITHME DE HUFFMAN

Dans sa forme statique, la méthode de construction de l'arbre de Huffman
 s'exprime de la manière suivante :

INITIALISATION :

1 - Classer les octets à compresser par ordre décroissant de fréquence
 d'apparition dans les données initiales.
2 - Pour chaque octet, former un noeud X tel que POIDS(X) = la fréquence
 d'apparition de l'octet.

CONSTRUCTION DE L'ARBRE :

TANT QUE tous les noeuds ne sont pas reliés :
3 - Soit X et Y deux noeuds ayant les poids les plus bas
 (en résolvant les égalités de manière arbitraire).
4 - Relier X et Y en créant un noeud Z tel que
 POIDS(Z) = POIDS(X) + POIDS(Y).
5 - Affecter à l'une des branches Z-X et Z-Y le label '0'
 et à l'autre le label '1' (l'ordre n'a pas d'importance).
FIN du TANT QUE.

DETERMINATION DES CODES :

6 - Pour chaque octet des données initiales, le code de Huffman est constitué
 par la suite des bits portés par les branches entre la racine de l'arbre et
 l'octet en question.

Exemple détaillé : compression du texte "SATISFAISANT" par la méthode de
 Huffman statique.

Détermination des fréquences et initialisation de l'arbre :

 3 3 2 2   1         1
 S A T I S F A I S A N T

Première itération : on relie les deux noeuds ayant les poids les plus bas
                       2
                       --
                     +1  0+
                     :    :
 3    3    2    2    1    1
 S    A    T    I    F    N

Deuxième itération : idem
                   4
                  ----
                +1    0+
                :      2
                :      --
                     +1  0+
                :    :    :
 3    3    2    2    1    1
 S    A    T    I    F    N

Troisième itération : on continue de même
                   4
                  ----
                + 1  0 +
         5      :      2
        --      :      --
      +1  0+    :    +1  0+
      :    :    :    :    :
 3    3    2    2    1    1
 S    A    T    I    F    N

Pour le quatrième passage, il faut modifier la position de la branche portant
 la lettre 'S' afin de la rendre contiguë au noeud de poids 4 auquel elle
 sera reliée :
               7
            -------
           +  1 0  +
           :       :
           :       4
           :     ------
           :    + 1  0 +
    5      :    :      2
    --     :    :      --
 +1  0+    :    :    +1  0+
 :    :    :    :    :    :
 3    2    3    2    1    1
 A    T    S    I    F    N

Cinquième et dernière itération : l'arbre de Huffman est complet, il ne reste
 plus qu'à déterminer les codes correspondant à chaque lettre du texte à
 compresser.
        12
     ----------
    +   1  0   +
    :          :
    :          7
    :       -------
    :      +  1 0  +
    :      :       :
    :      :       4
    :      :     ------
    :      :    + 1  0 +
    5      :    :      2
    --     :    :      --
 +1  0+    :    :    +1  0+
 :    :    :    :    :    :
 3    2    3    2    1    1
 A    T    S    I    F    N

Code:
 A    T    S    I    F    N
 11   10   01  001  0001 0000

Le texte compressé sera donc :
 011110001010001110010111000010

Il occupe 30 bits, alors que la représentation ASCII correspondante prenait
 12 x 8 soit 96 bits.
Il faudrait cependant rajouter aux 30 bits ci-dessus la place nécessaire au
 stockage de l'arbre de Huffman généré.
Notons qu'il n'y a pas de séparateur entre les codes.
En effet, la décompression se fait en passant de la racine de l'arbre et en
 suivant le chemin indiqué le long des branches par les bits du texte
 compressé.
Dès qu'il arrive à une branche, le décompresseur émet l'octet correspondant
 et repart à la racine de l'arbre.
Chaque préfixe étant unique, aucune ambiguïté ne peut survenir.