RVORES PATRICIA

09/09/2015

ÁRVORES PATRICIA

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL

ÁRVORES PATRICIA

CLEBER MACHADO
CIÊNCIA DA COMPUTAÇÃO
Classificação e Pesquisa de Dados

Porto Alegre – RS, Junho de 2008.

ÁRVORES PATRICIA

http://www.inf.ufrgs.br/~cagmachado/INF01124/t3.htm

1/8

09/09/2015

ÁRVORES PATRICIA

· 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, Auto­Preenchimento 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. Exemplo de Representação

http://www.inf.ufrgs.br/~cagmachado/INF01124/t3.htm

2/8

09/09/2015

ÁRVORES PATRICIA

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