PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
Un arbore PATRICIA este înrudit cu unTrie.Problema cu Tries este că atunci când setul de chei este rarefiat,adică.adică atunci când cheile efective formează un subansamblu mic din setul de chei potențiale,așa cum se întâmplă foarte des,multe (majoritatea) nodurilor interne din Trie au doar un singur descendent.acest lucru face ca Trie să aibă o complexitate spațială ridicată.
Un Trie utilizează fiecare parte (bit, caracter, …) a cheii,pe rând, pentru a determina ce subarbore să selecteze.Un arbore PATRICIA în schimb nominalizează (prin stocarea poziției sale în nod)ce element al cheii va fi utilizat în continuare pentru a determina ramificarea.Acest lucru elimină necesitatea oricăror noduri cu un singur descendent:
Indexul PATRICIA diferă de structura Binary Trie a lui Fredkin prin faptul că indexul înregistrează doar ramurile adevărate;în cazul în care o frază are doar o singură extensie corectă la dreapta, aceasta nu este înregistrată în index.Acest fapt reduce numărul de rânduri ale indexului la doar de două ori numărul de porniri și îl face independent de lungimea frazelor memorate.
– Morrison 1968 pp520.
Este cel mai ușor să creezi un arbore PATRICIA pentru chei (șiruri de caractere) pe un alfabet de mărimea doi: {a,b}, sau {0,1}.Totuși, șirurile de caractere pe un alfabet cu mai mult de două elemente, de ex. ascii, pot fi tratate ca șiruri pe un alfabet de două elemente, luând biții din fiecare caracter al alfabetului mai mare.
Exemplul următor arată creșterea unui arbore PATRICIA sub o secvență de inserții:
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; căutarea se termină la ababb~=ababa;prima diferență este la poziția 5, deci…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; nu are poziția #5;poate sări peste pozițiile cheie, dar trebuie să testeze în ordine, deci…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; căutarea se termină la ababb~==aaabba;poate sări peste pozițiile cheie, dar trebuie să testeze în ordine, deci…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab este, de asemenea, un prefix al lui ababa și ababb;trebuie să aibă capacitatea de a se încheia la un nod intermediar, ca și în cazul încercărilor.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Tratarea unei chei, cum ar fi `ab’, care este prefixul unei alte chei, de exemplu `ababa’, poate fi tratată în diferite moduri. Un caracter de terminare real sau teoretic, adesea notat cu `$’ (sau `\0′ în C și înrudirile sale) poate fi considerat ca fiind al treilea caracter din alfabet, dar care poate apărea numai la sfârșitul cheilor.Această ușoară complicație nu apare în cazul special în care toate cheile au aceeași lungime.
Note
- D. R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968.
A prezentat inițial PATRICIA ca un index pentru căutarea în texte marcate. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, pp 109, 1984.
Conține o codificare frumoasă și directă a algoritmilorPATRICIA, precum și a multor altora.Această carte este o resursă excelentă. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Stochează elemente (sau pointeri la elemente)în interiorul nodurilor interne `fork’. - Vezi pentru căutarea de șiruri etc..
.