Busca em Cadeia de Caracteres

Prévia do material em texto

U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Prof. Marcelo Otone Aguiar 
marcelo.aguiar@ufes.br 
www.marceloaguiar.pro.br 
Universidade Federal do Espírito Santo 
Centro de Ciências Exatas, Naturais e de Saúde – CCENS-UFES 
Departamento de Computação 
 
 
Busca em Cadeia de Caracteres 
Estrutura de Dados II 
 
COM10078 - Estrutura de Dados II 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
- Busca em cadeia de caracteres 
‣Força bruta; 
‣Algoritmo de Knuth-Morris-Pratt; 
‣Algoritmo de Boyer-Moore; 
‣Árvore Trie; 
‣Árvore PATRICIA; 
Conteúdo Programático da Disciplina 
2 
C.H. Prevista 
14 horas 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Conceitos Gerais 
• Uma cadeia de caracteres corresponde a uma sequência 
de elementos denominados caracteres. 
• Os caracteres são escolhidos de um conjunto denominado 
alfabeto. 
• Por exemplo, em uma cadeia de bits, o alfabeto é {0, 1}. 
• A pesquisa em cadeias de caracteres é um componente 
importante em diversos problemas computacionais, tais 
como edição de texto, recuperação de informação e 
estudo de sequências de DNA em biologia computacional. 
3 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Conceitos Gerais 
• Em programas editores de texto, o usuário pode estar 
interessado em buscar todas as ocorrências de um 
padrão (uma palavra particular) no texto que está sendo 
editado. 
• Esse problema é conhecido como casamento de cadeia 
de caracteres ou casamento de padrão (pattern 
matching) 
• O problema de casamento de cadeias ou casamento de 
padrão pode ser formalizado como se segue: 
4 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Conceitos Gerais 
• O texto é um arranjo T[1..n] de tamanho n 
• O padrão é um arranjo P[1..m] de tamanho m <= n 
• Os elementos de P e T são escolhidos de um alfabeto 
finito ∑ de tamanho c. 
• Exemplo, podemos ter: 
∑ = {0, 1} ou ∑ = {a, b, ..., z} 
• Dadas duas cadeias P (padrão) de comprimento |P| = m e 
T (texto) de comprimento |T| = n, em que n > m, deseja-
se saber as ocorrências de P em T. 
5 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Conceitos Gerais 
• Considerando os dados de entrada como sendo o texto T 
e o padrão P, temos as seguintes categorias de 
algoritmos: 
• Padrão e texto não são pré-processados: os algoritmos 
são do tipo sequencial, on-line e de tempo-real, pois tanto 
o padrão quanto o texto não são conhecidos a priori. 
• Estes algoritmos têm complexidade de tempo O(mn) para 
o pior caso. 
• Um exemplo é o algoritmo força bruta. 
6 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Conceitos Gerais 
• Padrão pré-processado: os algoritmos são do tipo 
sequencial e o padrão é conhecido anteriormente, o que 
permite o seu pré-processamento. 
• Estes algoritmos têm complexidade de tempo O(n) para o 
pior caso. 
• Representantes típicos desta categoria são os programas 
para edição de textos. 
• Os algoritmos mais conhecidos nesta categoria são o 
Knuth-Morris e Pratt, o Boyer-Moore e o Shif-And. 
7 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Conceitos Gerais 
• Padrão e texto são pré-processado: os algoritmos 
constroem um índice para permitir uma complexidade de 
tempo O(log n) ou menos. O tempo de pré-
processamento do texto para obter o índice pode ser tão 
grande quanto O(n) ou O(n log n), mas esse tempo é 
compensado por muitas operações de pesquisa no texto. 
Vale a pena construir um índice quando a base de dados 
é grande e semiestática. 
• Os tipos de índices mais conhecidos são os arquivos 
invertidos, árvores trie e Patricia, e arranjos de 
sufixos. 
8 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Casamento Exato 
• No casamento de padrão, o problema básico consiste em 
obter todas as ocorrências exatas do padrão no texto. 
• Os algoritmos para o casamento exato, em geral, 
funcionam em dois enfoques: 
• O primeiro consiste em ler os caracteres do texto um a 
um e, a cada passo, algumas variáveis são atualizadas 
de forma a identificar uma ocorrência possível. 
• Algoritmos: força bruta e o Knuth-Morris-Pratt 
9 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Casamento Exato 
• Os algoritmos para o casamento exato, em geral, 
funcionam em dois enfoques (continuação): 
• O segundo enfoque consiste em pesquisar o padrão P 
em uma janela que desliza ao longo do texto T. 
• Para cada posição desta janela, o algoritmo faz uma 
pesquisa por um sufixo da janela que casa com um 
sufixo de P, mediante comparações realizadas no 
sentido da direita para a esquerda. 
• Algoritmo: Boyer-Moore. 
10 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
 
 
BREVE HISTÓRICO 
11 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Breve Histórico 
• Em 1970, S. A. Cook provou um resultado 
teórico sobre um tipo particular de autômato que implicava 
na existência de um algoritmo de casamento de padrão 
com tempo proporcional a M + N no pior caso. 
• D. E. Knuth e V. R. Pratt seguindo a construção que Cook 
usara na demonstração do seu teorema obtiveram um 
algoritmo relativamente simples e prático. 
• Ocorreu também que J. H. Morris descobriu praticamente 
o mesmo algoritmo como solução de um problema de 
edição de texto. 
• Os três cientistas, Knuth, Morris e Pratt, não se 
preocuparam em publicar o algoritmo até 1976. 
12 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Breve Histórico 
• Nesse meio tempo, R. S. Boyer e J. S. Moore (e, 
independentemente, R. W. Gosper) descobriram um 
algoritmo que é muito mais rápido em muitas aplicações. 
• Muitos editores de texto usam esse algoritmo 
para busca de cadeias. 
• Em 1980, M. O. Rabin e R. M. Karp desenvolveram um 
algoritmo tão simples quanto o de força bruta que roda 
virtualmente sempre em tempo proporcional a M + N. 
• Além disso, o algoritmo deles estende-se facilmente a 
padrões bidimensionais que o torna mais útil que os 
outros para processamento de figuras. 
13 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
 
 
FORÇA BRUTA 
14 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
CEN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Força Bruta 
15 
• O algoritmo força bruta é o algoritmo mais simples para 
casamento de cadeias. 
• A ideia consiste em tentar casar qualquer subcadeia no 
texto de comprimento m com o padrão. 
• O pior caso do algoritmo força bruta é: 
Cn = m x n, 
Situação que ocorre, por exemplo, quando P = aab e 
 T = aaaaaaaaaa 
• Embora as cadeias que aparecem em muitas aplicações 
levam a um tempo de execução que é virtualmente 
proporcional a M + N 
 
 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Força Bruta 
16 
• Basicamente este algoritmo faz dois laços aninhados, 
sendo que, o laço externo pesquisa todos os possíveis 
índices do padrão dentro do texto, e o laço interno 
pesquisa cada caractere do padrão, comparando-o a seu 
correspondente potencial no texto. 
• O pior caso de tempo de procura não é bom, pois para 
cada índice-candidato em T pode-se realizar até m 
comparações de caracteres para descobrir que P não é 
igual a T começando no índice atual. 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Força Bruta 
Supondo que se recebe a cadeia de caracteres: 
T = “abacaabaccabacabaabb” 
P = “abacab” 
a b a c a a b a c c a b a c a b a a b b 
1 2 3 4 5 6 
a b a c a b 
7 
a b a c a b 
8 9 
a b a c a b 
1
0 
1
1 
1
2 
1
3 
a b a c a b 2
2 
2
3 
2
4 
2
5 
2
6 
2
7 
a b a c a b 
17 
Quantidade de comparações 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Pseudo-código 
Entrada: as cadeias T (texto) com n caracteres e P (padrão) com m 
caracteres 
Saída: o índice da primeira substring de T igual a P, ou uma 
indicação de que P não é uma substring de T 
para i<-0 até n-m {para cada índice candidato em T} faça 
 j <- 0 
 enquanto (j < m e T[i + j] = P[j]) faça 
 j <- j + 1 
 se j = m então 
 retorna i 
 retorna “Não existe substring em T igual a P.” 
18 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Desafio 
• Com o conhecimento que você possui da 
linguagem C e do funcionamento da busca por 
força bruta, implemente um algoritmo em C 
para este tipo de pesquisa. 
19 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
 
 
Algoritmo Knuth-Morris-Pratt 
20 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Knuth-Morris-Pratt (KMP) 
• É o primeiro algoritmo cujo pior caso tem complexidade de 
tempo linear no tamanho do texto. 
• É um dos algoritmos mais famosos para resolver o 
problema de casamento de cadeias. 
• O algoritmo foi inventado por Donald Knuth e Vaughan 
Pratt e independentemente por James Morris em 1977, 
embora os três tenham-no publicado conjuntamente. 
• Ele tem uma implementação complicada, e na prática 
perde em eficiência para os algoritmos Shift-And e 
Boyer-Moore-Horspool. 
21 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Knuth-Morris-Pratt (KMP) 
• Procura um padrão em um texto 
• String searching algorithm 
• Pouco código e muito eficiente 
• Complexidade no pior caso é O(n), ou seja é linear 
• A ideia geral é: 
• Quando aparece uma diferença (conflito), a palavra tem em si
 a informação necessária para determinar onde começar a 
próxima comparação (isso evita retroceder pelos caracteres já 
conhecidos) 
• Duas etapas: 
• Função prefixo 
• Função de comparação 
22 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Knuth-Morris-Pratt (KMP) 
• Exemplo com texto CAABAABAAAA e padrão AABAAA: 
• Depois do conflito entre txt[6] e pat[5], não precisamos 
retroceder no texto: podemos continuar e comparar 
txt[7..] com pat[3..]: 
 C A A B A A B A A A A 
 uma tentativa: A A B A A A 
não precisa tentar: A A B A A A 
 não precisa tentar: A A B A A A 
 próxima tentativa: A A B A A A 
23 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Função prefixo 
• É feito um pré-processamento do padrão e construído um 
vetor auxiliar de tamanho m. 
• O pré-processamento analisa todos os prefixos do padrão 
procurando pelo maior sufixo destes prefixos que também 
seja prefixo. 
• Desta forma, evita que um caractere seja reexaminado. 
• Ao final, teremos um vetor que conterá cada posição que 
gera um prefixo para cada posição do padrão. 
• O pré-processamento é realizado no padrão para 
determinar se seus prefixos aparecem como 
subsequências deles mesmos. 
24 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Função prefixo 
25 
A B C D A B C A 
j i i i i 
0 1 2 3 4 5 6 7 
-1 -1 -1 -1 0 
A == B? não, coloca -1 na posição marcada por “i” e incrementa “i” 
Depois, A == C? e assim sucessivamente... 
 
Se sim, então incrementa “j”, guarda o valor de “j” na posição marcada por “i” 
e incrementa o “i” 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Função prefixo 
26 
A B C D A B C A 
j i 
0 1 2 3 4 5 6 7 
-1 -1 -1 -1 0 1 
A == B? não, coloca -1 na posição marcada por “i” e incrementa “i” 
Depois, A == C? e assim sucessivamente... 
 
Se sim, então incrementa “j”, guarda o valor de “j” na posição marcada por “i” 
e incrementa o “i” 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Função prefixo 
27 
A B C D A B C A 
j i 
0 1 2 3 4 5 6 7 
-1 -1 -1 -1 0 1 2 
A == B? não, coloca -1 na posição marcada por “i” e incrementa “i” 
Depois, A == C? e assim sucessivamente... 
 
Se sim, então incrementa “j”, guarda o valor de “j” na posição marcada por “i” 
e incrementa o “i” 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Função prefixo 
28 
A B C D A B C A 
j i 
0 1 2 3 4 5 6 7 
-1 -1 -1 -1 0 1 2 
A == B? não, coloca -1 na posição marcada por “i” e incrementa “i” 
Depois, A == C? e assim sucessivamente... 
 
Se sim, então incrementa “j”, guarda o valor de “j” na posição marcada por “i” 
e incrementa o “i” 
 
Se “j” é diferente de -1, então podemos fazer j = aux[j], ou seja, J = 0, 
não incrementa o “i” e nem o “j” 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Função prefixo 
29 
A B C D A B C A 
j i 
0 1 2 3 4 5 6 7 
-1 -1 -1 -10 1 2 0 
Volta então o “j” na posição inicial e verifica: 
A == A? sim, incrementa “j”, guarda o valor de “j” na posição marcada por “i” e 
incrementa o “i” 
 
I = 8, ou seja, não é menor do que o tamanho da palavra ABCDABCA, 
portanto, chegamos ao fim da execução. 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Pseudo-código pré-processamento 
Entrada: as cadeias P (padrão) com m caracteres e tabela para 
armazenamento dos prefixos 
Saída: tabela com prefixos armazenados 
i <- 1 
j <- -1 
aux[0] = j 
para (i<-1 até m-1) faça 
 enquanto (j > -1 e P[j+1] <> P[i]) faça 
 j <- aux[j] 
 
 se (P[i] = P[j+1]) 
 j <- j + 1 
 
 aux[i] = j 
retorna aux 
30 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Exemplo Busca 
Supondo que se recebe a cadeia de caracteres: 
T = “abacaabaccabacabaabb” 
P = “abacab” 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
a b a c a a b a c c a b a c a b a a b b 
0 1 2 3 4 5 
a b a c a b 
31 
j 0 1 2 3 4 5 
P[j] a b a c a b 
F(j) -1 -1 0 -1 0 1 
0 1 2 3 4 5 
a b a c a b 
mismatching, K=0 
mismatching, K=-1 
0 1 2 3 4 5 
a b a c a b 
matching 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Pseudo-código Busca 
Entrada: as cadeias T (texto) com n caracteres e P (padrão) com m 
caracteres 
Saída: o índice da primeira substring de T igual a P, ou uma 
indicação de que P não é uma substring de T 
aux[m] 
preKMP(P, aux) 
k = -1 
para (i<-0 até n - 1) faça 
 enquanto (k > -1 e P[k+1] <> T[i]) faça 
 k <- aux[k] 
 
 se (T[i] = P[k+1]) então 
 k <- k + 1 
 
 se (k = m - 1) então 
 retorna i-k 
32 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Desafio 
• Implemente um algoritmo em C para a 
pesquisa KMP. 
• Você deverá implementar o pré-
processamento e a busca. 
33 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
 
 
Algoritmo Boyer-Moore 
34 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Algoritmo BM 
• Também chamado de Boyer-Moore. 
• Pela extrema simplicidade de implementação e 
comprovada eficiência, o BM deve ser escolhido em 
aplicações de uso geral que necessitam realizar 
casamento exato de cadeias. 
• A idéia é pesquisar no padrão no sentido da direita para a 
esquerda, o que torna o algoritmo muito rápido. 
• Executado frequentemente em editores de texto para os 
comandos de “localizar” e “substituir”. 
35 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Algoritmo BM 
• O algoritmo faz a varredura dos símbolos do 
padrão da direita para à esquerda (rightmost). 
• O algoritmo utiliza duas funções pré-processadas 
para deslocar o padrão à direita. 
• Estas funções dos deslocamentos são chamadas 
funções de ocorrência e de casamento. 
36 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Algoritmo BM 
• O enfoque do algoritmo BM consiste em pesquisar o 
padrão P em uma janela que desliza ao longo do texto T. 
• Para cada posição desta janela, o algoritmo faz uma 
pesquisa por um sufixo da janela que casa com um sufixo 
de P por meio de comparações realizadas no sentido da 
direita para a esquerda. 
• Se não ocorreu uma desigualdade, então uma ocorrência 
de P em T foi encontrada. 
• Senão, o algoritmo calcula um deslocamento em que o 
padrão deve ser deslizado para a direita antes que uma 
nova tentativa de casamento se inicie. 
37 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Algoritmo BM 
• O algoritmo BM original propõe duas heurísticas para 
calcular o deslocamento: 
• Heurística ocorrência: alinha a posição no texto que 
causou a colisão com o primeiro caractere no padrão 
que casar com ele. 
• Heurística casamento: ao mover o padrão para a 
direita, ele casa com o pedaço do texto anteriormente 
casado. 
38 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Heurística de ocorrência 
• Alinha a posição que causou a colisão no texto com o 
primeiro caractere no padrão que casa com este 
caractere; 
Ex.: P ={cacbac}, T ={aabcaccacbac}. 
 
 
39 
1 2 3 4 5 6 7 8 9 0 1 2 
a a b c a c c a c b a c 
c a c b a c 
c a c b a c 
c a c b a c 
c a c b a c 
c a c b a c 
A partir da posição 6 há uma 
colisão na posição 4. 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Heurística de casamento 
• Alinha a posição que causou a colisão no texto com o 
pedaço do padrão anteriormente casado; 
Ex.: P ={cacbac}, T ={aabcaccacbac}. 
 
 
40 
1 2 3 4 5 6 7 8 9 0 1 2 
a a b c a c c a c b a c 
c a c b a c 
c a c b a c 
c a c b a c 
A partir da posição 6 há uma coli
são na posição 4. 
Desloca o padrão até o 
próximo casamento. 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Algoritmo BM 
• O algoritmo BM decide qual das duas heurísticas deve 
usar escolhendo a que provoca o maior deslocamento do 
padrão. 
• Essa escolha implica realizar a comparação entre dois 
inteiros para cada caractere lido do texto, penalizando o 
desempenho do algoritmo com relação ao tempo de 
processamento. 
• A partir dessa observação, várias propostas de 
simplificação ocorreram ao longo dos anos, e os melhores 
resultados são os que consideram apenas a heurística 
ocorrência. 
41 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Algoritmo BMH 
• A simplificação mais importante é obra de Horspool 
(1980), conhecida como Boyer-Moore-Horspool (BMH), 
que executa mais rápido do que o algoritmo BM original. 
• Horspool observou que qualquer caractere já lido do texto 
a partir do último deslocamento pode ser usado para 
endereçar a tabela de deslocamentos. 
• Baseado neste fato, Horspool propôs endereçar a tabela 
com o caractere no texto correspondente ao último 
caractere do padrão. 
42 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Pseudo-código 
Entrada: as cadeias T (texto) com n caracteres e P (padrão) com m caracteres 
Saída: o índice da primeira substring de T igual a P, ou uma indicação de que P 
não é uma substring de T 
 
para j<-0 até j < 255 faça tabela[j] = m 
para j<-1 até j<m faça tabela[P[j-1]] = m – j 
i = m 
enquanto(i <= n) faça 
 k <- i 
 j <- m 
 enquanto (T[k-1] = P[j-1] e j > 0) faça 
 k <- k -1 
 j <- j -1 
 fimenquanto 
 
 se (j = 0) então 
 retorna k+1 
 i <- i + tabela[T[i-1]] 
fimenquanto 
retorna “Não existe substring em T igual a P.” 
43 
P[j-1] 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Desafio 
• Implemente um algoritmo em C para a 
pesquisa BMH. 
 
• Faça o teste com o texto = {aabcaccacbac} e 
o padrão = {cacbac} e apresente o número de 
instruções que foram executadas na busca 
pelo padrão. 
44 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Pesquisa Digital 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Pesquisa Digital 
• A pesquisa digital é baseada na representação das 
chaves como uma sequência de caracteres ou de dígitos. 
• O método de pesquisa digital é realizado da mesma forma 
que uma pesquisa em dicionários que possuem aqueles 
“índices de dedo”. Com a primeira letra da palavra são 
determinadas todas as páginas que contém as palavras 
iniciadas por aquela letra. 
• Os métodos de pesquisa digital são vantajosos quando as 
chaves são grandes e de tamanho variável. 
• Na pesquisa digital é possível localizar todas as 
ocorrências de determinada cadeia em um texto. 
46 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Pesquisa Digital 
• A diferença básica entre a busca digital e as buscas 
examinadas anteriormente é que a chave, na busca 
digital, não é tratada como um elemento único, indivisível. 
• Isto é, assume-se que cada chave é constituída de um 
conjunto de caracteres ou dígitos definidos em um 
alfabeto apropriado. 
• Em vez de se comparar a chave procurada com as 
chaves do conjunto armazenado, a comparação é 
efetuada, individualmente, entre os dígitos que compõem 
as chaves, dígito a dígito. 
47 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Pesquisa Digital 
• A raiz de uma árvore digital sempre existe e não corresponde a qualquer 
dígito do alfabeto. 
• Uma forma natural de decompor chaves constituídas de palavras é através 
das letras que as compõem. 
 
48 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Exemplo de Busca 
49 
x = seres 
x = sr 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Pesquisa Digital 
• É simples determinar a complexidade do processo de busca. 
O número de iterações efetuadas é igual ao tamanho k da 
chave, no máximo. 
• Em cada iteração, todas as operações podem ser efetuadas 
em tempo constante, exceto determinar o valor j 
correspondente à posição do dígito corrente na ordenação do 
alfabeto. Esse valor pode ser determinado, sem dificuldade, 
em tempo O(log m) por iteração, através de uma busca 
binária. 
• O algoritmo é então O(k(log m + 1)). Contudo, na maioria dos 
casos práticos o valor de m é pequeno. Nessa situação, a 
representação binária de cada dígito pode ser utilizada para 
determinar, diretamente, a sua posição na ordenação do 
alfabeto. Com essa premissa, a complexidade do algoritmo 
cai para O(k). 
50 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Pesquisa Digital 
• Uma vantagem desse método é que as chaves podem possuir 
tamanho arbitrário e variável. A complexidade da busca reflete 
apenas o tamanho da chave procurada. 
• Uma propriedade interessante dessa busca é que, ao localizar um 
certo prefixo x, terão sido localizadas todas as chaves do arquivo 
cujo prefixo é igual a x. Estas encontram-se na sub-árvore de raiz 
x. Tal propriedade pode ser útil em aplicações na área de 
linguística, onde os prefixos podem representar fonemas, palavras 
ou sentenças. 
• Intuitivamente, a técnica da árvore digital é tão mais eficiente 
quanto maior for a quantidade de chaves com prefixos comuns. 
Uma árvore digital que possua muitos zigue-zagues quase 
sempre é ineficiente. 
51 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
 
 
Árvore Trie 
52 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Árvore Trie 
• Definida em 1960 por Edward Fredkin; 
53 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Árvore Trie 
• Vêm de Retrieval 
• Cada nó contém informações sobre um ou mais símbolos 
do alfabeto utilizado 
• Principais Aplicações Abrangem: Corretores Ortográficos, 
Auto-Preenchimento de Textos e Armazenamento/Busca 
de Documentos XML 
• Cada nó no nível i representa o conjunto de todas as 
chaves que começam com a mesma sequência de i bits. 
 
 
 
54 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Árvore Trie 
Vantagens: 
• O formato das tries não depende da ordem em que as 
chaves são inseridas 
• Depende apenas dos valores das chaves 
• “Balanceamento natural” 
• Complexidade: O(AK) 
• A = tamanho do alfabeto 
• K = tamanho da chave 
• O pior caso é limitado pelo número de bits das chaves 
55 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Árvore Trie 
Desvantagens: 
• Caminhos de uma única direção acontecem quando 
chaves compartilham vários bits em comum 
• Por exemplo, as chaves B (00010) e C (00011) são 
idênticas exceto no último bit 
• Requer inspeção de todos os bits da chave independente 
do número de registros na trie 
• Os registros são armazenados apenas nas folhas, o que 
desperdiça memória em nós intermediários 
• Uma trie com N registros tem aproximadamente 1.44 N 
nós 
56 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
 
 
ÁRVORE PATRICIA 
57 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Árvore Patricia 
• A árvore Patricia é construída a partir da árvore binária de 
prefixo. Seja um conjunto de chaves {s1, …, sn} de valores 
binários tais que nenhuma chave seja prefixo de outra. 
• A árvore PATRICIA é uma representação compacta de 
uma Trie onde os nós que teriam apenas um filho são 
agrupados nos seus antecessores. É comum que as 
árvores Trie possuam um grupo disperso de chaves, 
desse modo, muitos nós possuem apenas um 
descendente. Isto faz com que as Trie tenham um custo 
grande de espaço. 
• A árvore Patriciaé estritamente binária, pois não possui 
zigue-zagues. 
58 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Árvore Patricia 
• Uma Trie usa cada uma das partes de uma chave, por 
vez, para determinar a sub-árvore. 
• Por outro lado, a árvore PATRICIA escolhe um elemento 
da chave (armazenando a sua posição) para determinar a 
sub-árvore. Isso remove a necessidade de nós com 
apenas um descendente. 
• Concebido por Donald Morrison, PATRICIA é um 
algoritmo para realização de buscas em árvores com as 
chaves dos nós representadas em binário, sem 
armazenar as chaves nos nós. 
59 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Árvore Patricia 
60 
• O nome é um acrônimo de “Practical Algorithm To 
Retrieve Information Coded In Alphanumeric”. 
• O método é particularmente útil para tratamento de 
chaves de tamanho variável extremamente longas, tais 
como títulos e frases. 
 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Busca 
61 
• A busca por uma string em uma arvore PATRICIA é 
similar a busca em uma Trie, com a diferença de que ao 
chegar em um nó, é comparado apenas um caractere, 
contra a comparação de substrings inteiras que acontece 
na Trie. 
• No pior caso, a complexidade de tempo é O(|s|), onde s é 
a string procurada. 
 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Inserção 
62 
• Inserir uma string em uma árvore Patricia é similar a pesquisar por 
essa string até o ponto onde a busca é encerrada, pois a string 
não é encontrada na árvore. 
• Se a busca é encerrada em uma aresta, um novo nó é criado 
nessa aresta. Esse nó armazena a posição do caractere que 
distingue a chave destino daquela aresta e a chave que se deseja 
inserir, e tem como filhos o nó que estava na extremidade 
seguinte da aresta e um novo nó com a parte restante da nova 
chave. 
• Se a busca for encerrada em um nó, então um nó filho é criado e 
o restante da nova chave é usado como rótulo para aresta entre 
os dois. 
• Ambos os casos tem complexidade de tempo de O(|s| + |E|), onde 
s é a string que será inserida e E é o alfabeto suportado pela 
árvore. 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
Remoção 
63 
• Remover uma string de uma árvore PATRICIA é o oposto da 
operação de inserção. 
• Primeiro, localiza-se a folha correspondente a string e remove-se 
ela da árvore. 
• Como o pai terá apenas um filho, os nós pai e irmão do nó 
removido são agrupados em um único nó. 
U
n
ive
rsid
ad
e
 Fe
d
e
ral d
o
 Esp
írito
 San
to
 - C
C
EN
S-U
FES 
Universidade Federal do Espírito Santo 
CCENS-UFES 
- Ordenação em memória primária 
‣Ordenação por troca direta (bolha); 
‣Ordenação por inserção direta; 
‣Ordenação por inserção binária; 
‣Ordenação por inserção com diminuição de incremento (shellsort); 
‣Ordenação por seleção direta; 
‣Heapsort; 
‣Quicksort; 
‣Mergesort; 
‣Ordenação por caixas; 
‣Ordenação por radicais; 
Próximo Conteúdo 
64 
C.H. Prevista 
26 horas