PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
Un arbre PATRICIA est lié à unTrie.Le problème avec les Tries est que lorsque l’ensemble des clés est clairsemé,i.c’est-à-dire lorsque les clés réelles forment un petit sous-ensemble de l’ensemble des clés potentielles,comme c’est très souvent le cas,beaucoup (la plupart) des nœuds internes du Trie n’ont qu’un seul descendant.Cela entraîne une grande complexité spatiale du Trie.
Un Trie utilise chaque partie (bit, caractère, …) de la clé,à tour de rôle, pour déterminer quel sous-arbre sélectionner.Un arbre PATRICIA nomme plutôt (en stockant sa position dans le nœud)quel élément de la clé sera ensuite utilisé pour déterminer la ramification.Cela supprime la nécessité de tout nœud avec un seul descendant:
L’index de PATRICIA diffère de la structure de tri binaire de Fredkin en ce que l’index n’enregistre que les vraies branches;lorsqu’une phrase n’a qu’une seule extension droite appropriée, elle n’est pas enregistrée dans l’index.Ce fait réduit le nombre de lignes d’index à seulement deux fois le nombre de départs, et le rend indépendant de la longueur des phrases stockées.
– Morrison 1968 pp520.
Il est plus facile de créer un arbre PATRICIA pour les clés (chaînes de caractères) sur un alphabet de taille deux : {a,b}, ou {0,1}.Cependant, les chaînes de caractères sur un alphabet de plus de deux éléments,par ex. ascii, peuvent être traitées comme des chaînes de caractères sur un alphabet de deux éléments en prenant les bits dans chaque caractère de l’alphabet le plus grand.
L’exemple suivant montre la croissance d’un arbre PATRICIA sous une séquence d’insertions :
C
o
m
p
u
t
e
r
–
S
c
i
e
n
c
e
empty -- initial state
12345 -- number character positionsinsert ababb -- the key
----> ababb
insert ababa; la recherche se termine à ababb~=ababa;la 1ère différence est en position 5, donc…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba ; n’a pas de position #5;peut sauter des positions clés mais doit tester dans l’ordre, donc….
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba ; search ends at ababb~=aaabba;can skip key positions but must test in order, so…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab ; ab est aussi un préfixe de ababa et ababb;doit avoir la capacité de se terminer à un nœud intermédiaire, comme avec Tries.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Le traitement d’une clé, telle que `ab’, qui est le préfixe d’une autre clé, par exemple `ababa’, peut être traité de différentes manières. Un caractère de terminaison réel, ou notionnel, souvent dénoté `$’ (ou `\0′ en C et ses apparentés)peut être considéré comme un troisième caractère de l’alphabet, mais seulement autorisé à apparaître à la fin des clés.Cette légère complication ne se pose pas dans le cas particulier où toutes les clés ont la même longueur.
Notes
- D. R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968.
Originally presented PATRICIA as an index for searchingin marked-up text. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, pp 109, 1984.
Contenant un beau codage direct des algorithmesPATRICIA, et de beaucoup d’autres.Ce livre est une grande ressource. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Stocke des éléments (ou des pointeurs vers des éléments)dans des nœuds internes `fork’. - Voir pour la recherche de chaînes de caractères etc..
.