PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
A PATRICIA fa rokon a Trie-vel.A Trie-vel az a probléma, hogy ha a kulcsok halmaza ritka,i.azaz amikor a tényleges kulcsok a potenciális kulcsok halmazának egy kis részhalmazát alkotják,ahogy ez nagyon gyakran előfordul,a Trie sok (legtöbb) belső csomópontjának csak egy leszármazottja van.ez a Trie nagy térkomplexitását okozza.
Egy Trie a kulcs minden egyes részét (bit, karakter, …) felváltva használja annak meghatározására, hogy melyik részfát válassza ki.A PATRICIA fa ehelyett kijelöli (a csomópontban elfoglalt pozíciójának tárolásával)hogy a kulcs melyik elemét fogja legközelebb használni az elágazás meghatározására.Így nincs szükség olyan csomópontokra, amelyeknek csak egy leszármazottja van:
A PATRICIA indexe abban különbözik a Fredkin-féle bináris trie struktúrától, hogy azindex csak a valódi elágazásokat rögzíti;ahol egy kifejezésnek csak egy megfelelő jobboldali kiterjesztése van, az nem kerül be az indexbe.Ez a tény az index sorainak számát csak a kezdetek számának kétszeresére csökkenti, és függetlenné teszi a tárolt mondatok hosszától.
– Morrison 1968 pp520.
A PATRICIA fát a legegyszerűbb a két elemű ábécé feletti kulcsok (karakterláncok) számára létrehozni: {a,b}, vagy {0,1}.Azonban a kettőnél több elemű ábécé feletti karakterláncok, pl.: {a,b}, vagy {0,1}. ascii, úgy kezelhetők, mint a kételemű ábécé feletti karakterláncok, a nagyobb ábécé minden egyes karakterén belüli bitek figyelembevételével.
A következő példa egy PATRICIA-fa növekedését mutatja be beszúrások sorozata alatt:
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; a keresés ababb~=ababa-nál ér véget;az 1. különbség az 5. pozícióban van, tehát…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; nincs az 5. pozícióban;kihagyhatja a kulcspozíciókat, de sorrendben kell tesztelnie, tehát…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; a keresés ababb~=aaabba-nál ér véget;kihagyhatja a kulcspozíciókat, de sorrendben kell tesztelnie, így…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab az ababa és ababb előtagja is;képesnek kell lennie arra, hogy egy köztes csomópontnál befejezze a keresést, mint a Tries esetében.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Az olyan kulcs, mint például az `ab’, amely egy másik kulcs, például az `ababa’ előtagja, többféleképpen kezelhető. Egy tényleges vagy fiktív záró karakter, gyakran `$’ (vagy `\0′ a C-ben és rokonaiban)tekinthető az ábécé harmadik karakterének, de csak a kulcsok végén fordulhat elő.Ez a kis bonyodalom nem merül fel abban a speciális esetben, amikor minden kulcs azonos hosszúságú.
Jegyzetek
- 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.
Tartalmazza aPATRICIA algoritmusok és sok más algoritmus szép, egyszerű kódolását.Ez a könyv nagyszerű forrás. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Elemeket (vagy elemekre mutató mutatókat)tárol belső “villa” csomópontokban. - Szöveges keresés stb.