Projeto e Análise de Algoritmos  
Aula 07 Tries  
Edirlei Soares de Lima  
<edirlei@iprj.uerj.br>  
Tries  
Originado de "information reTRIEval" devido a aplicação em  
recuperação de informação.  
Agilizam a busca através do pré-processamento do texto.  
Quando uma série de consultas é realizada em um texto fixo,  
o custo inicial de pré-processar o texto compensado pela  
aceleração das consultas seguintes.  
Permite a busca por padrões de texto em tempo proporcional  
ao tamanho do padrão buscado.  
Tries  
S = {bear, bell, bid, bull, buy, sell, stock, stop}  
b
s
e
i
u
e
l
t
a
r
l
l
d
l
l
y
o
l
c
k
p
Cada nó (exceto o nó raiz) contem um caractere;  
Os nós filhos são ordenados alfabeticamente;  
Os caminhos entre o raiz e um folha contem uma das strings S.  
Tries - Análise  
Se o comprimento total do texto é n, o texto possui m palavras e  
d é o tamanho do alfabeto:  
Cada nó possui no máximo d filhos;  
A trie possui m folhas e tem altura igual ao comprimento da maior palavra;  
O número de nós é O(n) (n se nenhum par de palavras compartilha um  
mesmo prefixo);  
b
i
s
e
u
e
l
t
a
r
l
l
d
l
l
y
o
l
c
k
p
Tries - Análise  
Uma trie utiliza espaço O(n) e permite realizar buscas,  
inserções e remoções em tempo O(dm).  
n: tamanho total das strings em S;  
m: tamanho da string buscada, inserida ou removida;  
d: tamanho do alfabeto;  
b
s
e
i
u
e
l
t
a
r
l
l
d
l
l
y
o
l
c
k
p
Tries Encontrando Padrões  
s e e  
a
b e a r ?  
s e l l  
s t o c k !  
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23  
s e e  
a
b u l l ?  
b u y  
s t o c k !  
2
4 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46  
b i d  
s t o c k !  
b i d  
s t o c k !  
4
7 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68  
h e a r  
t h e  
b e l l ?  
s t o p !  
6
9 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88  
b
i
h
e
a
s
e
u
e
t
a
l
l
l
y
e
l
o
d
36  
0, 24  
4
7, 58  
r
r
c
p
l
l
6
69  
84  
78  
30  
12  
k
17, 40,  
51, 62  
Tries Comprimidas  
Em uma trie comprimida:  
Cada nó interno deve ter pelo menos 2 filhos. Nós que contem apenas  
1 filho são concatenados, formando um novo nó;  
b
s
e
i
u
e
l
t
a
l
l
d
l
l
y
o
r
l
c
k
p
Tries Comprimidas  
Em uma trie comprimida:  
Cada nó interno deve ter pelo menos 2 filhos. Nós que contem apenas  
1 filho são concatenados, formando um novo nó;  
b
s
e
id  
u
ell  
to  
ar  
ll  
ll  
y
ck  
p
Menor número de nós, porém a informação de cada ocupa mais espaço.  
Solução?  
Tries Comprimidas  
Representação compacta para uma trie comprimida:  
Armazena intervalos de indices nos nós em vez de substrings;  
Utiliza espaço O(s);  
0
1 2 3 4  
0 1 2 3  
0 1 2 3  
S[0] = s e e  
S[4] = b u l l  
S[7] = h e a r  
S[1] = b e a r  
S[2] = s e l l  
S[3] = s t o c k  
S[5] = b u y  
S[6] = b i d  
S[8] = b e l l  
S[9] = s t o p  
1
, 0, 0  
, 1, 2  
0, 0, 0  
7
, 0, 3  
1, 1, 1  
4, 1, 1  
0, 1, 1  
3, 1, 2  
2, 2, 3 3, 3, 4 9, 3, 3  
6
1, 2, 3  
8, 2, 3  
4, 2, 3  
5, 2, 2 0, 2, 2  
Suffix Trie  
Uma suffix trie de uma string X é uma trie (comprimida ou  
não comprimida) de todos os sufixos de X.  
m i n i m i z e  
0
1 2 3 4 5 6 7  
e
i
mi  
nimize  
ze  
mize nimize  
ze  
nimize  
ze  
Suffix Trie Análise  
Representação compacta da suffix trie de uma string X de  
tamanho n usando um alfabeto de tamanho d.  
Permite realizar buscas por padrões arbitrários em O(dm), onde m é o  
tamanho do padrão a ser buscado.  
m i n i m i z e  
0
1 2 3 4 5 6 7  
7
, 7  
1, 1  
2, 7  
0, 1  
2, 7  
6, 7  
4
, 7  
6, 7  
2, 7  
6, 7  
Tries Aplicações  
Motores de busca armazenam o seu índice de busca (coleção de  
palavras que podem ser buscadas) em uma trie comprimida.  
Cada nó folha da trie é associada a uma palavra e a uma lista de páginas  
web (URLs) contendo a palavra;  
A trie é mantida em memória;  
A lista de ocorrências é mantida em memória externa e pode ser  
ranqueada por relevância;  
Buscas booleanas envolvendo conjuntos de palavras (exemplo: Analise  
and Algoritmos), correspondem a conjuntos de operações (exemplo:  
intercessão) nas listas de ocorrências;  
Técnicas extras também podem ser incluídas (exemplo: eliminação de  
stopwords).  
Tries Aplicações  
Base de Documentos  
Documento Texto  
Lista de ocorrências  
Pease porridge hot, pease porridge cold  
1
2
3
4
5
6
No  
Termo  
(Docs; Pos)  
Pease porridge in the pot  
Nine days cold  
1
2
3
4
5
6
7
8
9
0
1
2
3
cold  
days  
hot  
in  
it  
like  
nine  
old  
pease  
porridge  
pot  
some  
the  
(1;6), (4;8)  
(3;2), (6;2)  
(1;3), (4;4)  
(2;3), (5;4)  
(4;3,7), (5;3)  
(4;2,6), (5;2)  
(3;1), (6;1)  
(3;3), (6;3)  
(1;1,4), (2;1)  
(1;2,5), (2;2)  
(2;5), (5;6)  
(4;1,5), (5;1)  
(2;4), (5;5)  
Some like it hot, some like it cold  
Some like it in the pot  
Nine days old  
1
1
1
1
Vocabulário  
Ocorrências e posições  
Exercícios  
Lista de Exercícios 07 Tries  
http://www.inf.puc-rio.br/~elima/paa/  
Leitura Complementar  
Halim e Halim. Competitive Programming,  
3
rd Edition, 2003.  
Capítulo 6: String Processing