Embed Size (px)
Citation preview
1
TRIESEstruturas de Dados
Professor Dr. Paulo Roberto Gomes Luzzardi
Mestrando Eduardo da Silva Möller
2
TRIE - origem do termo vem da palavra retrieval,que significa recuperação.
Conceito
São estruturas de dados que representam as chaves caracter a caracter.
São árvores binárias, onde o filho de cada nodo representa o caracter seguinte e os irmãos representam as opções a serem usadas no lugar desse nodo.
3
Uso de uma Trie
Usada para fazer uma
rápida busca em grandes
TEXTOS
4
Formação das Chaves - Trie
- Cada chave é formada por uma combinação específica de símbolos do alfabeto.
- As combinações são de comprimento variável e ilimitado (chaves: binárias, códigos numéricos, etc.)
Cada chave é formada a partir de um alfabeto de símbolos.
Exemplos de alfabetos:{0, 1}{A, B, C, D, E, ..., Z}{0, 1, 2, 3, 4, 5, ..., 9}
5
Formação das Chaves - Trie
Exemplos de chaves:
- ABABBBABABA- 19034717- Maria-101010100000000000000101010100101010
As chaves são armazenadas e manipuladas de uma forma especial, pois são parcialmente partilhadas entre os elementos.
6
Comparação das Chaves - Trie
Em vez de se compararem chaves inteiras entre si, as comparações são feitas componente a componente.
Adicionalmente, as chaves são decompostas e as partes comuns entre elas são unidas.
7
Vantagens
- não ocorre desperdício de espaço em dados com tamanho variável (ex.: nomes)
- não precisa aplicar funções para converter chaves alfabéticas em numéricas
- percorrer a trie é eficiente e simples, porque cada nodo possui só dois ponteiros
8
Estrutura - Trie
9
Percorrendo uma Trie
• compara o primeiro caracter da chave com o nodo raiz
• enquanto o nodo atual não for o fim de uma palavra:
- procura pelo atual caracter da chave, no atual nível; - se encontrar, vai para próximo nível e procura próximo caracter; - se em algum dos níveis não encontrar, ou encontrar nodo com caracter de valor maior, a palavra não faz parte da trie.
• se chegou em nodo que não tem mais filhos, e corresponde ao último caracter da chave, então o caminho percorrido representa a chave desejada.
10
Características - Trie
As Tries são boas para suportar tarefas de tratamento lexicográfico, tais como:
- manuseamento de dicionários;
- pesquisas em textos de grande dimensão;
- construção de índices de documentos;
- expressões regulares (padrões de pesquisa).
11
Estrutura - Trie
As próximas Tries são mais organizadas de forma ligeiramente diferente do exemplo anterior.
Dado que todos os descendentes diretos de um mesmo pai são reunidos num único nó e as etiquetas ficam um nível abaixo do último símbolo da chave.
12
Estrutura - Trie
13
Estrutura - Trie
14
Estrutura - Trie
Portanto:
Cada nível da árvore que se desce, corresponde a avançar um elemento na chave;
Cada nó pode conter informação sobre um ou mais símbolos do alfabeto utilizado.
Assim: uma dada sequência de arestas pode formar qualquer palavra (chave) possível com base nesse alfabeto; não existe limite para o tamanho de uma sequência (e portanto para o tamanho de uma chave); as sequências têm comprimento variável.
15
R-Way Trie
Cada nó aloca espaço para todos os caracteres do alfabeto. Quase sempre há desperdício de espaço.
R = número de letras do alfabeto.
16\0 representa o fim de uma palavra.
Esse tipo de representação ternária é preferível em relação a outros tipos de tries porque se torna mais eficiente e simples, devido a cada nodo possuir somente três ponteiros.
TST - Ternary Search Tree
17
Tipos de Trie
R-Way Trie, se for reservada uma quantidade fixa de espaço a cada novo nó, poderá ocorrer desperdício de espaço, porque nem todas as chaves vão ocupar todo esse espaço reservado.
TST - Ternary Search Tree (Ternary Search Tree) tem um desempenho muito melhor em relação ao espaço, pois não o alocam em grande quantidade. Essas estruturas são árvores ternárias, onde o filho do centro de cada nodo representa o caracter seguinte da chave e os filhos da direita e da esquerda representam caracteres alternativos, isto é, pertencem a outra palavra.
18
Tipos de Trie
Aplicações específicas:
DST (Digital Search Tree);
Suffix Tree;
Patricia Tree;
DAWG (Directed Acyclic Word Graph);
TST (Ternary Search Tree).
19
Aplicações de Trie
Busca: localizar um dado que corresponde a chave informada;
Problema: seria em um sistema de cadastros de pessoas, onde quando temos nomes com grafias semelhantes (Manuel/Manoel, Elaine/Elayne, Luis/Luiz), podem ocorrer erros na entrada desses dados, ou seja, de não ser que sejam testados os possíveis erros cometidos.
20
Aplicações de Trie
Solução do problema: existe um método de busca por aproximação de correspondência, onde podemos localizar dados que são semelhantes a uma chave informada. Pela estrutura de representação de caracter a caracter usada nas tries, elas acabam tendo um desempenho muito bom nesse tipo de aplicação.
21
Corretor Ortográfico - Trie
Aplicação usual de Trie: é o corretor ortográfico. Nesse tipo de programa as palavras são comparadas com um dicionário armazenado em arquivo, e se não são encontradas indica-se as opões para correção.
22
Corretor Ortográfico - Trie
Com o dicionário armazenado numa trie, pode-se percorrer essa estrutura letra por letra para encontrar, ou não a palavra testada. Com base na chave informada o algoritmo vai percorrer a árvore que contém o dicionário, enquanto as letras da chave e alguma letra de cada nível da árvore coincidirem.
Caso seja detectado um erro na chave o algoritmo verifica a possibilidade de ocorrência de cada um tipos de erros para poder indicar as opções de correção.
23
Corretor Ortográfico - Trie
1. Substituição - avança um caracter na chave e avança um nível na árvore;
2. Deleção - avança um nível na árvore;
3. Inserção - avança um caracter na chave;
4. Transposição - avança um nível na árvore e testa a posição atual da chave, se coincidir, avança um caracter na chave e retrocede um nível na árvore para confirmar a inversão.
24
Corretor Ortográfico - Trie
Com as seguintes palavras: ABA, ANDA, MACA, MESA, MORTE, MOSCA.
Digamos que a chave a ser testada seja ADA, onde ocorreu erro na tentativa de escrever ABA. Será realizada a seguinte seqüência de testes :
* A = A - ok
* D = B - erro
* D = N - erro
* próximo passo avança na chave e na árvore (substituição)
* A = A - ok
25
Corretor Ortográfico - Trie
Detectado erro de substituição, onde a letra B foi substituída por D. Nesse ponto o algoritmo pode parar e apresentar as opções de correção, ou continuar verificando ocorrência dos outros tipos de erros a partir do ponto em que foi encontrada divergência entre o dicionário e a chave.
Vamos então analisar o teste de erro de deleção para a mesma chave.
* A = A - ok * D = B - erro * D = N - erro
* próximo passo avança somente na árvore (deleção)
* D = A - erro * D = D - ok * A = A - ok
Detectado erro de deleção, onde a letra N foi suprimida da chave.
26
Auto-preenchimento
Armazena palavras mais
usadas em uma TRIE
A medida que vai
digitando exibe as opções
possíveis de palavras já usadas
27
Auto-preenchimento de Textos - Trie
Utilização desta aplicação: Browsers; Programas de e-mail: Gmail e o Yahoo! mail, até linguagens de programação.
Série de endereços que já foram usados (browser/e-mail) ou os comandos disponíves (linguagem de programação).
São armazenados em tries e a medida que é digitada uma seqüência de caracteres o algoritmo vai comparando a existência de correspondências na estrutura. A cada caractere digitado, são apresentadas as opções de preenchimento, e no momento em que só existir um caminho possível a ser seguido na trie ocorre o preenchimento automático.
28
maca
mesa
morte
mosca
Auto-preenchimento
A
C
A
E
S
A
O
R
T
S
C
A
M
E
M O S C A
morte
mosca
mosca
29
Inserção - Trie
É feita uma busca pela palavra a ser inserida, se ela já existir na trie nada é feito, caso contrário, é recuperado o nó até onde acontece a maior substring da palavra a ser inserida, sendo o restante dos seus caracteres (palavra - prefixo) adicionados na trie a partir daquele nó.
30
Remoção - Trie
Tendo a busca encontrado o nó que representa o final da palavra a ser removida, são removidos os nós que possuem apenas um filho seguindo o caminho ascendente. A remoção é concluída quando se encontra um nó com mais de um filho.
31
Complexidade - Trie
Complexidade das operações de manipulação de uma Trie:
O(AK), em que:
A = tamanho do alfabetoK = tamanho da chave
A utilização de uma Trie só compensa se o acesso aos componentes individuais das chaves for bastante rápido, de outro modo as perdas de eficiência são significativas.
As Tries podem ser uma boa alternativa às árvores balanceadas porque garantem tempos de acesso razoáveis no pior caso, sem necessidade de operações complexas de balanceamento.
32
Complexidade - Trie
Quanto ao espaço: quanto maior for a estrutura mais eficiente se torna ao nível do espaço.
O desperdício de espaço: é considerável para quantidades pequenas de dados.
É devido a esse desperdício de espaço que surgiram estruturas mais eficientes baseadas em tries, como as tries compactas, também chamadas de Árvores Patricia.
33
Algorítmo de Inserção - TRIE
trie insert( key, t, depth )
typekey key;
trie t;
int depth;
{
int j;
trie t1;
if ( t==NULL ) return( NewDataNode(key) );
if ( IsData(t) )
34
Algoritmo de Inserção - TRIE
Continuação
if (t->k == key)
Error /*** Key already in table ***/;
else { t1 = NewIntNode();
t1->p[ charac(depth,t->k) ] = t;
t = insert( key, t1, depth );
}
else { j = charac(depth,key);
t->p[j] = insert( key, t->p[j], depth+1 );
}
return( t );
}
35
Algoritmo de Busca - TRIE
search( key, t )
typekey key;
trie t;
{
int depth;
for( depth=1; t!=NULL && !IsData(t); depth++ )
t = t->p[ charac(depth,key) ];
if( t != NULL && key == t->k )
found( t );
else notfound( key );
}
36
Referências
http://www.csse.monash.edu.au/%7Elloyd/tildeAlgDS/Tree/Trie/
http://www.ual.pt/dct/aed2/teoricas/Semana10.pdf
http://www.cs.princeton.edu/courses/archive/fall04/cos226/lectures/trie.4up.pdf
http://www.cis.ksu.edu/~rhowell/viewer/viewer.html
http://www.nist.org/
GOODRICH, Michael T.; TAMASSIA, Roberto; Data Structures and Algorithms in Java. John Wiley & Sons, Inc, 1998.
