Distância Mínima de Edição
Profa. Sandra de Amo
Bacharelado em Ciência da
Computação - UFU
Problema de otimização a resolver
Dadas duas palavras w1 e w2 determinar o quão próximas elas são.
Que medida utilizar para determinar a distância entre duas palavras ?
Medida natural e intuitiva: o custo de alinhar as palavras, isto é, o
custo de colocar uma sobre a outra, combinando letra a letra.
Exemplo:
w1 = SNOWY
w2 = SUNNY
• Qual o custo de transformar w1 em w2 ?
• Existem diversas maneiras de fazer isto, cada uma tendo um custo.
• Precisamos encontrar a maneira com custo mínimo
Exemplos de transformações e
seus respectivos custos
S
_ N O
W Y
S
U N N
_
Y
_ S
N O
S U N
_
W
_ Y
_
N Y
= match !!
= match !!
= inserção (I)
=1
= inserção (I)
=2
= deleção (D)
=1
= deleção (D)
=2
= substituição (S)
=1
Custo = 3
= substituição (S)
=1
Custo = 5
Distância de Edição
• Dist_edit (w1,w2) = menor custo de se transformar
w1 em w2
• Método “força bruta” para determinar Dist_edit
– Todo problema de otimização tem solução do tipo “força bruta”
• Considera-se todas as possiveis maneiras de se transformar
w1 em w2
• Calcula-se o custo de cada maneira
• Considera-se o menor custo
• Solução eficiente: usando Programação Dinâmica !
Aplicações
• Como corrigir automaticamente uma palavra w mal escrita ?
– Verifica-se em um dicionário se a palavra w existe.
– Caso não exista, constrói-se uma lista de palavras do dicionário que
estão próximas (no dicionário) = [ w1, w2, ... , wn]
– Calcula-se para cada wi, dist_edit(w, wi)
– Sugere-se o wi com menor dist_edit(w,wi)
• Exemplo:
w = graf
Palavras próximas: grafo, girafa, garra, grafite
Qual a mais próxima ?
• Como determinar se um determinado texto w1 é plágio de um outro
texto w2 ?
– Se dist_edit(w1,w2) < K, onde K é dado
Aplicações
• Biologia Computacional:
– Como alinhar duas sequências de nucleotídeos ?
Resultado do alinhamento
Problema de otimização a resolver
Problema P:
Input: dois strings x = (x1,...,xn), y = (y1,...,ym)
Output: x’ = (x’1,...,x’k), y’ = (y’1,...,y’k), k ≥ m, tal que custo(x’,y’) é
minimo (= dist_edit(x,y) )
x’1 x’2
y’1 y’2
x’3
y’3
x’k
y’k
Custo(x’,y’) = Σi=1k custo(x’i,y’i)
Custo(xi,yi) = 1 se x’i =‘-’ e y’i = yp (inserção de caracter yp)
ou x’i = xp e y’i = ‘-’ (remoção de carater xp)
ou x’i  y’i e ambos  ‘-’
Custo(xi,yi) = 0 se x’i = y’i
Como projetar o algoritmo de PD para
resolver o problema P ?
Problema P
• E(n,m) = custo mínimo do alinhamento
• Subproblemas E(i,j), com i ≤ n, j ≤ m
• Como ordenar os subproblemas ?
• Como resolver completamente cada subproblema, em
ordem crescente, executando uma função que envolve
os resultados dos subproblemas já resolvidos
anteriormente ?
0
0
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
I
A
L
E(11,10) = custo minimo de um alinhamento
3 possibilidades de alinhamento
0
1)
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
0
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
I
A
L
3 possibilidades de alinhamento
0
1)
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
0
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
I
A
L
Custo = diff(x[11], y[10] ) +
+ CUSTO de alinhar prefixos (EXPONENTIA, POLYNOMIA) =
= 0 + E(10, 9)
3 possibilidades de alinhamento
0
2)
0
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
A
L
I
-
3 possibilidades de alinhamento
0
2)
0
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
A
L
I
-
Custo = 1 + CUSTO de alinhar prefixos (EXPONENTIA, POLYNOMIAL) =
= 1 + E(10, 10)
3 possibilidades de alinhamento
0
3)
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
-
0
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
I
A
L
3 possibilidades de alinhamento
0
3)
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
-
0
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
I
A
L
Custo = 1 + CUSTO de alinhar prefixos (EXPONENTIAL, POLYNOMIA) =
= 1 + E(11, 9)
Fórmula
E(m,n) = min {diff(x[m],y[n]) + E(m-1,n-1), 1 + E(m,n-1), 1+ E(m-1,n) }
primeiro alinh.
seg. alinh.
terc. alinh.
Em geral:
E(i,j) = min { diff(x[i],y[j]) + E(i-1,i-1), 1 + E(i,j-1), 1+ E(i-1,j) }
Em que ordem resolver os
subproblemas ?
Soluções dos subproblemas
Algoritmo e sua complexidade
Complexidade = O(m) + O(n) + O(m.n) = O(m.n)
Um alinhamento com custo mínimo
=6
E
X
- -
P
O
N
E
N
-
T
P
O
L
Y
N
O
M
I
I
A
L
A
L
Como obter todos os alinhamentos com custo minimo
só olhando para o quadro dos custos ?