Template SBC

´
Algoritmos de pesquisa digital – Arvores trie e PATRICIA
Daniel Y. Chow1 , Gabriel C. Martins1
1

Universidade Estadual do Oeste do Paran´ (UNIOESTE) a Foz do Iguacu – PR – Brazil
¸
{gcmartins93,danielyc95}@gmail.com

Introducao
¸˜
´
Em estruturas de pesquisa como busca sequencial, busca bin´ ria e arvores bin´ rias e AVL a a s˜ o utilizados m´ todos de busca que visam localizar uma chave x dentro de um conjunto a e
`
S de chaves atrav´ s da comparacao chave a chave, onde x e Si, tal que Si S, s˜ o tratae
¸˜
a
´
dos como um unico elemento indivis´vel. Por´ m suponha que deseja armazenar um texto ı e liter´ rio para, em seguida, localizar frases nesse texto. Neste caso, o conjunto S de chaves a `
`
corresponderia as frases armazenadas, e cada Si, tal que Si S, a uma frase pass´vel de ı ser buscada. Este seria o cen´ rio perfeito para aplicacao das estruturas de pesquisa digia
¸˜
tal, como Retrieval e PATRICIA (Pratical Algorithm To Retrieval Information Coded In
Alphanumeric).
´
A diferenca entre busca digital e os algoritmos citados acima e que cada chave
¸
´ a ´
´
e n˜ o e tratada como um elemento indivis´vel. Isto e, assume-se que as chaves s˜ o conı a stitu´das de um conjunto de caracteres ou d´gitos de um alfabeto. Ao inv´ s de se comparar ı ı e a chave que deseja localizar com as chaves do conjunto S, compara-se individualmente os
`
d´gitos que as comp˜ em, digito a digito. ı o
´
Segundo Ziviane (2011, p. 188), ”o m´ todo de pesquisa digital e realizado da e mesma forma que uma pesquisa em dicion´ rios que possuem aqueles ”´ndices de dedo”. a ı
Com a primeira letra da palavra s˜ o determinadas todas as p´ ginas que contˆ m as palavras a a e iniciadas por aquela letra.”

1. Trie
O termo trie (lˆ -se trai) surgiu nos anos de 1960 definida por Edward Fredkin e tem e ´ origem na palavra retrieval, uma vez que a estrutura e usada na recuperacao de dados. Na
¸˜
estrutura de dados trie as