PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
Een PATRICIA-boom is verwant aan eenTrie.Het probleem met Tries is dat wanneer de verzameling sleutels schaars is, d.w.z.d.w.z. wanneer de werkelijke sleutels een kleine deelverzameling vormen van de verzameling potentiële sleutels, zoals zeer vaak het geval is, veel (de meeste) interne knooppunten in de Trie slechts één nakomeling hebben.Dit veroorzaakt dat de Trie een hoge ruimte-complexiteit heeft.
Een Trie gebruikt elk onderdeel (bit, karakter, …) van de sleutel, om te bepalen welke subtree geselecteerd moet worden. Een PATRICIA boom nomineert in plaats daarvan (door zijn positie in de node op te slaan) welk element van de sleutel vervolgens gebruikt zal worden om de vertakking te bepalen.Hierdoor zijn er geen knooppunten meer nodig met slechts één nakomeling:
PATRICIA’s index verschilt van Fredkin’s Binary Trie structuur in die zin dat de index alleen ware vertakkingen registreert; wanneer een woordgroep slechts één juiste rechter vertakking heeft, wordt deze niet in de index opgenomen.Dit feit vermindert het aantal index rijen tot slechts tweemaal het aantal startpunten, en maakt het onafhankelijk van de lengte van de opgeslagen zinnen.
– Morrison 1968 pp520.
Het is het gemakkelijkst om een PATRICIA boom te maken voor sleutels (strings) over een alfabet van twee grootte: {a,b}, of {0,1}.Echter, strings over een alfabet van meer dan twee elementen, b.v. ascii, kunnen worden behandeld als reeksen over een alfabet van twee door de bits binnen elk teken van het grotere alfabet te nemen.
Het volgende voorbeeld toont de groei van een PATRICIA-boom onder een opeenvolging van invoegingen:
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; zoekactie eindigt bij ababb~=ababa;1e verschil is op positie 5, dus…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; heeft geen positie #5;kan sleutelposities overslaan maar moet in volgorde testen, dus…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; zoeken eindigt op ababb~=aaabba;kan sleutelposities overslaan maar moet op volgorde testen, dus…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab is ook een voorvoegsel van ababa en ababb;moet kunnen eindigen op een tussenliggend knooppunt, zoals bij Tries.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Het omgaan met een sleutel, zoals `ab’, die het voorvoegsel is van een andere sleutel, b.v. `ababa’, kan op verschillende manieren worden behandeld. Een werkelijk, of fictief, eindteken, vaak aangeduid met `$’ (of `0′ in C en zijn verwanten) kan worden beschouwd als een derde teken in het alfabet, maar mag alleen voorkomen aan het eind van sleutels. Deze kleine complicatie doet zich niet voor in het speciale geval dat alle sleutels dezelfde lengte hebben.
Noten
- D. R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968.
Oorspronkelijk gepresenteerd PATRICIA als een index voor het zoeken in gemarkeerde tekst. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, pp 109, 1984.
Bevat een mooie eenvoudige codering van dePATRICIA-algoritmen, en van vele andere.Dit boek is een geweldige bron. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Houdt elementen (of pointers naar elementen) vast binnen interne `fork’ nodes. - Zie voor string searching etc..