3.4 Modélisations par des structures arborescentes
113
(a)
(b)
(c)
Fig. 3.37 De haut en bas : (a) un trie binaire contenant 14 clés ; (b) le même trie après
compression des chemins filaires (comme dans un Patricia) ; (c) le LC-trie (level compression
trie) compresse les sous arbres complets (entourés en pointillés dans (b) pour les sous-arbres de
hauteur supérieure ou égale à 2). À chaque nœud peuvent être associés deux champs : le champ
skip indique le nombre de bits qui ne sont pas à examiner car nous sommes sur un chemin filaire ;
le champ branch indique la hauteur du sous-arbre complet (et donc le nombre de bits à regrouper
pour trouver le nœud fils lors d’une recherche). Ces champs ne sont pas mentionnées sur la figure
(c) lorsque leurs valeurs sont toutes deux nulles
garantir de pouvoir décoder un mot du code dès sa lecture – nous parlons alors de
code instantané. C’est aussi la propriété nécessaire pour construire un trie.
Le terme de compression est employé lorsque nous assignons aux symboles les
plus fréquents les mots les plus courts. Le but est d’obtenir un codage du texte (dans
l’alphabet de sortie, par exemple binaire) qui soit le plus court possible.
L’algorithme le plus célèbre pour réaliser cette tâche est l’algorithme de Huffman. Cet algorithme construit un trie binaire par une démarche de bas en haut
(« bottom-up » en anglais), en considérant au début une forêt d’arbres binaires dont
113
(a)
(b)
(c)
Fig. 3.37 De haut en bas : (a) un trie binaire contenant 14 clés ; (b) le même trie après
compression des chemins filaires (comme dans un Patricia) ; (c) le LC-trie (level compression
trie) compresse les sous arbres complets (entourés en pointillés dans (b) pour les sous-arbres de
hauteur supérieure ou égale à 2). À chaque nœud peuvent être associés deux champs : le champ
skip indique le nombre de bits qui ne sont pas à examiner car nous sommes sur un chemin filaire ;
le champ branch indique la hauteur du sous-arbre complet (et donc le nombre de bits à regrouper
pour trouver le nœud fils lors d’une recherche). Ces champs ne sont pas mentionnées sur la figure
(c) lorsque leurs valeurs sont toutes deux nulles
garantir de pouvoir décoder un mot du code dès sa lecture – nous parlons alors de
code instantané. C’est aussi la propriété nécessaire pour construire un trie.
Le terme de compression est employé lorsque nous assignons aux symboles les
plus fréquents les mots les plus courts. Le but est d’obtenir un codage du texte (dans
l’alphabet de sortie, par exemple binaire) qui soit le plus court possible.
L’algorithme le plus célèbre pour réaliser cette tâche est l’algorithme de Huffman. Cet algorithme construit un trie binaire par une démarche de bas en haut
(« bottom-up » en anglais), en considérant au début une forêt d’arbres binaires dont