PATRICIA – Algoritmo Prático para Recuperar Informações Codificadas em Alfanumérico,D.R.Morrison (1968).
Uma árvore PATRICIA está relacionada a aTrie.e. quando as chaves reais formam um pequeno subconjunto do conjunto de chaves potenciais,como é muito frequentemente o caso,muitos (a maioria) dos nós internos do Trie têm apenas um descendente,o que faz com que o Trie tenha uma alta complexidade de espaço.
A Trie usa cada parte (bit, caracter, …) da chave, por sua vez, para determinar qual sub-árvore selecionar. Uma árvore PATRICIA em vez disso indica (armazenando sua posição no nó)qual elemento da chave será usado a seguir para determinar a ramificação.Isto remove a necessidade de qualquer nó com apenas um descendente:
PATRICIA’s index difere da estrutura Binary Trie de Fredkin em que o índice registra apenas ramos verdadeiros; onde uma frase tem apenas uma extensão correta, ela não é registrada no índice.Este facto reduz o número de linhas de índice para apenas o dobro do número de inícios, e torna-o independente do comprimento das frases armazenadas.
– Morrison 1968 pp520.
É mais fácil criar uma árvore PATRICIA forkeys (strings) sobre um alfabeto de tamanho dois: {a,b}, ou {0,1}. ascii, podem ser tratadas como cordas sobre um alfabeto de twoby tomando os bits dentro de cada caractere do alfabeto maior.
O exemplo a seguir mostra o crescimento de uma árvore PATRICIA por uma sequência de inserções:
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 pesquisa termina em ababb~=ababa; a 1ª diferença está na posição 5, portanto…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
inserir ba; não tem posição #5;pode saltar posições chave mas deve testar em ordem, por isso…
--------> . . . . . . ba . . . . . .ababa ababb
insira aaabba; a busca termina em ababb~=aabba;pode pular posições chave mas deve testar em ordem, então…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
inserir ab; ab é também um prefixo de ababa e ababb;deve ter a capacidade de terminar em um nó intermediário, como em Tries.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Tratar com uma chave, como `ab’, que é o prefixo de outra chave, e.g. `ababa’, pode ser tratado de várias maneiras. Um caractere terminal real, ou nocional, muitas vezes denominado `$’ (ou `\0′ em C e seus parentes) pode ser considerado como um terceiro caractere no alfabeto, mas só pode ocorrer nas extremidades das chaves. Esta pequena complicação não surge no caso especial de todas as chaves terem o mesmo comprimento.
Notas
- D. R. Morrison.PATRICIA – Algoritmo Prático para Recuperar Informações Codificadas em Alfanumérico.Jrnl. do ACM, 15(4) pp514-534, Out 1968.
Originalmente apresentou a PATRICIA como um índice para busca em texto marcado. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, pp 109, 1984.
Contém uma codificação simples dos algoritmos da PATRICIA, e de muitos outros. - R. Sedgewick.Algorithms em C. Addison-Wesley, edn 1, pp253, 1990.
Armazena elementos (ou apontadores para elementos) dentro de nós internos do `fork’. - Veja para busca de strings etc..