PATRICIA – praktický algoritmus pro získávání informací zakódovaných v alfanumerickém kódu,D.R.Morrison (1968).
Strom PATRICIA je příbuzný sTriem.Problémem Trie je, že pokud je množina klíčů řídká,tj.tj. když skutečné klíče tvoří malou podmnožinu množiny potenciálních klíčů,což je velmi častý případ,má mnoho (většina) vnitřních uzlů Trie pouze jednoho potomka. to způsobuje, že Trie má vysokou prostorovou složitost.
Trie používá každou část (bit, znak, …) klíče,postupně určuje, který podstrom má být vybrán. strom PATRICIA místo toho nominuje (uložením jeho pozice v uzlu)který prvek klíče bude dále použit pro určení větvení.Tím odpadá potřeba jakýchkoli uzlů s pouze jedním potomkem:
Index PATRICIA se od Fredkinovy struktury binárních trí liší tím, že index zaznamenává pouze pravé větve;pokud má věta pouze jedno správné pravé rozšíření, není v indexu zaznamenána.Tato skutečnost snižuje počet řádků indexu na pouhý dvojnásobek počtu začátků a činí jej nezávislým na délce uložených frází.
– Morrison 1968 str520.
Nejjednodušší je vytvořit strom PATRICIA pro klíče (řetězce) nad abecedou o velikosti dvou: {a,b} nebo {0,1}.Avšak řetězce nad abecedou o více než dvou prvcích,např. ascii, lze považovat za řetězce nad abecedou o dvou prvcích, pokud vezmeme bity uvnitř každého znaku větší abecedy.
Následující příklad ukazuje růst stromu PATRICIApodle posloupnosti vložení:
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; hledání končí na ababb~=ababa;1. rozdíl je na pozici 5, takže…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; nemá pozici #5;může přeskočit klíčové pozice, ale musí testovat v pořadí, takže…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; hledání končí na ababb~=aaabba;může přeskočit klíčové pozice, ale musí testovat v pořadí, takže…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab je také prefixem ababa a ababb;musí mít možnost ukončit hledání v mezilehlém uzlu, stejně jako u Tries.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
S klíčem, jako je `ab‘, který je prefixem jiného klíče, např. `ababa‘,lze pracovat různými způsoby. Skutečný nebo fiktivní koncový znak, často označovaný jako `$‘ (nebo `\0′ v jazyce C a jeho příbuzných), lze považovat za třetí znak abecedy, který se však smí vyskytovat pouze na konci klíčů.Tato drobná komplikace nevzniká ve zvláštním případě, kdy mají všechny klíče stejnou délku.
Poznámky
- D. R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968.
Původně představil PATRICIA jako index pro vyhledávánív označeném textu. - G. H. Gonnet. Handbook of Algorithms and Data Structures. addison-Wesley, International Computer Series, str. 109, 1984.
Obsahuje pěkné přímočaré kódování algoritmůPATRICIA a mnoha dalších. tato kniha je skvělým zdrojem informací. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Ukládá prvky (nebo ukazatele na prvky)v rámci vnitřních uzlů `fork‘. - Vyhledávání v řetězcích atd.
.