Elle est marrante la balise Coboy
Test :
[cowboy] La première chose à faire, avant de débuter la compression, est de compter
le nombre d'occurences de chaque caractère. Jusque là, ce n'est pas trop dur à
faire ! Une fois cette opération terminée, on est en mesure de voir quels
sont les caractères qui apparaissent le plus souvent, mais également ceux qui
apparaissent le moins souvent. Ce sont ces derniers qui vont nous intéresser
en premier lieu. C'est en effet à partir d'eux que l'on va commencer la
construction de notre arbre binaire, dans lequel le caractère apparaissant le
plus grand nombre de fois dans le fichier sera proche du tronc, et celui qui
apparait le moins de fois sera au plus loin dans les branches.
Je prends un exemple :
Supposons que l'on veuille compresser le texte suivant : "AAAABBBCCD"
Pour les nombres d'occurences, on obtient donc :
A -> 4 fois
B -> 3 fois
C -> 2 fois
D -> 1 fois
L'arbre binaire est alors le suivant :
TRONC
/
A /
B /
C D
En fait, c'est relativement simple ici car on utilise un alphabet de seulement
4 caractères. Mais en pratique on travaille avec des octets, c'est-à-dire avec
un maximum de 256 caractères !!! Je dis maximum, car certains caractères
n'appaitront peut être pas : On ne va donc pas s'en occuper, logique ! C'est
là que le tableau d'occurences, que nous avons calculé précédemment, prend
toute son utilité : On recherche les 2 caractères les moins fréquents (ceux
ayant le plus faible nombre d'occurences, donc). On additionne leur nombre
d'occurences afin de créer un nouveau "caractère" (ce n'en est pas un, en
fait. Il s'agit plutôt d'un noeud, en rapport bien sûr avec notre arbre).
Par exemple, compressons la phrase "LES MATHS AVEC HUFFMAN" (22 octets) :
' ' (espace) -> 3 fois
A -> 3 fois
C -> 1 fois
E -> 2 fois
F -> 2 fois
H -> 2 fois
L -> 1 fois
M -> 2 fois
N -> 1 fois
S -> 2 fois
T -> 1 fois
U -> 1 fois
V -> 1 fois
On va donc construire le premier étage. Mais avant, je tiens à préciser que,
normalement, un arbre se construit du bas vers le haut (voir l'arbre d'exemple
donné plus haut). Pour des raisons évidentes de place (sur l'écran !), je le
construit de droite à gauche. Dans le fond, ça ne change bien évidemment rien.
Le voici :
' ' -> 3
A -> 3
E -> 2
F -> 2
H -> 2
M -> 2
S -> 2
C -> 1 -+
¦ 2
L -> 1 -+
N -> 1 -+
¦ 2
T -> 1 -+
U -> 1 -+
¦ 2
V -> 1 -+
Par la même méthode vient le second étage :
' ' -> 3
A -> 3
E -> 2--+
¦ 4
F -> 2--+
H -> 2--+
¦ 4
M -> 2--+
S -> 2-------+
C -> 1--+ ¦ 4
¦ 2--+
L -> 1--+
N -> 1--+
¦ 2--+
T -> 1--+ ¦
¦ 4
U -> 1--+ ¦
¦ 2--+
V -> 1--+
Et ainsi de suite... Au final, en réarrangeant un petit peu l'ordre afin de
rendre la lecture plus claire, on obtient l'arbre suivant :
A -> 3------+
E -> 2--+ +-7--------+
+-4-+ ¦
F -> 2--+ ¦
¦
N -> 1--+ +-14--+
+-2--+ ¦ ¦
T -> 1--+ ¦ ¦ ¦
+-4--+ ¦ ¦
U -> 1--+ ¦ ¦ ¦ ¦
+-2--+ +-7--+ +-22 (c'est le tronc)
V -> 1--+ ¦ ¦
' ' -> 3------------+ ¦
H -> 2--+ ¦
+-4-------+ ¦
M -> 2--+ ¦ ¦
+-8--------+
S -> 2-------+ ¦
C -> 1--+ +-4--+
+-2--+
L -> 1--+
Bon, c'est bien beau tout ça, mais qu'est ce qu'on en fait de cet arbre ?!
Et bien on va dire que vers le haut ce sera un bit 1, et vers le bas un bit 0,
mais l'inverse fonctionne tout aussi bien. C'est une convention que l'on va
imposer, et conserver pour la décompression. On réécrit maintenant l'arbre
avec les bits, et on vire les statistiques (les nombres d'occurences), car ils
ne servent plus à rien désormais :
A -----+1
E --+1 +--------+1
+--+0 ¦
F --+0 ¦
¦
N --+1 +---+1
+---+1 ¦ ¦
T --+0 ¦ ¦ ¦
+---+1 ¦ ¦
U --+1 ¦ ¦ ¦ ¦
+---+0 +---+0 +- tronc
V --+0 ¦ ¦
' '----------+0 ¦
H --+1 ¦
+-------+1 ¦
M --+0 ¦ ¦
+-------+0
S ------+1 ¦
C --+1 +---+0
+---+0
L --+0
Comme pous pouvez le remarquer si vous avez compris comment on va utiliser cet
arbre (si vous ne voyez pas, lisez la suite et vous comprendrez !), aucun
caractère ne sera codé sur un seul bit :( C'est assez logique, car il n'y a
pas de caractère présent en grande majorité. Si par exemple on avait eu en
plus la lettre "z" présente 15 fois, vous voyez bien d'après l'arbre qu'il
aurait été tout prêt du tronc... Non, vous ne voyez pas ? Bon, ok on n'a qu'à
comparer 2 exemples :
CAS N°1 : ¦CAS N°2 :
--------- ¦---------
¦
A -> 50 fois ¦ A -> 2 fois
B -> 2 fois ¦ B -> 3 fois
C -> 3 fois ¦ C -> 4 fois
D -> 7 fois ¦ D -> 5 fois
¦
TRONC ¦ TRONC
/ ¦ /
A / ¦ / /
D / ¦ A B C D
B C ¦
Dans le premier cas, une seule branche relie "A" au tronc, 2 pour le "D" et 3
pour le "B" et le "C". Dans le second cas, tous les caractères sont reliés au
tronc par 2 branches... Gardez à l'esprit que plus on est proche du tronc,
moins on aura besoin de bits pour coder ce caractère.[/cowboy][nosmile]
ggrrrrrrrrrrrr !
, sinon 
(
