ARVORE PATRICIA

A árvore PATRICIA - Practical Algorithm To Retrieve Information Coded In Alphanumeric - É um tipo de árvore de prefixos em que sequências de nós com apenas um filho são compactados em um único nó.

Concebido por Donald Morrison, PATRICIA é um algoritmo para realização de buscas em árvores com as chaves dos nós representadas em binário, sem armazenar as chaves nos nós. O nome é um acrônimo de “Practical Algorithm To Retrieve Information Coded In Alphanumeric”, e o método é particularmente útil para tratamento de chaves de tamanho variáveis extremamente longas, tais como títulos e frases. No caso de pesquisas analíticas, os dados podem tirar proveito deste método desde que as informações sejam armazenadas como cadeias de texto.

Uma restrição dessas árvores é a necessidade de não haver um elemento que seja prefixo de outro, o que pode facilmente ser obtido se necessário.

Vêm de Retrieval (Relacionado à Recuperação de Informações)

Para distinção com tree pronuncia-se try

Cada nó contém informações sobre um ou mais símbolos do alfabeto utilizado

Alfabeto pode abranger: {0,1}, {A, B, C, D...} ou {0, 1, 2, 3,4...} e mais o caracter nulo (ou branco).

Caminho da raiz (root) da trie para qualquer outro nó em representa um prefixo de uma String

Principais Aplicações Abrangem: Corretores Ortográficos, Autopreenchimento de Textos e Armazenamento/Busca de Documentos XML

Em Tries Compactas todos os descendentes diretos do mesmo pai são agrupados

No último nodo, o último caracter da palavra sendo procurada deverá ter associado a si (como seu apontador) a posição da palavra no texto.

Trie Compactada Binária

Caminhos que possuem nós com apenas 1 filho são agrupados em uma única aresta

Diferente das Tries não armazena informações nos nodos internos, apenas contadores e ponteiros para cada sub-árvore descendente.

Campo Avançar

• Registro Acumulativo que Integra todos os Nodos Exceto os Folhas

• Identifica qual a Posição do Caracter da Chave Informada que deve ser analisado

Campo Comparar Com

• Apresenta o Caracter que deve ser Comparado ao Caracter da Chave Informada

• Como nas Árvores Binárias de Busca, após a análise, se a Chave é Menor ou Igual ao Nodo ela é Alocada/Consultada à Esquerda senão à Direita.

Exemplo de Consulta

Etapas:

• Primeiro Nodo Informa pra Comparar 7º Caractere da Palavra com “a”.

• Como “t” é maior que “a” desloca-se pra sub-árvore da direita.