17
Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Embed Size (px)

Citation preview

Page 1: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 514311

Trie

Nuno Campos

N.º 51431

Page 2: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 514312

Introdução às Tries

Trie (de retrieval) – estrutura de dados em árvore Chaves representadas por strings Suporta operações eficientes de PROCURA,

INSERÇÃO e REMOÇÃO Representa um alfabeto finito Todos os descendentes de um nó têm um prefixo

comum

Page 3: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 514313

Vantagens das Tries

(em relação à BST)

Procura de chaves mais rápida

Necessitam de menos espaço

Procura de prefixo mais longo eficiente

Page 4: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 514314

Aplicações das Tries

Verificadores de Ortografia Compressão de dados Biologia computacional Tabelas de reencaminhamento para

endereços IP Guardar e aplicar queries a documentos

XML Aplicações Modernas: Motores de procura

Page 5: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 514315

Tries e Motores de procura

Índice de motores de pesquisa– Colecção de todas as palavras a procurar– Guardadas numa trie compacta

Cada folha de uma trie– Está associada com a palavra– Lista de páginas (URLs) contendo essa palavra (lista de

ocorrências) A trie é mantida em memória Lista de ocorrências é mantida em memória externa

– Ordenada por relevância

Page 6: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 514316

Representação de Tries

nó / A E I L O R

0 - 1 - - - - 6

1 - - - - 2 - 4

2 - - - 3 - - -

3 (1) - - - - - -

4 (2) - - - - 5 -

5 (3) - - - - - -

6 - - - 7 - - -

7 - - - - - 8 9

8 (4) - - - - - -

9 (5) - - - - - -

Representação em Árvore (Non-compact trie)

Representação em Matriz

Page 7: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 514317

Análise de Trie Não Compacta

Usa espaço O(n) Suporta procuras, inserções e remoções em

tempo O(dm)– n é o tamanho total das strings no conjunto total

de todas as strings– m é o tamanho do parâmetro string da operação– d é o tamanho do alfabeto

Page 8: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 514318

Tries compactas

Uma trie compacta pode ter nós de grau 2 Uma trie compacta é obtida a partir de uma trie não compacta por compressão de nós

redundantes

Page 9: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 514319

Representação compacta

Page 10: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 5143110

Análise de Trie Compacta

A representação compacta, para um array de strings:– Guarda, nos nós, valores de índices em vez de

substrings– Usa O(s) de espaço, onde s é o número d strings

no array– É utilizado como uma estrutura de índices auxiliar

Page 11: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 5143111

Suffix Trie

m i n i m i z e

0 1 2 3 4 5 6 7

A suffix trie de uma string X é a trie compacta de todos os sufixos de X

Page 12: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 5143112

Análise de Suffix Trie

String X de tamanho n Alfabeto de tamanho d

– Espaço O(n)– Queries de procura de padrões aleatórios em X:

tempo O(dm)– m é tamanho do padrão– Pode ser construída em tempo O(n)

Page 13: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 5143113

Adicionar uma palavra (1)

Trie Não Compacta– Procurar letras na trie– Se não encontrar, criar nós que faltam

Adicionar a palavra RICO

Page 14: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 5143114

Adicionar uma palavra (2)

Trie Compacta– Procurar letras na trie– Criar nó com as letras que faltam

Adicionar a palavra RICO

Page 15: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 5143115

Remover uma palavra (1)

Trie Não Compacta– Procurar palavra seguindo a trie– Remover a partir do fim, até atingir um nó que tenha mais de um filho

Remover AR

Page 16: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 5143116

Remover uma palavra (2)

Trie Compacta– Procurar palavra seguindo a trie– Remover o nó final– Caso o nó pai do nó final apenas tenha mais um filho, então juntamos o nó pai e o novo nó filho

Remover AR

Page 17: Nuno Campos - N.º 51431 1 Trie Nuno Campos N.º 51431

Nuno Campos - N.º 5143117

Referências

Ramesh et al [1989] Goodrich, Tamassia [2004] Glander, Karl W. and Durre, Karl P. [1994] http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie/ http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic7/ http://www.cse.lehigh.edu/~lopresti/Courses/2003-04/CSE397-497/lecture_8.ppt http://linux.thai.net/~thep/datrie/datrie.html http://tarar.zabvision.edu.pk/data/DS/Sufix%20Trees/Topic%20%237%20Tries%20and

%20suffix%20trees.htm http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node22.html http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node24.html http://www.cs.princeton.edu/courses/archive/spring04/cos226/lectures/trie.4up.pdf http://ww3.algorithmdesign.net/handouts/Tries.pdf http://www.cs.umd.edu/class/spring2005/cmsc132/lecs/lec22.ppt http://algo.inria.fr/seminars/sem00-01/bourdon.pdf http://en.wikipedia.org/wiki/Main_Page