最小编辑距离算法
如果无法正常显示，请先停止浏览器的去广告插件。
1. 最小编辑距离算法
Minimum Edit Distance
詹卫东
北京大学中文系
2. 编辑距离
编
编辑前字符串
字符串 s
编辑后字符串 t
p
编辑操作p：插入、删除、替换
“编辑距离”定义为
“编辑操作的次数”
源文 Sh is
源文：She
i a star
t with
ith the
th theatre
th t company.
机器译文：她 是 与 剧院 公司 的 一 颗 星。
参考译文：她 是 剧团 的 明星。
编辑距离：6
删除次数（4次）：
替换次数（2次）：
计算机器译文
跟正确答案之
间的距离
与
公司 一 颗
剧院 剧团
星 明星
2
3. 最小编辑距离
原始串 s o t
目标串 s t o p
s o t
编辑操作1
s t o t
s t o p
(2
(2.替换，2分，累计3分)
替换 2分 累计3分)
编辑距离：3
• 插入操作
（insertCost权值） ： 1
• 删除操作
（deleteCost权值） ： 1
s o t
编辑操作2
s t t
s t o
• 替换操作
（substituteCost）
(1.插入，1分，累计1分)
： 2
(1
(1.替换，2分，累计2分)
替换 2分 累计2分)
(2.替换，2分，累计4分)
s t o p (3
(3.插入，1分，累计5分)
插入 1分 累计5分)
编辑距离：5
3
4. 最小编辑距离计算：动态规划
( (1) ) D(0,
( , 0) ) = 0 /* 空串变换成空串的编辑距离
(2) D(i, 0) = insertCost * i /* 空串变换成长度为 i 的串的编辑距离 */
(3) D(0, j) = deleteCost * j /* 长度为 j 的串变换成空串的编辑距离 */
D(i-1, j)
(4) D(i, j) = min
deleteCost
+ insertCost( target i )
D(i-1, j-1) + substituteCost( source j , target i )
D(i, j-1)
insertCost
*/
+ deleteCost( source j )
i ：目标串字符位置序号
= 1
j ：原始串字符位置序号
= 1
= 0 if target[i] = source[j]
= 2 otherwise
substituteCost
D(i j) ：从 j 变化到 i 的距离值
D(i,j)
source j ：j 位置的字符
target i ：i 位置的字符
4
5. 最小编辑距离算法描述
function Min-Edit _ Distance ( (target,
g , 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[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(target i ),
d[i-1, j-1] + substituteCost(source j , target i ),
d[i, j-1] + deleteCost(source j ));
return d[n,
d[n m];
5
6. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 o 1 s 0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target 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;
6
7. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 o 1 s 0 0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=1 j=1
d[1,1] = min
d[0,1]+insert(t[1]) = 2
d[0 0]
d[0,0]+substitute(s[1],t[1])
b
( [ ] [ ]) =0
0 = 0
d[1,0]+delete(s[1]) = 2
7
8. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 o 1 1 s 0 0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=1 j=2
d[1,2] = min
d[0,2]+insert(t[1]) = 3
d[0 ]
d[0,1]+substitute(s[2],t[1])
b
( [2] [ ]) =3
3 = 1
d[1,1]+delete(s[2]) = 1
8
9. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 2 o 1 1 s 0 0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=1 j=3
d[1,3] = min
d[0,3]+insert(t[1]) = 4
d[0 2]
d[0,2]+substitute(s[3],t[1])
b
( [3] [ ]) =4
d[1,2]+delete(s[3]) = 2
= 2
9
10. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 2 o 1 1 s 0 1 0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=2 j=1
d[2,1] = min
d[1,1]+insert(t[2]) = 1
d[ 0]
d[1,0]+substitute(s[1],t[2])
b
( [ ] [2]) =3
3 = 1
d[2,0]+delete(s[1]) = 3
10
11. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 2 o 1 2 1 s 0 1 0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=2 j=2
d[2,2] = min
d[1,2]+insert(t[2]) = 2
d[1 1]
d[1,1]+substitute(s[2],t[2])
b i
( [2] [2]) =2
2
d[2,1]+delete(s[2]) = 2
= 2
11
12. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 1 2 o 1 2 1 s 0 1 0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=2 j=3
d[2,3] = min
d[1,3]+insert(t[2])=3
d[1 2]
d[1,2]+substitute(s[3],t[2])=1
b i
( [3] [2]) 1
d[2,2]+delete(s[3])=3
= 1
12
13. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 1 2 o 1 2 1 s 0 1 2 0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=3 j=1
d[3,1] = min
d[2,1]+insert(t[3])=2
d[2 0]
d[2,0]+substitute(s[1],t[3])=4
b i
( [1] [3]) 4
d[3,0]+delete(s[1])=4
= 2
13
14. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 1 2 o 1 2 1 1 s 0 1 2 0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=3 j=2
d[3,2] = min
d[2,2]+insert(t[3])=3
d[2 1]
d[2,1]+substitute(s[2],t[3])=1
b i
( [2] [3]) 1
d[3,1]+delete(s[2])=3
= 1
14
15. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 1 2 2 o 1 2 1 1 s 0 1 2 0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=3 j=3
d[3,3] = min
d[2,3]+insert(t[3])=2
d[2 2]
d[2,2]+substitute(s[3],t[3])=4
b i
( [3] [3]) 4
d[3,2]+delete(s[3])=2
= 2
15
16. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 1 2 2 o 1 2 1 1 s 0 1 2 3
0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=4 j=1
d[4,1] = min
d[3,1]+insert(t[4])=3
d[3 0]
d[3,0]+substitute(s[1],t[4])=5
b i
( [1] [4])
d[4,0]+delete(s[1])=5
= 3
16
17. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 1 2 2 o 1 2 1 2
1 s 0 1 2 3
0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=4 j=2
d[4,2] = min
d[3,2]+insert(t[4])=2
d[3 1]
d[3,1]+substitute(s[2],t[4])=4
b i
( [2] [4]) 4
d[4,1]+delete(s[2])=4
= 2
17
18. 最小编辑距离计算示例
source j
source : s o t
target : s t o p
n = length (target) = 4
m = length (source) = 3
3 t 2 1 2 3
2 o 1 2 1 2
1 s 0 1 2 3
0 # s t o p
# 0 1 2 3 4
Create matrix d [n, m];
target i
i=4 j=3
d[4,3] = min
d[3,3]+insert(t[4])=3
d[3 2]
d[3,2]+substitute(s[3],t[4])=3
b i
( [3] [4]) 3
d[4,2]+delete(s[3])=3
= 3
18
19. 最小编辑距离计算示例
s o t
s t o t
编辑操作①
(1. 插入t，1分，累计1分)
s t o p (2. t替换p，2分，累计3分)
s o t
s t o t (1. 插入t，1分，累计1分)
s t o p t (2. 插入p，1分，累计2分)
s t o p
s o t
编辑操作③
(3. 删除t，1分，累计3分)
编辑操作② s o t 编辑操作④
s t (1. 删除o，1分，累计1分) s t o t (1. 插入t，1分，累计1分)
s to (2
(2. 插入o，1分，累计2分)
插入o 1分 累计2分) s to (2
(2. 删除t，1分，累计2分)
删除t 1分 累计2分)
s t o p (3. 插入p，1分，累计3分） s t o p (3. 插入p，1分，累计3分)
19
20. 最小编辑距离计算示例
j
3
t
2
1
2
3
①
2 o 1 2 1 2 ②
1 s 0 1 2 3 ③
0 # s t o p ④
# 0 1 2 3 4
i
20
21. 最小编辑距离计算练习
• intention
i t ti
execution
ti
编辑操作①
编辑操作②
i n t e n t i o n i n t e n * t i o n
e x e c u t i o n * e x e c u t i o n
操作 s s s s s
代价 2 2 2 2 2
= 10
s 替换操作
s：
操作 d s s s i
代价 1 2 2 2 1
d 删除操作
d：删除操作
= 8
i 插入操作
i：插入操作
21
22. 最小编辑距离计算练习
source
n 9 8 9 10 11 12 11 10 9 8
o 8 7 8 9 10 11 10 9 8 9
i 7 6 7 8 9 10 9 8 9 10
t 6 5 6 7 8 9 8 9 10 11
n 5 4 5 6 7 8 9 10 11 10
e 4 3 4 5 6 7 8 9 10 9
t 3 4 5 6 7 8 7 8 9 8
n 2 3 4 5 6 7 8 7 8 7
i 1 2 3 4 5 6 7 6 7 8
# 0 1 2 3 4 5 6 7 8 9
# e x e c u t i o n
target
23. 最小编辑距离计算练习
source
n 9 8 9 10 11 12 11 10 9 8
o 8 7 8 9 10 11 10 9 8 9
i 7 6 7 8 9 10 9 8 9 10
t 6 5 6 7 8 9 8 9 10 11
n 5 4 5 6 7 8 9 10 11 10
e 4 3 4 5 6 7 8 9 10 9
t 3 4 5 6 7 8 7 8 9 8
n 2 3 4 5 6 7 8 7 8 7
i 1 2 3 4 5 6 7 6 7 8
# 0 1 2 3 4 5 6 7 8 9
# e x e c u t i o n
target
24. 参考文献
• Daniel Jurafsky & James H. Martin, 2000,
p
and Language
g g Processing:
g An
Speech
Introduction to Natural Language
Processing Computational Linguistics
Processing,
Linguistics,
and Speech Recognition, Chapter 5,
section 5
5.6,
6 pp153-156,
pp153 156 Prentice-Hall
Prentice Hall Inc
Inc..
24