Concordância de Modelos (Pattern Matching)
Problema: Dada uma cadeia de carateres, detectar
a occorrência de um modelo.
Modelo: cadeia particular de carateres (Padrão).
Aplicações:
• processamento de texto
• manipulação simbólica
• tradução automática
• ...
Pattern Matching: solução trivial
Deslocar o modelo ao longo da cadeia, uma posição
de cada vez e comparar carater a carater.
{ C[1..n] ∧ P [1..m] ∧ m ≤ n }
i := 0; achou := false;
{ achou ≡ (P [1..m] ∈ C[1..i]) ∧ i ≤ n }
while not achou and (i < n) do
begin
j := i; i := i+1; k := 0;
iguais := true;
while iguais and (k < m) do
begin
k := k+1; j:= j+1;
{ iguais ≡ (C[i..j − 1] = P [1..k − 1]) }
iguais := C[j]=P[k];
{ iguais ≡ (C[i..j] = P [1..k]) }
end;
achou := iguais;
end;
{ achou ≡ (∃i ∈ [1..n] : C[i..i + m − 1] = P [1..m]) }
Note-se que:
• o contador i não deve ultrapassar n − m + 1
• o contador j depende do valor de i: j = i + k − 1
procedure pattmatch(C, P :cadeiacar; m, n
:indice; var achou :boolean; var indprim :indice);
var i, k, fim : integer;
iguais : boolean;
begin
achou := false; i := 0; fim := n-m+1
while not achou and (i < fim) do
begin
i := i+1; k := 0;
iguais := false;
while iguais and (k < m) do
begin
iguais := C[i+k]=P[k+1]
k := k+1;
end;
achou := iguais;
end ;
{ achou ≡ (∃i ∈ [1..n − m + 1] : C[i..i + m − 1] =
P [1..m]) }
if achou
then indprim := i
else indprim := 0;
end;
Exercı́cio:
• Escrever uma versão para contar o número total
de ocorrências do modelo na cadeia.
• Fazer a verificação formal do algoritmo.
Análise de Complexidade
Operação básica: comparação entre carateres.
Melhor dos casos:
1. Se m ≤ n2 , então m < n − m + 1, logo,
BC (n, m) = m se P [1..m] = C[1..m]
2. Se m > n2 , então BC (n, m) = n − m + 1 se
P [1] 6∈ C[1..n]
Pior dos casos:
para cada i, todos os carateres de p concordam
menos o último,
WC (n, m) = (n − m + 1) ∗ m
Exemplo dum pior dos casos:
1
2
3
...
4
a
a
a
a
a
a
a
b
a
a
a
a
...
n
a
a
a
a
a
b
Casos ineficientes: concordâncias parciais
Concordâncias parciais implicam repetições
dentro do modelo =⇒ necessário um
algoritmo que use conhecimento parcial!
...
a
b
c
a
b
c
a
b
d
a
b
c
a
b
d
a
b
c
1
3
?
6
a
b
m
?
Após C[i] = P [6] fazer a comparação C[i] = P [3]
pois P [1] = P [4] e P [2] = P [5]
c
Algoritmo de Knuth-Morris-Pratt
Precisamos de um registo de repetições
P:
a
b
c
a
b
d
a
b
c
R:
0
0
0
1
2
0
1
2
3
• inicializar R[1..m] a zero;
• inicializar k a 1;
• para todo o i ∈ {2, . . . , m} fazer
- se P [i] = P [k]
- então
R[i] ← k
incrementar k
- senão
R[i] ← 0
k←1
{ R[j] = l =⇒ P [l] = P [j]) }
• Como usar o registo de repetições?
C:
a
b
c
a
b
c
a
b
d
P:
a
b
c
a
b
d
a
b
c
1
2
3
4
5
6
7
8
9
0
0
0
1
2
0
1
2
3
R:
a
b
c
Para voltar ao primeiro carater diferente no padrão
anterior fazer k ← R[k − 1] + 1 e comparar
?
C[i] = P [k]
• Que fazer após uma concordância total?
C:
a
b
c
a
b
c
P:
a
b
c
a
b
c
1
2
3
4
5
6
0
0
0
1
2
3
R:
a
b
d
a
b
Avançar os contadores i e k;
Como k = 7 > m = 6 faz-se k ← R[m] + 1 e
?
compara-se C[i = 7] = P [k = 4]
c
function KMP(C, P :cadeiacar; m, n :indice) :integer;
var i, k, numconc : integer;
R : array[1..m] of integer;
procedure construirR;
var i, k : integer;
begin
for k:=1 to m do R[i] := 0;
k := 1;
for i:=2 to m do
if P[i]=P[k]
then begin
R[i] := k; k := k+1;
end else k := 1;
end;
begin { Programa principal do KMP }
construirR; numconc := 0; i := 1; k := 1;
while i < n do
begin
if C[i]=P[k]
then begin
i := i+1; k := k+1;
if k > m
then begin
numconc := numconc+1;
k :=R[k-1]+1;
end
end else if k = 1;
then i := i+1
else k :=R[k-1]+1;
end;
end;
Análise de Complexidade
Pior dos casos: m + 1 + 2 n ⇒
WC (n, m) = O(m + n)
Autómatos Finitos
Um autómato finito A = (Q, Σ, g, I, F ) é um
quintuplo onde:
• Q é um conjunto finito de estados;
• Σ é um alfabeto finito;
• g : Σ × Q −→ Q diz-se relação de transição;
• I ⊂ Q é um conjunto de estados iniciais;
• F ⊂ Q é um conjunto de estados finais.
Exemplo: Autómato reconhecedor da frase aabc
Q = {0, 1, 2, 3, 4};
Σ = {a, b, c};
I = {0};
F = {4};
g
0
1
2
3
a
1
2
2
1
b
0
0
3
0
c
0
0
0
4
4