PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
Ett PATRICIA-träd är besläktat med en Trie.Problemet med Trie är att när mängden nycklar är sparsam,dvs.dvs. när de faktiska nycklarna utgör en liten delmängd av mängden potentiella nycklar, vilket mycket ofta är fallet, har många (de flesta) av de interna noderna i Trie endast en efterföljare, vilket gör att Trie har en hög utrymmeskomplexitet.
En Trie använder varje del (bit, tecken, …) av nyckeln i tur och ordning för att bestämma vilket underträd som skall väljas.Ett PATRICIA-träd nominerar istället (genom att lagra dess position i noden)vilket element av nyckeln som nästa gång kommer att användas för att bestämma förgreningen.Detta eliminerar behovet av noder med endast en nedstigare:
PATRICIAs index skiljer sig från Fredkins binära trestegsstruktur genom att indexet endast registrerar sanna förgreningar; om en fras endast har en korrekt högerförlängning registreras den inte i indexet.Detta faktum minskar antalet indexrader till endast dubbelt så många som antalet starter och gör det oberoende av längden på de lagrade fraserna.
– Morrison 1968 pp520.
Det är lättast att skapa ett PATRICIA-träd för nycklar (strängar) över ett alfabet av två storlekar: {a,b}, eller {0,1}.Strängar över ett alfabet med mer än två element, t.ex. ascii, kan behandlas som strängar över ett alfabet med två element genom att ta bitar inom varje tecken i det större alfabetet.
Följande exempel visar tillväxten av ett PATRICIA-träd under en sekvens av infogningar:
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ökningen slutar vid ababb~=ababa;den första skillnaden finns i position 5, så…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; har ingen position #5;kan hoppa över nyckelpositioner men måste testa i ordning, så…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; sökning slutar vid ababb~=aaabba;kan hoppa över nyckelpositioner men måste testa i ordning, så…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab är också ett prefix för ababa och ababb;måste ha möjlighet att avsluta vid en mellanliggande nod, som med Tries.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Hantering av en nyckel, t.ex. `ab’, som är prefix för en annan nyckel, t.ex. `ababa’, kan hanteras på olika sätt. Ett faktiskt, eller fiktivt, avslutande tecken, ofta betecknat `$’ (eller `\0′ i C och dess släktingar)kan betraktas som ett tredje tecken i alfabetet, men får bara förekomma i slutet av nycklar.Denna lilla komplikation uppstår inte i det speciella fallet att alla nycklar har samma längd.
Anteckningar
- D. R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968.
Originellt presenterades PATRICIA som ett index för sökning i markerad text. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, pp 109, 1984.
Innehåller en trevlig och enkel kodning av PATRICIA-algoritmerna, och av många andra.Denna bok är en stor resurs. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Lagrar element (eller pekare till element)inom interna `fork’-noder. - Se för strängsökning etc..