算法：编辑距离（莱文斯坦距离）

爱被打了一巴掌 2022-12-29 04:48 118阅读 0赞

### 编辑距离 ###

*  题目描述
 *   *  编辑距离介绍
     *  莱文斯坦距离
     *  示例
 *  代码
 *   *  运行过程分析
 *  参考文献

# 题目描述 #

## 编辑距离介绍 ##

编辑距离是针对二个字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个（或哪几个）是比较可能的字。DNA也可以视为用A、C、G和T组成的字符串，因此编辑距离也用在生物信息学中，判断二个DNA的类似程度。Unix下的diff及patch即是利用编辑距离来进行文本编辑对比的例子。  
编辑距离有几种不同的定义，差异在可以对字符串进行的处理。

在莱文斯坦距离中，可以删除、加入、取代字符串中的任何一个字元，也是较常用的编辑距离定义，常常提到编辑距离时，指的就是莱文斯坦距离。
    也存在其他编辑距离的定义方式，例如 Damerau-Levenshtein 距离是一种莱文斯坦距离的变种，但允许以单一操作交换相邻的两个字符（称为字符转置），如 AB→BA 的距离是 1（交换）而非 2（先删除再插入、或者两次替换）。
    LCS（最长公共子序列）距离只允许删除、加入字元。
    Jaro 距离只允许字符转置。
    汉明距离只允许取代字元。 [1]

## 莱文斯坦距离 ##

莱文斯坦距离，又称Levenshtein距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。俄罗斯科学家弗拉基米尔·莱文斯坦在1965年提出这个概念。 \[1\]  
例如将kitten一字转成sitting：

sitten （k→s）
    sittin （e→i）
    sitting （→g）

## 示例 ##

示例1：  
kitten和sitting的莱文斯坦距离是3。将kitten变为sitting的最小处理方式如下：

kitten →sitten（将k改为s）
    sitten → sittin（将e改为i）
    sittin → sitting（最后加入g）

若是考虑LCS距离（只考虑加入及删除），LCS距离是5：

删除位在第1个字的k
    在第1个字之前加入s
    删除位在第4个字的e
    在第4个字之前加入i
    在第6个字之后加入g [1]

示例2：  
输入：word1 = “horse”, word2 = “ros”  
输出：3  
解释：

horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')

示例 3：  
输入：word1 = “intention”, word2 = “execution”  
输出：5  
解释：

intention -> inention (删除 't')
    inention -> enention (将 'i' 替换为 'e')
    enention -> exention (将 'n' 替换为 'x')
    exention -> exection (将 'n' 替换为 'c')
    exection -> execution (插入 'u')

# 代码 #

import pysnooper
    class Solution:
        # @pysnooper.snoop() # pysnooper是装饰器，可以修改函数，作用是打印函数的参数
        def editDistance(self , word1 , word2 ):
            # write code here
            temp = [[i+j for j in range(len(word2)+1)] for i in range(len(word1)+1)]
            for i in range(1,len(word1)+1):
                for j in range(1,len(word2)+1):
                    if word1[i-1] == word2[j-1]:
                        d = 0
                    else:
                        d =1
                    temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
            return temp[-1][-1]
    
    word1,word2 = "horse","ros"
    s = Solution()
    print(s.editDistance(word1 , word2))

## 运行过程分析 ##

Starting var:.. word1 = 'horse'
    Starting var:.. word2 = 'ros'
    11:24:46.749754 call         4     def editDistance(self , word1 , word2 ):
    11:24:46.750755 line         6         temp = [[i+j for j in range(len(word2)+1)] for i in range(len(word1)+1)]
    New var:....... temp = [[0, 1, 2, 3], [1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8]]
    11:24:46.750755 line         7         for i in range(1,len(word1)+1):
    New var:....... i = 1
    11:24:46.750755 line         8             for j in range(1,len(word2)+1):
    New var:....... j = 1
    11:24:46.750755 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.750755 line        12                     d =1
    New var:....... d = 1
    11:24:46.750755 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8]]
    11:24:46.750755 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 2
    11:24:46.751755 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.751755 line        12                     d =1
    11:24:46.751755 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 4], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8]]
    11:24:46.751755 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 3
    11:24:46.751755 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.751755 line        12                     d =1
    11:24:46.751755 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8]]
    11:24:46.751755 line         8             for j in range(1,len(word2)+1):
    11:24:46.751755 line         7         for i in range(1,len(word1)+1):
    Modified var:.. i = 2
    11:24:46.751755 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 1
    11:24:46.751755 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.751755 line        12                     d =1
    11:24:46.751755 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8]]
    11:24:46.751755 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 2
    11:24:46.751755 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.751755 line        10                     d = 0
    Modified var:.. d = 0
    11:24:46.751755 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 5], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8]]
    11:24:46.751755 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 3
    11:24:46.752755 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.752755 line        12                     d =1
    Modified var:.. d = 1
    11:24:46.752755 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8]]
    11:24:46.752755 line         8             for j in range(1,len(word2)+1):
    11:24:46.752755 line         7         for i in range(1,len(word1)+1):
    Modified var:.. i = 3
    11:24:46.752755 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 1
    11:24:46.752755 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.752755 line        10                     d = 0
    Modified var:.. d = 0
    11:24:46.752755 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8]]
    11:24:46.752755 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 2
    11:24:46.756755 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.756755 line        12                     d =1
    Modified var:.. d = 1
    11:24:46.756755 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 6], [4, 5, 6, 7], [5, 6, 7, 8]]
    11:24:46.756755 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 3
    11:24:46.756755 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.756755 line        12                     d =1
    11:24:46.756755 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 5, 6, 7], [5, 6, 7, 8]]
    11:24:46.756755 line         8             for j in range(1,len(word2)+1):
    11:24:46.756755 line         7         for i in range(1,len(word1)+1):
    Modified var:.. i = 4
    11:24:46.756755 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 1
    11:24:46.756755 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.757757 line        12                     d =1
    11:24:46.757757 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 6, 7], [5, 6, 7, 8]]
    11:24:46.757757 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 2
    11:24:46.757757 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.757757 line        12                     d =1
    11:24:46.757757 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 3, 7], [5, 6, 7, 8]]
    11:24:46.757757 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 3
    11:24:46.757757 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.757757 line        10                     d = 0
    Modified var:.. d = 0
    11:24:46.757757 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 3, 2], [5, 6, 7, 8]]
    11:24:46.758758 line         8             for j in range(1,len(word2)+1):
    11:24:46.758758 line         7         for i in range(1,len(word1)+1):
    Modified var:.. i = 5
    11:24:46.758758 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 1
    11:24:46.758758 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.758758 line        12                     d =1
    Modified var:.. d = 1
    11:24:46.758758 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 3, 2], [5, 4, 7, 8]]
    11:24:46.758758 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 2
    11:24:46.758758 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.758758 line        12                     d =1
    11:24:46.758758 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 3, 2], [5, 4, 4, 8]]
    11:24:46.758758 line         8             for j in range(1,len(word2)+1):
    Modified var:.. j = 3
    11:24:46.758758 line         9                 if word1[i-1] == word2[j-1]:
    11:24:46.759756 line        12                     d =1
    11:24:46.759756 line        13                 temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1,temp[i-1][j-1]+d)
    Modified var:.. temp = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 3, 2], [5, 4, 4, 3]]
    11:24:46.759756 line         8             for j in range(1,len(word2)+1):
    11:24:46.759756 line         7         for i in range(1,len(word1)+1):
    11:24:46.759756 line        14         return temp[-1][-1]
    11:24:46.759756 return      14         return temp[-1][-1]
    Return value:.. 3
    3

# 参考文献 #

\[1\]Navarro, Gonzalo. A guided tour to approximate string matching (PDF). ACM Computing Surveys. 1 March 2001, 33 (1): 31–88 \[19 March 2015\]. doi:10.1145/375360.375365.