利用编辑距离计算字符串的相似度Python实现

谁借莪１个温暖的怀抱￠ 2021-09-28 00:46 297阅读 0赞

参考资料：  
**原文：[编辑距离计算python实现][python] （作者：koibiki）**

采用动态规划的思想，跟计算最长公共子串问题类似。  
**编辑距离**是针对二个字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。

利用编辑距离计算相似度的概率*f(x,y)*：  
如果y为x的子串，则 f ( x , y ) = 1 f(x,y)=1 f(x,y)=1  
否则： f ( x , y ) = 1 − e d i t ( x , y ) m a x ( l e n ( x ) , l e n ( y ) ) f(x,y)=1-\\frac\{edit(x,y)\}\{max(len(x),len(y))\} f(x,y)=1−max(len(x),len(y))edit(x,y)

Python实现：

#编辑距离是用来比较两个字符串之间相似度的度量方法，表示的是两个字符串间相互转换所需的最少步骤。
    import numpy as np
    
    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):
                temp = 0 if word1[i - 1] == word2[j - 1] else 1
                dp[i][j] = min(dp[i - 1][j - 1] + temp, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1))
        return dp[len1][len2]
    
    #假设 word1 > word2
    def simility(word1, word2):
        if word2 in word1:
            return 1.0
        res = edit_distance(word1, word2)
        maxLen = max(len(word1),len(word2))
        return 1-res*1.0/maxLen
    
    if __name__ == '__main__':
        res = simility('中国男子篮球职业联赛','中男篮职业联赛')
        print(res)#0.7

[python]: https://blog.csdn.net/koibiki/article/details/83031788