PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
PATRICIA-puu on sukua Trie:lle.Trie:n ongelmana on se, että kun avainjoukko on harva,i.ts. kun todelliset avaimet muodostavat pienen osajoukon potentiaalisten avainten joukosta,kuten hyvin usein tapahtuu,monilla (useimmilla) Trie:n sisäisillä solmuilla on vain yksi jälkeläinen.Tämä aiheuttaa Trie:lle suuren tilakompleksisuuden.
Trie käyttää avaimen jokaista osaa (bittiä, merkkiä, …) vuorollaan määrittämään, mikä alipuu valitaan.PATRICIA-puu sen sijaan nimeää (tallentamalla sen sijainnin solmuun)mikä avaimen elementti seuraavaksi käytetään haarautumisen määrittämiseen.Tämä poistaa tarpeen solmuille, joilla on vain yksi jälkeläinen:
PATRICIAn indeksi eroaa Fredkinin Binary Trie -rakenteesta siinä, että indeksi tallentaa vain todelliset haarautumat;jos lauseella on vain yksi oikea oikea jatke, sitä ei tallenneta indeksiin.Tämä vähentää indeksirivien määrän vain kaksinkertaiseksi aloitusten määrään nähden ja tekee siitä riippumattoman tallennettujen lausekkeiden pituudesta.
– Morrison 1968 s. 520.
Patricia-puu on helpointa luoda avaimille (merkkijonoille), joiden aakkoset ovat kooltaan kaksi: {a,b} tai {0,1}.Kuitenkin merkkijonot, joiden aakkosissa on useampia kuin kaksi alkiota, kuten esim. ascii, voidaan käsitellä kuin merkkijonoja kahden aakkoston yli ottamalla bitit kunkin suuremman aakkoston merkin sisällä.
Seuraavassa esimerkissä esitetään PATRICIA-puun kasvu lisäyssarjan alla:
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; haku päättyy kohtaan ababb~=ababa;1. ero on kohdassa 5, joten…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; ei ole sijaa #5;voi ohittaa avainpaikkoja, mutta on testattava järjestyksessä, joten….
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; haku päättyy kohtaan ababb~=aaabba;voi ohittaa avainpaikkoja, mutta on testattava järjestyksessä, joten…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab on myös etuliite ababa ja ababbabb;pitää pystyä lopettamaan välisolmuun, kuten Triesissä.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Käsitellä avainta, kuten `ab’, joka on toisen avaimen, esim. `ababa’, etuliite,voidaan käsitellä eri tavoin. Todellinen tai kuvitteellinen lopetusmerkki, jota usein merkitään `$’ (tai `\0′ C:ssä ja sen sukulaisissa)voidaan pitää kolmantena merkkinä aakkosissa, mutta sen sallitaan esiintyä vain avainten lopussa.Tämä pieni komplikaatio ei synny erikoistapauksessa, jossa kaikki avaimet ovat samanpituisia.
Huomautuksia
- 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 searching in marked-up text. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, pp 109, 1984.
Sisältää mukavan suoraviivaisen koodauksen PATRICIA-algoritmeista ja monista muista.Tämä kirja on loistava lähde. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Säilyttää elementtejä (tai osoittimia elementteihin)sisäisten ”haarukkasolmujen” sisällä. - Vrt. merkkijonohaku jne..