A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

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

编辑距离递推公式:



算法计算步骤:

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 == B[j] 时,temp = 1;否则 temp = 0。

dp[j] = min(dp[i-1][j-1] + temp , min(dp[i-1][j] + 1 , dp[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[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[j] = min(dp[i - 1][j - 1] + delta, min(dp[i-1][j] + 1, dp[j - 1] + 1))
    return dp[len1][len2]
edit_distance("jarrry", "jerr")
3.0

---------------------
作者:koibiki
来源:CSDN
原文:https://blog.csdn.net/koibiki/article/details/83031788
版权声明:本文为博主原创文章,转载请附上博文链接!

1 个回复

倒序浏览
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马