Prévia do material em texto
Pesquisa Digital
Pesquisa digital é baseada na representação das
chaves como uma sequência de símbolos de um
alfabeto. Ex: {0,1}, {a, b, c, ...}, {0, 1, 2, ...}.
As chaves são comparadas símbolo a símbolo em uma
busca.
Os métodos de pesquisa digital são particularmente
vantajosos quando as chaves são grandes e de
tamanho variável.
c a s a 2 3 5 a b
chaves
Pesquisa Digital
Um aspecto interessante é a possibilidade de localizar
todas as ocorrências de uma determinada cadeia em
um texto, com tempo de resposta logarítmico em
relação ao tamanho do texto.
Aplicações
Indexação de textos
Corretores ortográficos
Autopreenchimento de textos
Compressão de dados
Tabela de roteamento para endereços IP
Biologia Computacional
Estudaremos as árvores Trie e Patricia.
Vem de retrieval (recuperação) mas se pronuncia “try”.
Cada nó contém informações sobre um ou mais
símbolos.
O caminho da raiz da Trie para qualquer outro nó
representa um prefixo de uma string.
Em Tries compactas todos os descendentes diretos
do mesmo pai são agrupados.
Trie
É uma árvore 𝑀-ária (com 𝑀 filhos).
Os nós são vetores de 𝑀 componentes com campos
correspondentes aos símbolos que formam as chaves.
Trie
𝑀 = 2 𝑀 = 𝑛
...
...
Cada nó no nível 𝑖 representa o conjunto de todas as
chaves que começam com a mesma sequência de 𝑖
símbolos.
Este nó especifica uma ramificação com 𝑀 caminhos
dependendo do (𝑖 + 1)-ésimo símbolo de uma chave.
Trie
0
0
1
𝑖
O nó 𝑖 vai representar
todas as chaves que
começam com 00.
Ex:
• 0000
• 0001
• 0010
• 0011
𝑀 = 2
Trie
Considerando as chaves como sequência de bits (isto é,
𝑀 = 2), o algoritmo de pesquisa digital é semelhante ao
de pesquisa em árvore binária, exceto que, em vez de se
caminhar na árvore de acordo com o resultado de
comparação entre chaves, caminha-se de acordo com os
bits da chave.
0
0
1
Trie
Uma Trie para as palavras: carro, casa, bico, bicicleta
c
a
r
r
o
s
a
b
i
c
o i
c
l
e
t
a
c
a
r s
b
i
c
o i
bicicleta bico
carro casa
Trie compacta
N
ó
s
e
x
te
rn
o
s
Compactando os nós externos
Trie
Nesta disciplina iremos usar Tries compactas
Nó interno:
São utilizados para diferenciar as chaves.
Nó externo:
São nós folhas.
Armazenam as chaves.
chave
ponteiros
...
Trie (inserção)
Dado uma chave 𝑥
Se a árvore está vazia então
Crie um nó externo, armazene 𝑥 e retorne.
Senão
Caminhe na árvore até encontrar um NULL ou um nó externo 𝑦
Se foi encontrado um NULL então
Crie um nó externo, armazene 𝑥 e retorne
Senão //encontrou um nó externo 𝑦
Se 𝑥 ≠ 𝑦 então
Encontre, a partir do símbolo que encontrou 𝑦, quais símbolos
que 𝑥 e 𝑦 são iguais e insira para cada um deles um nó interno.
Para o símbolo que difere, crie um nó externo para 𝑥 e armazene
na árvore os nós externos de 𝑥 e 𝑦, e retorne.
Senão
𝑥 já está na árvore, retorne.
Trie (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B
Trie (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B
C
Trie (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B C
0
1
0
0
1
0 1
Trie (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B C
0
1
0
0
1
0 1
H
Trie (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B C
0
1
0
0
1
0 1
H
1
Trie (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B C
0
1
0
0
1
0 1
H
1
J
Trie (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B C
0
1
0
0
1
0 1
H
1
J
1
Trie (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B C
0
1
0
0
1
0 1
H
1
J
1
Q
Trie (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B C
0
1
0
0
1
0 1
H
1
J Q
1
1
0
0
Trie (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
Inserir as chaves
W = 110110
K = 100010
B C
0
1
0
0
1
0 1
H
1
J Q
1
1
0
0
Trie (remoção)
Dado uma chave 𝑥
Caminhe na árvore (de forma recursiva) até encontrar um NULL
ou um nó externo 𝑦
Se encontrou NULL ou 𝑥 ≠ 𝑦 então
Retorne, pois 𝑥 não está na árvore.
Senão
Remova o nó externo
Atribua NULL para o ponteiro que apontava para o nó externo
Retorne da recursão para o nó anterior.
//Durante o retorno da recursão faça a contração
Se o nó atual tem somente 1 filho Faça
Atribua para o ponteiro o nó externo
Remova o nó interno atual
Trie (remoção)
Remover
C = 010011
B C
0
1
0
0
1
0 1
H
1
J Q
1
1
0
0
Encontrar C
Trie (remoção)
Remover
C = 010011
B C
0
1
0
0
1
0 1
H
1
J Q
1
1
0
0
Remove C
Trie (remoção)
Remover
C = 010011
B
0
1
0
0
1
0
H
1
J Q
1
1
0
0
No só tem 1 filho.
Remover o nó e atribui o ponteiro
do pai para o nó externo B.
Contração
Trie (remoção)
Remover
C = 010011
B
0
1
0
0
1
H
1
J Q
1
1
0
0
No só tem 1 filho.
Remover o nó e atribui o ponteiro
do pai para o nó externo B.
Contração
Trie (remoção)
Remover
C = 010011
B
0
1
0
0
H
1
J Q
1
1
0
0
No só tem 1 filho.
Remover o nó e atribui o ponteiro
do pai para o nó externo B.
Contração
Trie (remoção)
Remover
C = 010011
B
0
1
0
H
1
J Q
1
1
0
0
No tem mais de 1 filho.
Parar.
Trie
Considerações Importantes:
O formato das tries, diferentemente das árvores binárias
comuns, não depende da ordem em que as chaves
são inseridas e sim da estrutura das chaves através
da distribuição de seus símbolos.
Desvantagem:
A formação de caminhos de uma só direção para
chaves com um grande número de bits em comum.
Exemplo: Caminho gerado pelas chaves B e
C no exercício anterior.
Exercícios
1. Desenhe passo a passo a árvore trie resultante da inserção das
palavras: carro, casa, bico, bicicleta, casamento.
Exercícios
2. Desenhe passo a passo a árvore trie resultante da inserção dos
registros com as chaves F, C, Q, H, R, X, O, B nesta ordem, em
uma árvore vazia.
a) Apresente os bits comparados para localizar ou não as chaves D, R, Z,
F. Caso exista comparação com alguma chave, informe se era a chave
procurada ou não.
b) Remova as chaves Q e C
Patricia
PATRICIA - Practical Algorithm To Retrieve Information
Coded In Alphanumeric
Criado por Morrison D. R. 1968 para aplicação em
recuperação de informação em arquivos de grande
porte.
Patricia
Knuth D. E. 1973 → novo tratamento algoritmo.
Reapresentou-o de forma mais clara como um caso particular de
pesquisa digital, essencialmente, um caso de árvore trie binária.
Sedgewick R. 1988 apresentou novos algoritmos de
pesquisa e de inserção baseados nos algoritmos
propostos por Knuth.
Gonnet, G.H e Baeza-Yates R. 1991 propuseram
também outros algoritmos.
Patricia
O algoritmo para construção da árvore Patricia é
baseado no método de pesquisa digital, mas sem o
inconveniente citado para o caso das tries.
O problema de caminhos de uma só direção é eliminado
por meio de uma solução simples e elegante:
Cada nó interno da árvore contém o índice do bit a ser
testado para decidir qual ramo tomar.A árvore Patria é um tipo de árvore Trie compacta.
Patricia
Exemplo: dada as chaves de 6 bits:
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B C
1
3
6
0
0 1 H
1
J Q
3
1
1 0 0
Trie
Patricia
Patricia
Exemplo para as palavras: carro, casa, bico, bicicleta, rato
c
a
r s
b
i
c
o i
bicicleta bico
carro casa
1
3 4
c
r s
b
o i
bicicleta bico
carro casa
Trie Patricia
r
rato
r
rato
Patricia (inserção)
Árvore Patricia binária
Cada chave 𝑘 é inserida de acordo com os passos
abaixo, partindo da raiz:
1. Se a subárvore corrente for vazia, então é criado um nó
externo contendo a chave 𝑘 (isto ocorre somente na
inserção da primeira chave) e o algoritmo termina.
2. Se a raiz da subárvore corrente for um nó interno, vai-se
para a subárvore indicada pelo bit da chave 𝑘 de índice
dado pelo nó corrente, de forma recursiva.
Patricia (inserção)
3. Se a subárvore corrente for simplesmente um nó externo
𝑝, os bits da chave 𝑘 são comparados:
a) Compare, saindo do início, os bits correspondentes da
chave 𝑝 com a chave 𝑘 até encontrar um índice 𝒊 cujos
bits difiram.
b) Se todos forem iguais, a chave já se encontra na árvore e
o algoritmo termina;
c) senão, vai-se para o Passo 4.
Patricia (inserção)
4. Um nó interno e um nó externo são criados: o primeiro
contendo o índice 𝒊 e o segundo, a chave 𝑘. A seguir, o
nó interno é ligado ao externo pelo apontador da
subárvore esquerda ou direita, dependendo se o bit de
índice 𝒊 da chave 𝑘 é 0 ou 1, respectivamente.
5. O caminho de inserção é percorrido de baixo para cima,
subindo com o par de nós criados no Passo 4 até chegar
a um nó interno cujo índice seja menor que o índice 𝒊
determinado no Passo 2. Este é o ponto de inserção e o
par de nós é inserido.
Patricia (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B
Patricia (inserção)
Dada as chaves de 6 bits
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
B
C
B e C
Diferem no bit 6
C
6
1