PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
A PATRICIA tree is related to aTrie.The problem with Tries is that when the set of keys is sparse,i.Cioè quando le chiavi effettive formano un piccolo sottoinsieme dell’insieme delle chiavi potenziali, come è molto spesso il caso, molti (la maggior parte) dei nodi interni del Trie hanno solo un discendente, il che fa sì che il Trie abbia un’alta complessità spaziale.
Un Trie usa ogni parte (bit, carattere, …) della chiave, a turno, per determinare quale sottoalbero selezionare.Un albero PATRICIA invece nomina (memorizzando la sua posizione nel nodo) quale elemento della chiave sarà usato successivamente per determinare la ramificazione.Questo rimuove la necessità di qualsiasi nodo con un solo discendente:
L’indice di PATRICIA differisce dalla struttura Binary Trie di Fredkin in quanto l’indice registra solo le ramificazioni vere; quando una frase ha solo una corretta estensione destra, non viene registrata nell’indice.Questo fatto riduce il numero di righe dell’indice a solo il doppio del numero di inizi, e lo rende indipendente dalla lunghezza delle frasi memorizzate.
– Morrison 1968 pp520.
È più facile creare un albero PATRICIA per le chiavi (stringhe) su un alfabeto di dimensione due: {a,b}, o {0,1}.Tuttavia, le stringhe su un alfabeto di più di due elementi, per esempio ascii, possono essere trattate come stringhe su un alfabeto di due elementi prendendo i bit all’interno di ogni carattere dell’alfabeto più grande.
L’esempio seguente mostra la crescita di un albero PATRICIA sotto una sequenza di inserimenti:
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; la ricerca termina con ababb~=ababa; la prima differenza è alla posizione 5, quindi…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; non ha posizione #5; può saltare posizioni chiave ma deve testare in ordine, quindi…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; la ricerca finisce ad ababb~=aaabba; può saltare posizioni chiave ma deve testare in ordine, quindi…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab è anche un prefisso di ababa e ababb; deve avere la capacità di terminare in un nodo intermedio, come con Tries.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Il trattamento di una chiave, come `ab’, che è il prefisso di un’altra chiave, per esempio `ababa’, può essere gestito in vari modi. Un carattere finale reale o fittizio, spesso indicato come `$’ (o `0′ in C e nei suoi parenti) può essere considerato come un terzo carattere dell’alfabeto, ma può essere presente solo alla fine delle chiavi. Questa piccola complicazione non si presenta nel caso speciale in cui tutte le chiavi abbiano la stessa lunghezza.
Note
- D. R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968.
Originariamente presentato PATRICIA come un indice per la ricerca nel testo marcato. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, pp 109, 1984.
Contiene una bella codifica diretta degli algoritmiPATRICIA, e di molti altri.Questo libro è una grande risorsa. - R. Sedgewick.Algoritmi in C. Addison-Wesley, edn 1, pp253, 1990.
Immagazzina elementi (o puntatori a elementi) all’interno di nodi interni `fork’. - Si veda per la ricerca di stringhe ecc.