Casamento de Padrões
Um Estudo Empírico
Leonardo Teixeira Passos
Thiago Henrique Braga
Sumário





Introdução
Definição do Problema
Algoritmos clássicos
Resultados Experimentais
Conclusões
Introdução

Casamento de padrões possui várias
aplicações:
– Editores de texto
– Casamento de cadeias de DNA



Ampla literatura disponível
Vários algoritmos propostos
Melhorias de algoritmos anteriores
Definição Formal



Texto T[1 .. n] e Padrão P[1 .. m]
Tamanhos n e m, onde m ≤ n
Encontrar todos os deslocamentos s
onde T[s+1 .. s+m] = P[1 .. m],
com 0 ≤ s ≤ n – m
c b a c b a b a b a c b T
s=3
c b a b a P
Algoritmos clássicos

Geralmente possuem duas fases:
– Pré-processamento
– Emparelhamento





Força Bruta
Rabin Karp
Knuth-Morris-Pratt
Boyer-Moore
Boyer-Moore-Horspool
Força Bruta

Método simples de casamento.

Não é inteligente o bastante para
aproveitar caracteres já casados,
quando acha um caracter em P que não
pode ser casado em T.
Força Bruta

Desloca uma posição a cada nova
iteração, independente de ter
encontrado um casamento ou não.

O padrão desloca-se no texto como
uma janela.

Complexidade: O(n2) .
Força Bruta
Rabin Karp

Algoritmo que utiliza o conceito de
hash.

É uma melhora do algoritmo de Força
Bruta.
Rabin Karp

O algoritmo gera para o padrão P um
código, digamos p, que é calculado
uma única vez.

Exemplo:
Rabin Karp

Para cada porção do texto T a ser
casada com P, gera-se o código de T,
digamos t, que é então comparado com
p;
Rabin Karp

No entanto, toda vez que se tenta casar
uma nova porção de texto em T com P,
o algoritmo utiliza o valor t’ da última
iteração como parte do cálculo para o
novo t.
Rabin Karp

Exemplo:
Rabin Karp

Retira-se a parte mais significativa do
número, move o restante em um casa,
e acrescenta o número referente ao
novo caracter (parte menos
significativa).

aba = t’ = 2562 * 97 + 256 * 98 + 97

baa = t = t’ * 256 - 2563 + 97
Rabin Karp

O cálculo de t e p poderá envolver
números que consomem uma grande
quantidade de bits.

Como consequência, utiliza-se o
operador `mod` nos cálculos
intermediários, sem afetar o resultado
final (`mod` aplicado ao resultado final).
Rabin Karp

O segundo operador da operação
`mod` deverá ser um número primo
grande, para evitar colisões.
Rabin Karp

Ao utilizarmos o operador de módulo,
quando obtermos p  q, então
necessariamente garantimos que
P[1 .. m]  T[s+1 .. s+m], mas o
contrário não é verdadeiro.
Rabin Karp

Assim, quando p = q é utilizada a
comparação tal como o algoritmo de
Força Bruta.

Conclui-se então, que o algoritmo de
Rabin-Karp, no pior caso, também
apresenta complexidade quadrática.
KMP: Knuth-Morris-Pratt

Idéia: usar uma função prefixo
– informar como o padrão se compara com
seus próprios deslocamentos
c b a a b a b a b a c b T
s=3
a b a b a c P
c b a a b a b a b a c b T
s’ = s+2
a b a b a c P
KMP: Knuth-Morris-Pratt





Pré-processamento: calcular prefixo
Falha na tentativa de casamento: o
algoritmo KMP consulta o vetor prefixo
para evitar deslocamentos inválidos
Faz o deslocamento
Pré-processamento: O(m)
Emparelhamento: O(n)
KMP: Knuth-Morris-Pratt
1 2 3 4 5 6 7 8 9 10
a a a b a a b a a c
a a b
a a b
a a b
a a b
Boyer-Moore



Posiciona o padrão sobre o caracter
mais a esquerda no texto
Busca da direita para a esquerda
Fase de pré-processamento:
– Heurística-do-bom-sufixo
– Heurística-do-mau-caracter

Falha na tentativa de casamento:
escolhe-se o maior valor entre elas
Boyer-Moore
Heurística-do-bom-sufixo


Possui 2 casos
Primeiro:
b a b a b a c a a c a T
s
b a c a a c P
1
...
s’ = s + 3

Segundo:
i
i+1
m
b a c a a c P
b a b a b a c b b a c T
s
a c b b a c P
1
s’ = s + 4
...
i
i+1 i+2
m
a c b b a c P
Boyer-Moore
Heurística-do-mau-caracter


Vetor BC[1 .. || ]
Cada posição do vetor armazena o
índice da posição mais a direita de um
caracter do padrão e -1 caso o caracter
não ocorra no padrão
b a b d b a c b b a c T
s
s’ = s+2
d a b b a c P
1
...
i
i+1 i+2
m
d a b b a c P
Boyer-Moore
1 2 3 4 5 6 7 8 9 10
a a a b a a b a a c
a a b
a a b
a a b
a a b
Boyer-Moore-Horspool

É uma simplificação sobre o algoritmo
de Boyer-Moore, proposta por
Horspool.

É mais eficiente, além
consideravelmente mais simples de ser
codificada.
Boyer-Moore-Horspool

Fase de pré-processamento: calcular o
vetor de deslocamento (s):
P = aca

S[‘a’] = 1 e S[‘c’] = 2
Demais posições de S são inicializadas
com 0.
Boyer-Moore-Horspool

Deslocamento na fase de
emparelhamento:
a) deslocar o padrão para a posição
onde se encontra o primeiro caracter
(da direita para a esquerda) da porção
corrente do texto T. Nessa posição i,
existe um caracter c.
Boyer-Moore-Horspool

Deslocamento na fase de
emparelhamento:
b) reiniciar a tentativa de casamento a
partir da posicão i’:
i’ = i - (S[T[c]] - 1)
Boyer-Moore-Horspool
Boyer-Moore-Horspool

Melhor caso: O(n/m). Para isto,
considera-se S[T[c]] = 0 na fórmula
i’ = i - (S[T[c]] - 1), o que garantirá o a
reinicialização do processo de tentativa
de casamento a partir posição i + 1.

Caso médio: O(n/m)

Pior caso: O(nm)
Resultados Experimentais

Arquivo de teste: 1 Gb.

Padrão: bca

Texto: gerado aleatoriamente. Cada
linha possui 1024 bytes.
Resultados Experimentais

Força Bruta
Nº de comparações: 1.115.541.632
Tempo: 4:07.02

Rabin Karp
Nº de comparações: 1.073.487.466
Tempo: 4:17.76
Resultados Experimentais

KMP
Nº de comparações: 916.030.648
Tempo: 4:04.54
Resultados Experimentais

Boyer-Moore
Nº de comparações: 387.603.550
Tempo: 3:51.40

Boyer-Moore-Horspool
Nº de comparações: 387.603.550
Tempo: 3:35.41
Conclusões




Escolha criteriosa do valor q no Rabin
Karp  muitas colisões
Desempenho KMP superior ao Rabin
Karp e Força Bruta
Deslocamentos mais eficientes:
Boyer-Moore e Boyer-Moore-Horspool
Melhor tempo de execução:
Boyer-Moore-Horspool