PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
Et PATRICIA-træ er beslægtet med etTrie.Problemet med Tries er, at når mængden af nøgler er sparsom,dvs.dvs. når de faktiske nøgler udgør en lille delmængde af mængden af potentielle nøgler,som det meget ofte er tilfældet,har mange (de fleste) af de interne knuder i Trie kun én efterkommer.Dette medfører,at Trie har en høj rumkompleksitet.
En Trie bruger hver del (bit, tegn, …) af nøglen,efter tur,til at bestemme,hvilket undertræ der skal vælges.Et PATRICIA-træ nominerer i stedet (ved at lagre dets position i knuden)hvilket element af nøglen dernæst vil blive brugt til at bestemme forgreningen.Dette fjerner behovet for noder med kun én efterkommer:
PATRICIA’s indeks adskiller sig fra Fredkins binære trie-struktur ved at indekset kun registrerer sande forgreninger; hvis en sætning kun har én korrekt højre forlængelse, registreres den ikke i indekset.Denne kendsgerning reducerer antallet af indeksrækker til kun det dobbelte af antallet af starter, og gør det uafhængigt af længden af de lagrede sætninger.
– Morrison 1968 pp520.
Det er lettest at oprette et PATRICIA-træ for nøgler (strenge) over et alfabet af størrelse to: {a,b}, eller {0,1}.Imidlertid kan strenge over et alfabet med mere end to elementer,f.eks. ascii, kan behandles som strenge over et alfabet på to elementer, ved at man tager bitsene inden for hvert tegn i det større alfabet.
Det følgende eksempel viser væksten af et PATRICIA-træ under en sekvens af indsættelser:
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; søgningen slutter ved ababb~=ababa;1. forskel er på position 5, så…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; har ingen position #5;kan springe nøglepositioner over, men skal teste i rækkefølge, så…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; søgning slutter ved ababb~=aaabba;kan springe nøglepositioner over, men skal teste i rækkefølge, så …
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab er også et præfiks af ababa og ababb;skal have mulighed for at afslutte ved et mellemliggende knudepunkt, som med Tries.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Håndtering af en nøgle, som f.eks. `ab’, der er præfiks af en anden nøgle, f.eks. `ababa’, kan håndteres på forskellige måder. Et faktisk eller fiktivt afsluttende tegn, ofte betegnet `$’ (eller `\0′ i C og dets slægtninge)kan betragtes som et tredje tegn i alfabetet, men må kun forekomme i enderne af nøgler.Denne lille komplikation opstår ikke i det særlige tilfælde, at alle nøgler har samme længde.
Noter
- D. R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968.
Originalt blev PATRICIA præsenteret som et indeks til søgning i udemærket tekst. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, pp 109, 1984.
Indeholder en dejlig enkel kodning af PATRICIA-algoritmerne og af mange andre.Denne bog er en fantastisk ressource. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Lagerer elementer (eller pointers til elementer)inden for interne `fork’-knuder. - Se for stringsøgning osv..