Embed Size (px)
Citation preview
Algoritmos e ModelaçãoComputacional
Paulo MateusMEBiom – LMAC
2018
Pesquisa de padrões4
Pesquisa de padrões
O problema da pesquisa de padrões consiste em receber dois vectores T e P com entradas
valores em Zn (o alfabeto) e determinar se P ocorre em T . A solução mais simples (dita
naive) consiste em percorrer todas as entradas de T e verificar em cada uma delas se P
ocorre.
Desenvolva em Java essa solução.
Qual a complexidade desta?
Poderemos fazer melhor?
Autómatos finitos 5
Uma das melhores soluções baseia-se em autómatos finitos:
Um autómato finito M é um tuplo M = (Q, q0, A,⌃, �) onde:
• Q é um conjunto finito de estados;
• q0 2 Q é o estado inicial;
• A ✓ Q é o conjunto de estado finais (ditos estados de aceitação);
• ⌃ é o alfabeto de entrada finito (no nosso caso Zn);
• � : Q⇥ ⌃ ! Q é a função de transição;
Ver exemplo no quadro.
Autómatos finitos6
O conjunto das sequências com alfabeto ⌃ é denotado por ⌃⇤(onde ⇤ é chamada a estrela
de Kleene). A sequência vazia é denotada por ".
A função de transição � estende-se para sequências da seguinte forma:
• �⇤(q, ") = q;
• �⇤(q, wa) = �(�⇤(q, w), a).
O conjunto de sequências aceites por um autómato M ,
LM = {w 2 ⌃⇤ : �⇤(q0, w) 2 A},
é chamado a linguagem aceite pelo autómato.
As linguagem aceites pelo autómatos são chamadas linguagens regulares. Chama-se a
atenção que nem todas as linguagens são regulares.
Exemplo
L={w: w tem pelo menos 2 a’s e um número ímpar de b’s}
6
O conjunto das sequências com alfabeto ⌃ é denotado por ⌃⇤(onde ⇤ é chamada a estrela
de Kleene). A sequência vazia é denotada por ".
A função de transição � estende-se para sequências da seguinte forma:
• �⇤(q, ") = q;
• �⇤(q, wa) = �(�⇤(q, w), a).
O conjunto de sequências aceites por um autómato M ,
LM = {w 2 ⌃⇤ : �⇤(q0, w) 2 A},
é chamado a linguagem aceite pelo autómato.
As linguagem aceites pelo autómatos são chamadas linguagens regulares. Chama-se a
atenção que nem todas as linguagens são regulares.
Lema da Bombagem 7
Lema 1 (Lema da Bombagem). Seja L ✓ ⌃⇤uma linguagem regular. Existe p 2 N tal
que para todo o w 2 L com |w| > p, existem x, y, z tal que w = xyz, |y| � 1 e |xy| p
e para todo o k 2 Nxy
kz 2 L.
Mostre que L = {0n1n : n 2 N} não é regular.
Autómato vs pesquisa de padrões8
Autómato para pesquisa de padrões
Dado um padrão P = p1 . . . pm 2 ⌃⇤considere-se o autómato MP com alfabeto ⌃ tal que
• Q = 0, . . . ,m;
• q0 = 0;
• A = {m};
• �(i, a) = �P (Pia) onde Pi = P [1 . . . i] e �P : ⌃⇤ ! Q
�P (x) = max{k : Pk é sufixo de x}
Exemplo
P=ababaca
Todas as restantes transições são para 0
Correção 9
Teorema 1 O padrão P ocorre em T se existir um prefixo T0de T que é aceite por MP .
Prova: Por indução é fácil de provar que �⇤(q0, T 00) = �P (T 00) para qualquer prefixo T
00
de T . Mais, P ocorre em T se existir um prefixo T0de T cujo sufixo é P . Neste caso
�P (q0, T 0) = m 2 A por definição de �P e logo T0 2 LMP . ⇤
Exercício: Construa o Algoritmo de pesquisa de padrões baseado em autómatos finitos em
Java.
Complexidade
• É necessário construir a tabela !• Qual é a complexidade desta construção?
• Temos que preencher |Σ|×# entradas• Para cada entrada temos que verificar qual o
maior sufixo que é prefixo de P• Uma verificação é O(m)• Temos de fazer m verificações• A operação para calcular cada entrada é O(m2)
• A complexidade de construir a tabela é O(m3|Σ|)
Encontrar o padrão
• Após a construção do autómato• Basta percorrer o texto T e verificar
se o autómato chega ao estado final• Ou seja o tempo de encontrar o
padrão é O(n)
• Logo, o tempo total éO(n+m3|Σ|)
É possível melhorar este tempo?
iTq
Knuth-Morris-Pratt10
Knuth-Morris-Pratt
Um autómato tem excesso de estrutura! Seja P um padrão de tamanho m, basta considerar
a função função de prefixo ⇡ : {1, . . . ,m} ! Zm onde
⇡(q) = max{k : k < q e Pk é sufixo de Pq}
com Pi = P [1 . . . i].
Motivação12
12
Basta saber se houve match m ou mismatch s
12
Autómato vs Match m and MisMatch s
Knuth-Morris-Pratt Algorithm
Let ⇡[i ] be the largest integer smaller than i such thatP[1..⇡[i ]] (longest prefix) is a su�x of P[1..i ].
Pedro Ribeiro (DCC/FCUP) String Matching 2015/2016 13 / 43
Podemos definir um autómato desta forma:! "#, % = "'(#)! "#, * = "#+, i<m! "-,* = "' - +,
Knuth-Morris-Pratt Algorithm
Let ⇡[i ] be the largest integer smaller than i such thatP[1..⇡[i ]] (longest prefix) is a su�x of P[1..i ].
Pedro Ribeiro (DCC/FCUP) String Matching 2015/2016 13 / 43
Algoritmo de KMP
Assumindo que temos pi
Variável:• i varre T (text), 0≤i<n• j tamanho do prefixo de P (pattern) encontrado
Complexidade :- Note que j>=0 e j<n é um invariate do ciclo
pois j é incrementado no máximo em cada iterada- Como pi[j]>=0, j é decrementado em todo o ciclo
no máximo n vezes
Logo a complexidade é O(n) + complexidade de calcular pi
14
/* Encontra a primeira ocorrência do padrão no texto*/public boolean match() {
int j = 0;if (text.length == 0) return false;
for (int i = 0; i < text.length; i++) {while (j > 0 && pattern[j] != text[i]) {
j = pi[j - 1];}if (pattern[j] == text[i]) j++;if (j == pattern.length) {
matchPoint = i - pattern.length + 1;return true;
}}return false;
}
Calcular pi
15
/* Calcula o vector pi*/
private void computepi() {int j = 0;pi[0]=0;for (int i = 1; i < pattern.length; i++) {
while (j > 0 && pattern[j] != pattern[i]) {j = pi[j - 1];
}if (pattern[j] == pattern[i]) {
j++;}pi[i] = j;
}}
}
17
Vamos começar por mostrar que o computepi está correcta.
Seja ⇡⇤(q) = {q, ⇡(q), ⇡2(q), . . . , ⇡t(q)} onde t é tal que ⇡
t(q) = 0.
Lema 2 Seja P um padrão de tamanho m então ⇡⇤(q) = {k : Pk é sufixo de Pq} para
todo o q = 1 . . .m.
Lema 3 Seja P um padrão de tamanho m se ⇡(q) > 0 então ⇡(q)� 1 2 ⇡⇤(q � 1).
Seja Eq�1 = {k : k 2 ⇡⇤(q � 1) e P [k + 1] = P [q]} para q = 2 . . .m.
Lema 4 Se Eq�1 = ; então ⇡(q) = 0. Se Eq�1 6= ; então ⇡(q) = 1 + maxEq�1.
17
Vamos começar por mostrar que o computepi está correcta.
Seja ⇡⇤(q) = {q, ⇡(q), ⇡2(q), . . . , ⇡t(q)} onde t é tal que ⇡
t(q) = 0.
Lema 2 Seja P um padrão de tamanho m então ⇡⇤(q) = {k : Pk é sufixo de Pq} para
todo o q = 1 . . .m.
Lema 3 Seja P um padrão de tamanho m se ⇡(q) > 0 então ⇡(q)� 1 2 ⇡⇤(q � 1).
Seja Eq�1 = {k : k 2 ⇡⇤(q � 1) e P [k + 1] = P [q]} para q = 2 . . .m.
Lema 4 Se Eq�1 = ; então ⇡(q) = 0. Se Eq�1 6= ; então ⇡(q) = 1 + maxEq�1.
A Complexidade é como anteriormente mas agora pesquisamos o padrão no padrão assumindo um mismatch em cada passo! Ou seja é O(m)
