112
3 Arbres, algorithmes et données
3.4.8 Tables de routage IP
Un certain nombre d’auteurs se sont intéressés à l’implémentation efficace de tables
de routage pour Internet. Il s’agit, dans un nœud du réseau, de pouvoir décider
très rapidement de la prochaine étape sur le chemin d’un paquet dont on connaît
l’adresse finale. Cette prochaine étape est déterminée par un préfixe de l’adresse
finale, de longueur variable. D’un point de vue algorithmique, il s’agit de représenter
efficacement un dictionnaire de grande taille, et il n’est pas surprenant que des
variantes des structures digitales se soient révélées bien adaptées. Par exemple,
Nilsson et Karlsson ont proposé dans [195] une variante des arbres PATRICIA :
les LC-tries (pour level compression trie).
Un LC-trie sur n clés est obtenu à partir du trie classique construit sur ces n
clés, par la compression des chemins filiformes, combinée à une compression des
niveaux pleins de l’arbre et à leur remplacement par des nœuds d’arité 2 i (i étant
le nombre de niveaux sous la racine qui sont pleins) ; ce remplacement se fait de
manière récursive dans chaque sous-arbre (voir la figure 3.37).
Il est possible d’implémenter efficacement (sans mémoire auxiliaire « excessive ») ces arbres. De plus, les LC-tries ont le même nombre de feuilles que le trie
de départ (ce qui n’était pas le cas pour de précédentes tentatives de compression),
et la profondeur moyenne d’une feuille (i.e., le temps moyen d’accès à l’adresse
de la prochaine étape sur le paquet en cours de traitement) est d’ordre inférieur à
la profondeur dans un trie ou dans un arbre PATRICIA : suivant les modèles sur la
répartition initiale des clés, cette profondeur moyenne (qui est d’ordre log n pour
un trie ou un arbre PATRICIA) est d’ordre log ∗ n où log ∗ n est le logarithme itéré
(cf. section B.5.1) une fonction qui croît très lentement. L’analyse a été faite par
Devroye [60].
Le livre de Wu [253] expose en détails plusieurs structures de données apparentées à la structure de trie pour des problématiques de routage de paquets dans les
réseaux.
3.4.9 Compression de données
Nous présentons ici quelques exemples en compression de données (conservative)
où les structures arborescentes ont une grande importance.
Codes préfixes L’encodage de données (sur disque ou en mémoire) est une
opération usuelle qui fait le plus souvent appel à des codes dits de longueur variable.
L’idée, illustrée par la figure 3.38, est d’encoder chaque symbole représentant la
donnée sur un autre alphabet (le plus souvent binaire) sous la forme d’un mot [21].
Le plus souvent, cet encodage est réalisé sous la forme d’une structure d’arbre
digital où les symboles sont en correspondance avec les feuilles de l’arbre et les mots
du code correspondent aux marques des chemins partant de la racine et finissant aux
nœuds terminaux. Aucun mot du code ne peut être préfixe d’un autre si nous voulons
3 Arbres, algorithmes et données
3.4.8 Tables de routage IP
Un certain nombre d’auteurs se sont intéressés à l’implémentation efficace de tables
de routage pour Internet. Il s’agit, dans un nœud du réseau, de pouvoir décider
très rapidement de la prochaine étape sur le chemin d’un paquet dont on connaît
l’adresse finale. Cette prochaine étape est déterminée par un préfixe de l’adresse
finale, de longueur variable. D’un point de vue algorithmique, il s’agit de représenter
efficacement un dictionnaire de grande taille, et il n’est pas surprenant que des
variantes des structures digitales se soient révélées bien adaptées. Par exemple,
Nilsson et Karlsson ont proposé dans [195] une variante des arbres PATRICIA :
les LC-tries (pour level compression trie).
Un LC-trie sur n clés est obtenu à partir du trie classique construit sur ces n
clés, par la compression des chemins filiformes, combinée à une compression des
niveaux pleins de l’arbre et à leur remplacement par des nœuds d’arité 2 i (i étant
le nombre de niveaux sous la racine qui sont pleins) ; ce remplacement se fait de
manière récursive dans chaque sous-arbre (voir la figure 3.37).
Il est possible d’implémenter efficacement (sans mémoire auxiliaire « excessive ») ces arbres. De plus, les LC-tries ont le même nombre de feuilles que le trie
de départ (ce qui n’était pas le cas pour de précédentes tentatives de compression),
et la profondeur moyenne d’une feuille (i.e., le temps moyen d’accès à l’adresse
de la prochaine étape sur le paquet en cours de traitement) est d’ordre inférieur à
la profondeur dans un trie ou dans un arbre PATRICIA : suivant les modèles sur la
répartition initiale des clés, cette profondeur moyenne (qui est d’ordre log n pour
un trie ou un arbre PATRICIA) est d’ordre log ∗ n où log ∗ n est le logarithme itéré
(cf. section B.5.1) une fonction qui croît très lentement. L’analyse a été faite par
Devroye [60].
Le livre de Wu [253] expose en détails plusieurs structures de données apparentées à la structure de trie pour des problématiques de routage de paquets dans les
réseaux.
3.4.9 Compression de données
Nous présentons ici quelques exemples en compression de données (conservative)
où les structures arborescentes ont une grande importance.
Codes préfixes L’encodage de données (sur disque ou en mémoire) est une
opération usuelle qui fait le plus souvent appel à des codes dits de longueur variable.
L’idée, illustrée par la figure 3.38, est d’encoder chaque symbole représentant la
donnée sur un autre alphabet (le plus souvent binaire) sous la forme d’un mot [21].
Le plus souvent, cet encodage est réalisé sous la forme d’une structure d’arbre
digital où les symboles sont en correspondance avec les feuilles de l’arbre et les mots
du code correspondent aux marques des chemins partant de la racine et finissant aux
nœuds terminaux. Aucun mot du code ne peut être préfixe d’un autre si nous voulons