Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

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

Mais conteúdos dessa disciplina