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 nó raiz e um nó 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 nó 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