Casamento de Padrões - DCC

Transcrição

Casamento de Padrões
Ricardo Terra
rterrabh [at] gmail.com
Ricardo Terra (rterrabh [at] gmail.com)
Fevereiro, 2013
1 / 34
CV
Nome: Ricardo Terra
Email: rterrabh [at] gmail.com
www: ricardoterra.com.br
Twitter: rterrabh
Lattes: lattes.cnpq.br/ 0162081093970868
Ph.D. (UFMG/UWaterloo),
Post-Ph.D. (INRIA/Université Lille 1)
Background
Acadêmico : UFLA (desde
Profissional : DBA Eng.
2014),
(1 ano ),
UFSJ (1 ano ), FUMEC (3 anos ), UNIPAC (1 ano ), FAMINAS (3 anos )
Synos (2 anos ), Stefanini (1 ano )
Fevereiro, 2013
2 / 34
Introdução
Fevereiro, 2013
3 / 34
Introdução
Em primeiro lugar, o que é “Casamento de Padrões”?
Em suma, consiste em encontrar ocorrências de um certo
padrão em uma sequência de elementos
Fevereiro, 2013
4 / 34
Introdução
Em segundo lugar, por que estudar isto?
Fevereiro, 2013
5 / 34
Introdução
Em segundo lugar, por que estudar isto?
Se isso não é importante, o Google também não é!
Fevereiro, 2013
5 / 34
Introdução
Ainda não convencido?
Fevereiro, 2013
6 / 34
Introdução
Ainda não convencido?
O que seria do Bing sem o Google?
(veja url)
Fevereiro, 2013
6 / 34
Introdução
Nada ainda?
Fevereiro, 2013
7 / 34
Introdução
Nada ainda?
Processamento de texto, sequenciamento de DNA,
representação de imagens...
Fevereiro, 2013
7 / 34
Introdução
Pronto!
Ideia: ok
Motivação: ok
Conhecimento: a partir de agora...
Nesta aula: Casamento de Cadeias (String Matching)
Casamento Exato
Definições
Alfabeto, string, padrão, formalização do problema...
Algoritmos
Categorias
Naive, AF, Shift-And e KMP
Casamento Aproximado (uma visão geral)
Fevereiro, 2013
8 / 34
Casamento Exato
Fevereiro, 2013
9 / 34
Casamento Exato
Definições
Texto: arranjo T[1..n]
Padrão: arranjo P[1..m], m ≤ n
Seus elementos gerados a partir de um Alfabeto finito Σ
e.g., Σ = {0,1} ou Σ = {a,b,...,z}
T e P são chamados de strings
Fevereiro, 2013
10 / 34
Casamento Exato
Definições
Texto: arranjo T[1..n]
Padrão: arranjo P[1..m], m ≤ n
Seus elementos gerados a partir de um Alfabeto finito Σ
e.g., Σ = {0,1} ou Σ = {a,b,...,z}
T e P são chamados de strings
Formalização do Problema
Dois strings
Texto T de comprimento |T| = n
Padrão P de comprimento |P| = m
m n
Objetivo: saber as ocorrências de P em T
Fevereiro, 2013
10 / 34
Casamento Exato
Exemplo mega simples
Texto: aabaabc
1
2
3
4 5
6
7
Padrão: ab
Alfabeto: Σ = {a,b, c}
Nosso objetivo: 2 e 5
Aplicações mega simples
Comando / do Vi
i.e., função básica de Localizar em editores de texto
Fevereiro, 2013
11 / 34
Casamento Exato
Categorias de Algoritmos
Padrão e texto não são pré-processados
O(m n) [espaço O(1)]
Algoritmo Naive
Fevereiro, 2013
12 / 34
Casamento Exato
Algoritmo Naive
Padrão pré-processado
O(n) [espaço O(m |Σ|)]
Algoritmo AF, Shift-And e KMP
Fevereiro, 2013
12 / 34
Casamento Exato
Algoritmo Naive
Padrão e texto são pré-processados
Uso de índices (e.g., arquivos invertidos, árvores trie e Patricia)
Bases semi-estáticas
O(lg n)1
1 lg
[espaço O(n)]
n = log2 n
Fevereiro, 2013
12 / 34
Casamento Exato
Algoritmo Naive
Padrão e texto são pré-processados
Uso de índices (e.g., arquivos invertidos, árvores trie e Patricia)
Bases semi-estáticas
O(lg n)1
1 lg
[espaço O(n)]
n = log2 n
Fevereiro, 2013
12 / 34
Algoritmo Naive
Algoritmo Naive (padrão e texto não são pré-processados)
Referenciado na literatura também como Força Bruta
Mais simples
Tentar casar o padrão com todas as subcadeias do texto
P[1..m] = T[s+1..s+m] para n-m+1 possíveis valores de s
Pior desempenho
O(nm)
Fevereiro, 2013
13 / 34
Algoritmo Naive
Pseudocódigo
Exemplo:
( T = acaabc, P = aab, n-m+1=4 )
Fevereiro, 2013
14 / 34
Algoritmo Naive
Pseudocódigo
Exemplo:
Fevereiro, 2013
14 / 34
Algoritmo Naive
Pseudocódigo
Exemplo:
Fevereiro, 2013
14 / 34
Algoritmo Naive
Pseudocódigo
Exemplo:
Fevereiro, 2013
14 / 34
Algoritmo Naive
Pseudocódigo
Exemplo:
Fevereiro, 2013
14 / 34
Algoritmo Naive
Por que é ineficiente?
(para não dizer ruim)
Não aprende!
Isto é, informação obtida do texto para um valor de s é
ignorada para os outros valores de s
e.g., se P = aaab e s=0 é válida
Implica s=1 ou 2 ou 3 não são válidos pois T[4]=b
Mas, ele testa mesmo assim!
Os próximos algoritmos tornam efetivo o uso desse tipo de
informação e, por isso, têm melhor desempenho
Fevereiro, 2013
15 / 34
Algoritmos baseados em AF
Algoritmos baseados em Autômatos Finitos (padrão pré-processado)
Autômato é um modelo de computação (máquina) cujo
propósito principal é reconhecer linguagens
Um autômato finito M é uma quíntupla (Q,q0 ,A,Σ,δ) onde
Q é um conjunto finitos de estados
q0 ∈ Q é o estado inicial
A ⊆ Q é o conjunto de estados finais
Σ é um alfabeto de entrada finito
δ é uma função de transição Q x Σ → Q
Fevereiro, 2013
16 / 34
Exemplo de um AFD
Quíntupla (Q,q0 ,A,Σ,δ)
Q = {q1 , q2 , q3 }
q0 = q1
A = {q2 }
Σ = {0, 1}
δ(q1 , 0) = q1 ,
δ(q2 , 0) = q3 ,
δ(q3 , 0) = q2 ,
δ(q1 , 1) = q2
δ(q2 , 1) = q2
δ(q3 , 1) = q2
Fevereiro, 2013
17 / 34
Exemplo de um AFD
AFD (um estado ativo)
AFND, AFND-λ (n estados ativos)
Quíntupla (Q,q0 ,A,Σ,δ)
Q = {q1 , q2 , q3 }
q0 = q1
A = {q2 }
Σ = {0, 1}
δ(q1 , 0) = q1 ,
δ(q2 , 0) = q3 ,
δ(q3 , 0) = q2 ,
δ(q1 , 1) = q2
δ(q2 , 1) = q2
δ(q3 , 1) = q2
Fevereiro, 2013
17 / 34
Ideia
(ou sacada)
1
Construir um AF para o padrão P [O(m |Σ|)]
2
O AF consome caractere a caractere do texto T [Θ(n)]
Se estado atual = estado final, então ocorrência do padrão
Pseudocódigo
Fevereiro, 2013
18 / 34
Exemplo:
( T = abababacaba, P = ababaca)
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Exemplo:
Fevereiro, 2013
19 / 34
Algoritmo Shift-And
Algoritmo Shift-And (padrão pré-processado)
Usa o conceito de paralelismo de bit
Bom desempenho devido às operações sobre bits [O(1)]
Ideia
1
Construção de uma tabela para armazenar máscara de
bits para cada caractere de P [O(m2 )]
e.g., se P=abba, então M[a]=1001
Pois, a aparece nas posições 1 e 4
2
Cada caractere lido (T) atualiza a máscara de bits R’ [Θ(n)]
Se o caractere casar com o padrão, um shift é realizado
Se a R’m = 1, uma ocorrência do padrão
Caso contrário, R’ = 0m
Fevereiro, 2013
20 / 34
Algoritmo Shift-And
M[t]
M[e]
M[s]
Exemplo:
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
0
1
0
( T = "os testes ", P = teste)
Texto
o
s
(R >>1) | 10m−1
1 0 0 0 0
0
0
R’
0
0
0
t
e
s
t
e
s
Fevereiro, 2013
21 / 34
Algoritmo Shift-And
M[t]
M[e]
M[s]
Exemplo:
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
0
1
0
Texto
o
s
(R >>1) | 10m−1
1 0 0 0 0
1 0 0 0 0
0
0
0
0
R’
0
0
0
0
0
0
t
e
s
t
e
s
Fevereiro, 2013
21 / 34
Algoritmo Shift-And
M[t]
M[e]
M[s]
Exemplo:
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
0
1
0
Texto
o
s
(R >>1) | 10m−1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
0
0
0
0
0
0
R’
0
0
0
0
0
0
0
0
0
t
e
s
t
e
s
Fevereiro, 2013
21 / 34
Algoritmo Shift-And
M[t]
M[e]
M[s]
Exemplo:
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
0
1
0
Texto
o
s
t
e
s
t
e
s
(R >>1) | 10m−1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
0
0
0
1
0
0
0
0
R’
0
0
0
0
0
0
0
0
0
0
0
0
Fevereiro, 2013
21 / 34
Algoritmo Shift-And
M[t]
M[e]
M[s]
Exemplo:
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
0
1
0
Texto
o
s
t
e
s
t
e
s
(R >>1) | 10m−1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 1 0 0 0
0
0
0
1
0
0
0
0
0
1
R’
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Fevereiro, 2013
21 / 34
Algoritmo Shift-And
M[t]
M[e]
M[s]
Exemplo:
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
0
1
0
Texto
o
s
t
e
s
t
e
s
(R >>1) | 10m−1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 1 0 0 0
1 0 1 0 0
0
0
0
1
0
0
0
0
0
0
1
0
R’
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
Fevereiro, 2013
21 / 34
Algoritmo Shift-And
M[t]
M[e]
M[s]
Exemplo:
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
0
1
0
Texto
o
s
t
e
s
t
e
s
(R >>1) | 10m−1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 1 0 0 0
1 0 1 0 0
1 0 0 1 0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
R’
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
Fevereiro, 2013
21 / 34
Algoritmo Shift-And
M[t]
M[e]
M[s]
Exemplo:
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
0
1
0
Texto
o
s
t
e
s
t
e
s
(R >>1) | 10m−1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 1 0 0 0
1 0 1 0 0
1 0 0 1 0
1 1 0 0 1
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
1
R’
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
Fevereiro, 2013
21 / 34
Algoritmo Shift-And
M[t]
M[e]
M[s]
Exemplo:
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
0
1
0
Texto
o
s
t
e
s
t
e
s
(R >>1) | 10m−1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 1 0 0 0
1 0 1 0 0
1 0 0 1 0
1 1 0 0 1
1 0 1 0 0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
0
R’
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
Fevereiro, 2013
21 / 34
Algoritmo Shift-And
M[t]
M[e]
M[s]
Exemplo:
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
0
1
0
Texto
o
s
t
e
s
t
e
s
(R >>1) | 10m−1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 1 0 0 0
1 0 1 0 0
1 0 0 1 0
1 1 0 0 1
1 0 1 0 0
1 0 0 0 0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
R’
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
Fevereiro, 2013
21 / 34
Algoritmo Knuth-Morris-Pratt
Algoritmo Knuth-Morris-Pratt (padrão pré-processado)
Algoritmo utiliza informação já obtida para avançar em s
Ao contrário do Naive que sempre faz s = s + 1 [O(n m)],
KMP calcula o s de forma a evitar testes desnecessários [Θ(n)]
E, ainda, evita a computação da função transição δ
Por meio de uma arranjo auxiliar π[1..m]
pré-computado em Θ(m)
Em algoritmos por AF, isso é pré-computado em O(m|Σ|)
Fevereiro, 2013
22 / 34
Exemplo:
( P = ababaca)
Pseudocódigo
Compute-Prefix-Function(P)
i
P[i]
π[i]
1
a
2
b
3
a
4
b
5
a
6
c
Fevereiro, 2013
7
a
23 / 34
Exemplo:
( P = ababaca)
Pseudocódigo
i
P[i]
π[i]
1
a
0
2
b
3
a
4
b
5
a
6
c
Fevereiro, 2013
7
a
23 / 34
Exemplo:
( P = ababaca)
Pseudocódigo
i
P[i]
π[i]
1
a
0
2
b
0
3
a
4
b
5
a
6
c
Fevereiro, 2013
7
a
23 / 34
Exemplo:
( P = ababaca)
Pseudocódigo
i
P[i]
π[i]
1
a
0
2
b
0
3
a
1
4
b
5
a
6
c
Fevereiro, 2013
7
a
23 / 34
Exemplo:
( P = ababaca)
Pseudocódigo
i
P[i]
π[i]
1
a
0
2
b
0
3
a
1
4
b
2
5
a
6
c
Fevereiro, 2013
7
a
23 / 34
Exemplo:
( P = ababaca)
Pseudocódigo
i
P[i]
π[i]
1
a
0
2
b
0
3
a
1
4
b
2
5
a
3
6
c
Fevereiro, 2013
7
a
23 / 34
Exemplo:
( P = ababaca)
Pseudocódigo
i
P[i]
π[i]
1
a
0
2
b
0
3
a
1
4
b
2
5
a
3
6
c
0
Fevereiro, 2013
7
a
23 / 34
Exemplo:
( P = ababaca)
Pseudocódigo
i
P[i]
π[i]
1
a
0
2
b
0
3
a
1
4
b
2
5
a
3
6
c
0
Fevereiro, 2013
7
a
1
23 / 34
Exemplo:
( P = ababaca)
Pseudocódigo
i
P[i]
π[i]
1
a
0
2
b
0
3
a
1
4
b
2
5
a
3
6
c
0
Fevereiro, 2013
7
a
1
23 / 34
Exemplo:
( P = ababaca)
s’ = s + (q s’ = s + (5 s’ = s + (5
s’ = s +
Pseudocódigo
π[q])
π[5])
- 3)
2
i
P[i]
π[i]
1
a
0
2
b
0
3
a
1
4
b
2
5
a
3
6
c
0
Fevereiro, 2013
7
a
1
23 / 34
Exemplo:
( P = ababaca)
s’ = s + (q s’ = s + (5 s’ = s + (5
s’ = s +
Pseudocódigo
π[q])
π[5])
- 3)
2
i
P[i]
π[i]
1
a
0
2
b
0
3
a
1
4
b
2
5
a
3
6
c
0
Fevereiro, 2013
7
a
1
23 / 34
Algoritmos baseados em Janelas Deslizante
Algoritmos Boyer-Moore (BM), BMH e BMHS (padrão pré-processado)
Enfoque diferente
Usam uma janela de tamanho m que desliza ao longo do
texto T (ao invés de ler caractere-a-caractere)
Para cada posição desta janela, o algoritmo realiza
comparações no sentido da direita para a esquerda
Se não ocorrer desigualdade, uma ocorrência do padrão
Senão, o algoritmo calcula o deslocamento
BM propõe duas heurísticas: ocorrência e casamento
O que difere entre o BM, BMH e BMHS
Fevereiro, 2013
24 / 34
Casamento Aproximado
Fevereiro, 2013
25 / 34
Nem sempre procuramos de forma “exata”...
Fevereiro, 2013
26 / 34
Nem sempre procuramos de forma “exata”...
Observe que o Google já corrigiu!
Fevereiro, 2013
26 / 34
E, às vezes, o Google apenas recomenda...
Fevereiro, 2013
27 / 34
E, às vezes, o Google apenas recomenda...
Por que será?
Fevereiro, 2013
27 / 34
Definição
Existem variações com relação ao casamento exato
A mais importante é aquela que permite “alterações” no
que você procura (i.e., no padrão P)
Por exemplo, ao procurar este, talvez pesquisar também:
esse, essa, esta, isso, nessa...
Distância de edição
É o número de operações (inserção, substituição ou retirada de
caracteres) para transformar um string x em um string y
ed(“este”,“esse”)=1
ed(“este”,“isso”)=3
Fevereiro, 2013
28 / 34
Definição
Existem variações com relação ao casamento exato
A mais importante é aquela que permite “alterações” no
que você procura (i.e., no padrão P)
Por exemplo, ao procurar este, talvez pesquisar também:
esse, essa, esta, isso, nessa...
Distância de edição
Google
É o número de operações (inserção, substituição ou retirada de
caracteres) para transformar um string x em um string y
ed(“este”,“esse”)=1
ed(“este”,“isso”)=3
Fevereiro, 2013
28 / 34
Formalização do Problema
Dois strings
Texto T de comprimento |T| = n
Padrão P de comprimento |P| = m
mn
Objetivo: saber as ocorrências de P’ em T onde
ed(P,P’)=k
0 < k < m
k = 0 → casamento exato
k = m → aí já pode mudar tudo (sem sentido algum)
Fevereiro, 2013
29 / 34
Algoritmos
Não são triviais
Basicamente modificações em algoritmos conhecidos
Shift-And
Não serão abordados nessa disciplina
Provavelmente abordados em TPs
Fevereiro, 2013
30 / 34
Considerações Finais
Fevereiro, 2013
31 / 34
Considerações Finais
Para concluir, viu-se nesta aula:
Casamento de Cadeias
Problema, motivação, notação e terminologia
Casamento Exato (foco)
Naive, AF, Shift-And e KMP
Casamento Aproximado (uma visão geral)
Próxima Aula
Lista de exercícios sobre casamento exatos
Enunciado do TP
Fevereiro, 2013
32 / 34
Referências
Thomas Cormen et al. Introduction To Algorithms. 3 ed., 2009.
Nívio Ziviani. Projeto de Algoritmos: com Implementações
em Pascal e C. 2 ed., 2004.
Fevereiro, 2013
33 / 34
Obrigado!!!
Fevereiro, 2013
34 / 34
Possíveis Questionamentos
Algoritmo BM – Heurística Ocorrência
Alinha a posição no texto que causou a colisão com o
primeiro caractere no padrão que casa com ele
Exemplo:
( T = aabcaccacbac, P = cacbac )
Fevereiro, 2013
34 / 34
Algoritmo BM – Heurística Casamento
Ao mover o padrão para a direita, faça-o casar com o
pedaço do texto anteriormente casado
Exemplo:
( T = aabcaccacbac, P = cacbac )
Fevereiro, 2013
34 / 34
Arquivo Invertido (padrão e texto são pré-processados)
Contém vocabulário e ocorrências
Lei de Heaps (V = Knβ = O(nβ ))
Fevereiro, 2013
34 / 34
Arquivo Invertido – Pesquisa em três passos
1
Pesquisa no vocabulário: palavras e padrões da consulta
são isoladas e pesquisadas no vocabulário
2
Recuperação das ocorrências: as listas de ocorrências das
palavras encontradas no vocabulário são recuperadas
3
Manipulação das ocorrências: as listas de ocorrências são
processadas para tratar frases, proximidade, ou operações
booleanas
Fevereiro, 2013
34 / 34
Arquivo Invertido usando Trie – Exemplo
Fevereiro, 2013
34 / 34

Casamento de Padrões - DCC

Transcrição

Documentos relacionados

emanuelle missura

Dicas para os noivos para a escolha do DJ

Falando Sério Sobre o Namoro Cristão! - Texto I

modelo de petição_divórcio com partilha1

Sim, aceito! Bem-Vindos ao Caribe

2015-05-24-Ricardo Matos-A Essencia do Casamento 4

Manual de Casamentos no Cristo Redentor do Corcovado Rio de

Estilo de Casamento

Família - Igreja Edificando

Linhas de Pesquisa