114
3 Arbres, algorithmes et données
Fig. 3.38 Trois tries binaires permettant permettant d’encoder les symboles a, b, c, d et r de
abracadabra. Le symbole a est codé par 11, 11011, 0 (respectivement de gauche à droite)
les éléments sont des nœuds externes correspondant aux symboles à coder. De plus,
chaque nœud contient un champ freq qui a pour valeur la fréquence du symbole.
La méthode est ici statique 28 car les fréquences sont supposées connues à l’avance.
Les deux nœuds de la forêt qui possèdent les fréquences les plus faibles sont ensuite
choisis (à fréquence égale le choix d’un nœud ou d’un autre n’a pas d’importance).
Un nouveau nœud interne dont les deux fils sont les deux nœuds choisis est construit.
Le champ freq de ce nœud prend comme valeur la somme des fréquences de ses
fils. Ceci fournit une nouvelle forêt ; le processus itératif s’arrête lorsque la forêt ne
contient plus qu’un seul arbre, qui est le trie de codage (voir la figure 3.39).
Les codes de Huffman sont des codes optimaux : connaissant les probabilités
des symboles, l’arbre de Huffman minimise la longueur moyenne du mot binaire
affectée à un symbole, qui n’est autre que la longueur de cheminement externe de
l’arbre, pondérée par les probabilités des symboles.
Compression à la Lempel et Ziv Les techniques de compression à la Lempel et
Ziv utilisent des méthodes à base de dictionnaires. C’est donc tout naturellement
que la structure de trie est centrale pour ce type de compression (voir l’article de
synthèse [18]).
Principe. Le compresseur comme le décompresseur maintiennent en parallèle un
dictionnaire. Cette méthode est donc dynamique et son principe se résume grâce au
schéma de la figure 3.40.
Au fur à mesure de la lecture du texte sont ajoutés au dictionnaire des mots
choisis. Pour les prochaines occurrences de ces mots, seules leurs références dans
le dictionnaire sont transmises.
Il existe de nombreuses variantes de l’algorithme de Lempel et Ziv. Le principe
général est dans un premier temps de découper le texte en segments. Chaque
nouveau segment est encodé à l’aide du dictionnaire et le dictionnaire est ensuite
mis à jour. C’est dans la stratégie de mise à jour du dictionnaire que se situe la
différence majeure entre les deux méthodes données par Lempel et Ziv nommées
28 Mais il existe bien sûr des variantes dynamiques effectuant des mises à jour au fur et à mesure
que le texte est lu.
3 Arbres, algorithmes et données
Fig. 3.38 Trois tries binaires permettant permettant d’encoder les symboles a, b, c, d et r de
abracadabra. Le symbole a est codé par 11, 11011, 0 (respectivement de gauche à droite)
les éléments sont des nœuds externes correspondant aux symboles à coder. De plus,
chaque nœud contient un champ freq qui a pour valeur la fréquence du symbole.
La méthode est ici statique 28 car les fréquences sont supposées connues à l’avance.
Les deux nœuds de la forêt qui possèdent les fréquences les plus faibles sont ensuite
choisis (à fréquence égale le choix d’un nœud ou d’un autre n’a pas d’importance).
Un nouveau nœud interne dont les deux fils sont les deux nœuds choisis est construit.
Le champ freq de ce nœud prend comme valeur la somme des fréquences de ses
fils. Ceci fournit une nouvelle forêt ; le processus itératif s’arrête lorsque la forêt ne
contient plus qu’un seul arbre, qui est le trie de codage (voir la figure 3.39).
Les codes de Huffman sont des codes optimaux : connaissant les probabilités
des symboles, l’arbre de Huffman minimise la longueur moyenne du mot binaire
affectée à un symbole, qui n’est autre que la longueur de cheminement externe de
l’arbre, pondérée par les probabilités des symboles.
Compression à la Lempel et Ziv Les techniques de compression à la Lempel et
Ziv utilisent des méthodes à base de dictionnaires. C’est donc tout naturellement
que la structure de trie est centrale pour ce type de compression (voir l’article de
synthèse [18]).
Principe. Le compresseur comme le décompresseur maintiennent en parallèle un
dictionnaire. Cette méthode est donc dynamique et son principe se résume grâce au
schéma de la figure 3.40.
Au fur à mesure de la lecture du texte sont ajoutés au dictionnaire des mots
choisis. Pour les prochaines occurrences de ces mots, seules leurs références dans
le dictionnaire sont transmises.
Il existe de nombreuses variantes de l’algorithme de Lempel et Ziv. Le principe
général est dans un premier temps de découper le texte en segments. Chaque
nouveau segment est encodé à l’aide du dictionnaire et le dictionnaire est ensuite
mis à jour. C’est dans la stratégie de mise à jour du dictionnaire que se situe la
différence majeure entre les deux méthodes données par Lempel et Ziv nommées
28 Mais il existe bien sûr des variantes dynamiques effectuant des mises à jour au fur et à mesure
que le texte est lu.