python实现编辑距离_编辑距离计算python实现

编辑距离是用来比较两个字符串之间相似度的度量方法，表示的是两个字符串间相互转换所需要的最少步骤。

编辑距离递推公式：

算法计算步骤：

1.对于字符串A 'jarrry'和字符串B'jerr'，先初始化矩阵dp为  [len(A) + 1][len(B) + 1]，dp矩阵的第一行与第一列均从零开始递增，最后得矩阵为

j

a

r

r

r

y

0

1

2

3

4

5

6

j

1

e

2

r

3

r

4

2.然后从第一列开始循环。对于每个矩阵坐标 (i，j)，设置中间变量temp，当 A[i] == B[j] 时，temp = 1；否则 temp = 0。

dp[i][j] = min(dp[i-1][j-1] + temp ， min(dp[i-1][j] + 1 , dp[i][j-1] + 1))

3.循环完成dp矩阵为

j

a

r

r

r

y

0

1

2

3

4

5

6

j

1

0

1

2

3

4

5

e

2

1

1

2

3

4

5

r

3

2

2

1

2

3

4

r

4

3

3

2

1

2

3

dp[len(A)][len(B)]就是A,B两个字符串得编辑距离

python实现：

def edit_distance(word1, word2):

len1 = len(word1);

len2 = len(word2);

dp = np.zeros((len1 + 1,len2 + 1))

for i in range(len1 + 1):

dp[i][0] = i;

for j in range(len2 + 1):

dp[0][j] = j;

for i in range(1, len1 + 1):

for j in range(1, len2 + 1):

delta = 0 if word1[i-1] == word2[j-1] else 1

dp[i][j] = min(dp[i - 1][j - 1] + delta, min(dp[i-1][j] + 1, dp[i][j - 1] + 1))

return dp[len1][len2]

edit_distance("jarrry", "jerr")

3.0