✤ Apr 20, 2014 ✤
最近几天在整理以前收集的和用过有点忘记的编程、算法等相关信息。
当初毕设做的字符串测试数据自动生成算法中就是应用了编辑距离，那会捯饬这个浪费了不少时间。
所谓编辑距离，是指两个任意字符串s, t。由s经过编辑操作编程t所需的操作次数，这里的编辑操作包括插入、替换、删除三种操作。
由此，两个字符串之间的编辑距离可以定义为：
ED(s:a,t:b)=min(ED(s:a,t)+1,ED(s,t:b)+1,ED(s,t)+ED(a,b))
在这里，s, t是两个可能为空的字符串；s:a，t:b是字符串s，t的子串；a，b为字符。如果两个字符串均为空，则它们的编辑距离是0；一个非空字符串和空字符串的编辑距离是非空字符串的长度。
0.0 介个是编辑距离相关的信息，恩，如果用程序实现计算编辑距离肿么做呢。
可以用动态规划来实现编辑距离~
首先定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。
显然可以有如下动态规划公式：
- if i == 0 且 j == 0，edit(i, j) = 0
- if i == 0 且 j > 0，edit(i, j) = j
- if i > 0 且j == 0，edit(i, j) = i
- if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。
那算法就是这样，譬如可以有如下一个示例。串A：GUMBO，串B：GAMBOL，计算它们之间的编辑距离。
Steps 1 and 2
= = G U M B O
= 0 1 2 3 4 5
G 1
A 2
M 3
B 4
O 5
L 6
Steps 3 to 6 When i = 1
= = G U M B O
= 0 1 2 3 4 5
G 1 0
A 2 1
M 3 2
B 4 3
O 5 4
L 6 5
Steps 3 to 6 When i = 2
= = G U M B O
= 0 1 2 3 4 5
G 1 0 1
A 2 1 1
M 3 2 2
B 4 3 3
O 5 4 4
L 6 5 5
Steps 3 to 6 When i = 3
= = G U M B O
= 0 1 2 3 4 5
G 1 0 1 2
A 2 1 1 2
M 3 2 2 1
B 4 3 3 2
O 5 4 4 3
L 6 5 5 4
Steps 3 to 6 When i = 4
= = G U M B O
= 0 1 2 3 4 5
G 1 0 1 2 3
A 2 1 1 2 3
M 3 2 2 1 2
B 4 3 3 2 1
O 5 4 4 3 2
L 6 5 5 4 3
Steps 3 to 6 When i = 5
= = G U M B O
= 0 1 2 3 4 5
G 1 0 1 2 3 4
A 2 1 1 2 3 4
M 3 2 2 1 2 3
B 4 3 3 2 1 2
O 5 4 4 3 2 1
L 6 5 5 4 3 2
Step 7
所以，A、B之间的编辑距离最右下角的数字，即edit(A,B)=2。
算法说完了，最后说一下python中的具体实现。其实，实现的代码真的是灰常简单，(⊙v⊙)嗯，闲言碎语不要讲，直接附代码~
#! /usr/bin/env python
# -*- coding: utf-8 -*
def edit_dis(m,n):
"""
动态规划算法,计算编辑距离，操作包括插入、删除、替换
simple input:
>>> print edit_dis("abc","abec")
1
>>> print edit_dis("ababec","abc")
3
"""
len_1=lambda x:len(x)+1
c=[[i] for i in range(0,len_1(m)) ]
c[0]=[j for j in range(0,len_1(n))]
for i in range(0,len(m)):
for j in range(0,len(n)):
c[i+1].append(
min(
c[i][j+1]+1, # 插入操作
c[i+1][j]+1, # 删除操作
c[i][j] + (0 if m[i]==n[j] else 1 ) # 替换操作
)
)
return c[-1][-1]
if __name__ == '__main__':
print edit_dis("abc","abedfsfc")
恩，就酱~