编辑距离python递归,自然语言处理解决编辑距离问题的动态程序设计（Python）,规划,思想,python...

最近在看自然语言处理的课&＃xff0c;本来只想看看。但是一动手&＃xff0c;才发现&＃xff0c;呵呵呵?

我都是自学&＃xff0c;所以底子不太好&＃xff0c;理解东西比较慢。这动态规划处理编辑距离的问题就让我烦扰了好久。忧桑。

好在我才看完《算法图解》&＃xff0c;里面有说道动态规划的问题&＃xff0c;而且比较容易懂。

动态规划的问题都要涉及到表格&＃xff0c;《算法图解》中的动态规划的问题是处理两个单词之间的相似度&＃xff0c;而编辑距离涉及到替换、删除、增加&＃xff0c;两个的表格设计不同&＃xff0c;然后就是。。。我迷糊了

当然我现在弄清楚了一些。两个单词之间的相似度是基于表格周围最大值而变化&＃xff0c;而编辑距离是基于周围最小值而变化

str1 &＃61; ‘altrui’&＃xff0c;str2 &＃61; ‘algor’

len(str1) &＃61; 6&＃xff0c;len(str2) &＃61; 5

这时我们需要一个 7 * 6的表格(除去表示字符的行列)&＃xff0c;为dp

可以这么想&＃xff01;

①现在我们先来到dp[0][0]&＃xff0c;这个时候&＃xff0c;我们没有任何字符&＃xff0c;所以不需要任何改变

②来到dp[0][1]&＃xff0c;这个时候我们str1出现了第一个字符&＃xff0c;然后我们str2依然没有字符。那str2如何变成此时的str1呢&＃xff0c;就是添加一个&＃xff0c;所以dp[0][1] &＃61; 1

③来到dp[0][2]&＃xff0c;这个时候str2出现了第二个字符&＃xff0c;然而str2依然没有出现可以使用的字符&＃xff0c;所以str2要变成此时的str1&＃xff0c;就要添加两个字符&＃xff0c;所以dp[0][2] &＃61; 2。这一行以此类推。

④来到dp[1][0]&＃xff0c;在这个地方&＃xff0c;str2有一个字符&＃xff0c;str1没有提供字符&＃xff0c;所以str2变成str1要删除一个字符。到dp[1][1]&＃xff0c;str1提供A啦&＃xff0c;此时两者都不需要改变。所以为0。

⑤dp[1][2],此时str1又给我一个字符L&＃xff0c;那此时的str2‘A’变成str1‘AL’&＃xff0c;则要删去一个字符&＃xff0c;操作为1。dp[1][3]&＃xff0c;此时str1‘ALT’&＃xff0c;str2‘A’&＃xff0c;在之前删除的基础上我们又要删除一个&＃xff0c;所以为2(你也可以直接从A考虑&＃xff0c;要删除两个)。以此类推。。。

理解动态规划关键是要自己动手把表格画画&＃xff0c;不能光靠公式&＃xff0c;只会敲代码是不行的&＃xff0c;那就相当于在背代码

(其实是和自己说&＃xff0c;小声哔哔)

python实现代码如下

def edit_dis(str1, str2):

m,n &＃61; len(str1),len(str2)

dp &＃61; [[0 for x in range(n&＃43;1)] for x in range(m&＃43;1)]

# 生成一个含有m&＃43;1个列表&＃xff0c;每个列表又包含n&＃43;1个0的二维列表(当然也可以用numpy.zeros()来生成)

for i in range(m&＃43;1):

for j in range(n&＃43;1):

if i &＃61;&＃61; 0:

dp[i][j] &＃61; j

elif j &＃61;&＃61; 0:

dp[i][j] &＃61; i

elif str1[i-1] &＃61;&＃61; str2[j-1]:

dp[i][j] &＃61; dp[i-1][j-1]

else:

dp[i][j] &＃61; min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) &＃43; 1

return dp[m][n]

还有一个递归版本

def edit_dist(str1, str2):

if len(str1) &＃61;&＃61; 0:

return len(str2)

elif len(str2) &＃61;&＃61; 0:

return len(str1)

elif str1 &＃61;&＃61; str2:

return 0

if str1[len(str1)-1] &＃61;&＃61; str2[len(str2)-1]:

d &＃61; 0

else:

d &＃61; 1

return min(edit_dist(str1, str2[:-1]) &＃43; 1,

edit_dist(str1[:-1], str2) &＃43; 1,

edit_dist[:-1], str2[:-1]) &＃43; d)