3.2 Recherche de clés
75
et nous avons trouvé la place où elle devrait être insérée : comme premier enfant du
nœud contenant la clé X (6) .
Remarquons que chaque comparaison de la clé cherchée avec la clé contenue
dans un nœud de l’arbre nécessite une comparaison sur chacune des coordonnées.
L’analyse des performances de la recherche d’une clé dans un arbre quadrant fait
l’objet de la section 8.2.
3.2.3 Structures digitales et dictionnaires
Les structures digitales sont centrales en informatique dès lors que les objets à traiter
sont représentés par des séquences de symboles (par exemple des séquences de
bits, d’octets ou encore de mots-machines), i.e., des mots sur un alphabet, variable
suivant la situation à modéliser. Il s’agit ici de représenter un ensemble de clés,
de manière à implémenter efficacement les opérations de recherche, insertion et
suppression, ou bien les opérations ensemblistes d’union ou intersection, et plus
globalement le traitement de chaînes de caractères. Ces structures reproduisent un
principe utilisé par exemple dans les dictionnaires ou les répertoires téléphoniques :
les mots sont regroupés selon leur première lettre, ce qui permet un accès rapide
(grâce à un onglet par exemple). Ce mécanisme peut être poursuivi récursivement
jusqu’à séparer les mots les uns des autres, et nous aboutissons à la structure de trie
définie en section 1.2.7.
Les structures digitales se retrouvent aussi dans les algorithmes qui proposent la
complétion d’un mot dans un éditeur de texte ou de courrier ; elles sont en général
pondérées pour proposer de préférence les mots les plus utilisés. D’autres exemples
d’utilisation se rencontrent en bio-informatique, ou sont liés à des questions de
compression d’image. Dans de tels cas, ce sont souvent des variantes telles que les
arbres suffixes (une implémentation efficace en espace du trie construit sur tous les
suffixes d’un même mot) ou les arbres PATRICIA (tries où les branches filiformes
ont été compactées) qui sont utilisées. Nous renvoyons à l’annexe A.5 pour les
principaux algorithmes sur la structure de trie.
Trie
Les tries ont été introduits en section 1.2.7 ; cf. la définition 1.41. Nous en
avons donné un exemple en figure 1.32. La recherche d’un mot dans un tel arbre
consiste en l’examen successif de ses lettres. Chaque lettre supplémentaire conduit
à restreindre l’ensemble des mots qui partagent le même préfixe. Dans l’arbre,
cela correspond à cheminer le long d’une branche. Les opérations d’insertion et
de suppression d’un mot peuvent être facilement implantées. La structure de trie est
donc particulièrement adaptée pour les applications de type dictionnaire, y compris
dans un contexte dynamique où l’ensemble des mots n’est pas « figé » mais peut
varier par insertions et suppressions successives de mots. Si nous considérons des
75
et nous avons trouvé la place où elle devrait être insérée : comme premier enfant du
nœud contenant la clé X (6) .
Remarquons que chaque comparaison de la clé cherchée avec la clé contenue
dans un nœud de l’arbre nécessite une comparaison sur chacune des coordonnées.
L’analyse des performances de la recherche d’une clé dans un arbre quadrant fait
l’objet de la section 8.2.
3.2.3 Structures digitales et dictionnaires
Les structures digitales sont centrales en informatique dès lors que les objets à traiter
sont représentés par des séquences de symboles (par exemple des séquences de
bits, d’octets ou encore de mots-machines), i.e., des mots sur un alphabet, variable
suivant la situation à modéliser. Il s’agit ici de représenter un ensemble de clés,
de manière à implémenter efficacement les opérations de recherche, insertion et
suppression, ou bien les opérations ensemblistes d’union ou intersection, et plus
globalement le traitement de chaînes de caractères. Ces structures reproduisent un
principe utilisé par exemple dans les dictionnaires ou les répertoires téléphoniques :
les mots sont regroupés selon leur première lettre, ce qui permet un accès rapide
(grâce à un onglet par exemple). Ce mécanisme peut être poursuivi récursivement
jusqu’à séparer les mots les uns des autres, et nous aboutissons à la structure de trie
définie en section 1.2.7.
Les structures digitales se retrouvent aussi dans les algorithmes qui proposent la
complétion d’un mot dans un éditeur de texte ou de courrier ; elles sont en général
pondérées pour proposer de préférence les mots les plus utilisés. D’autres exemples
d’utilisation se rencontrent en bio-informatique, ou sont liés à des questions de
compression d’image. Dans de tels cas, ce sont souvent des variantes telles que les
arbres suffixes (une implémentation efficace en espace du trie construit sur tous les
suffixes d’un même mot) ou les arbres PATRICIA (tries où les branches filiformes
ont été compactées) qui sont utilisées. Nous renvoyons à l’annexe A.5 pour les
principaux algorithmes sur la structure de trie.
Trie
Les tries ont été introduits en section 1.2.7 ; cf. la définition 1.41. Nous en
avons donné un exemple en figure 1.32. La recherche d’un mot dans un tel arbre
consiste en l’examen successif de ses lettres. Chaque lettre supplémentaire conduit
à restreindre l’ensemble des mots qui partagent le même préfixe. Dans l’arbre,
cela correspond à cheminer le long d’une branche. Les opérations d’insertion et
de suppression d’un mot peuvent être facilement implantées. La structure de trie est
donc particulièrement adaptée pour les applications de type dictionnaire, y compris
dans un contexte dynamique où l’ensemble des mots n’est pas « figé » mais peut
varier par insertions et suppressions successives de mots. Si nous considérons des