文档介绍：最小编辑距离算法
Minimum Edit Distance
詹卫东
北京大学中文系
编辑距离
编辑前字符串 s
编辑距离定义为
编辑后字符串 t “”
“编辑操作的次数”
编辑操作p:插入、删除、替换
源文:She is a star with the pany.
机器译文:她是与剧院公司的一颗星。计算机器译文
参考译文:她是剧团的明星。跟正确答案之
间的距离
编辑距离:6
删除次数(4次): 与公司一颗
替换次数(2次): 剧院Æ剧团星Æ 明星
如何计算最小编辑距离
s o t 编辑操作1
原始串 s o t
Æ s t o t (,1分,累计1分)
目标串 s t o p
Æ s t o p (,2分,累计3分)
插入操作的权值编辑距离:3
(insertCost):1
s o t 编辑操作2
删除操作的权值
Æ s t t (,2分,累计2分)
(deleteCost):1
替换操作的权值Æ s t o (,2分,累计4分)
(substituteCost):2 Æ s t o p (,1分,累计5分)
编辑距离:5
最小编辑距离计算:动态规划
D(0, 0) = 0 i, 目标串字符位置
D(i, 0) = insertCost * i j, 原始串字符位置
D(0, j) = deleteCost * j
D(i-1, j) + insertCost( targeti )
D(i, j) = min D(i-1, j-1) + substituteCost( sourcej , targeti )
D(i, j-1) + deleteCost( sourcej )
= 0 if target[i] = source[j]
substituteCost
= 2 otherwise
insertCost = 1
deleteCost = 1
最小编辑距离算法描述
function Min-Edit_Distance (target, source)
n = length(target);
m = length(source);
create distance matrix d[n,m];
d[0,0]=0;
d[0,1]=1,… d[0,m]=m;
d[1,0]=1,…d[n,0]=n;
for each i from 1 to n do
for each j from 1 to m do
d[i, j] = min( d[i-1, j] + insertCost(targeti)),
d[i-1, j-1] + substituteCost(sourcej, targeti),
d[i, j-1] + deleteCost(sourcej));
return d[n,m];
最小编辑距离计算示例
source : s o t j
3 t
target : s t o p 2 o
1 s
n = length (target) 0 # s t op
m = length (source) # 0 1 2 3 4
Create matrix d [n, m]; i
i=0 j=0
d[0,0] = 0;
d[0,1] = 1; …; d[0,m] = m;
d[1,0] = 1; …; d[n,0] = n;
最小编辑距离计算示例
source : s o t j
3 t
target : s t o p 2 o
1 s 0
n = length (target) 0 # s t op
m = length (source) # 0 1 2 3 4
Create matrix d [n, m]; i
i=1 j=1
d[0,1]+insert(t[1]) = 2
d[1,1] = min d[0,0]+substitute(s[1],t[1]) =0 = 0
d[1,0]+delete(s[1]) = 2
最小编辑距离计算示例
source : s o t j
3 t
target : s t o p 2 o 1
1 s 0
n = length (target) 0 # s t op
m = length (source) # 0 1 2 3 4
Create matrix d [n, m]; i
i=1 j=2
d[0,2]+insert(t[1]) = 3
d[1,2] = min