一篇文章带你读懂什么是编辑距离

问题描述

编辑距离又称作Levenshtein距离,是指两个字符串之见由一个字符串转换成另一个字符串所需的最少操作次数.通常来说,比较两个字符串,将一个字符串修改成另一个字符串共有三个基本操作:增,删,改.其中增就是增加某个元素,删就是去掉某个元素,而改相当于将元素a替换成元素b.理论上,两个长度相等的字符串都可以通过"改"这个操作来实现,而长度不相等的时候就必须要有增或者删操作了.如果不考虑最少操作次数的话.对于任何一个字符串s1和s2,最多操作max{len(s1), len(s2)}次.我们举个栗子.如果strs1 = “horse”, strs2 = “deer”, 我们不管三七二十一,直接做这样的操作:

可见此时做了五次操作,而这恰恰是字符串"horse"的长度,反过来也是一样的.但是题目要求的是最少的操作次数,我们再看一个例子,假如str1 = “love”, str2 = “life”.如果采用暴力转换,那么无疑要经过四次变换.但我们明显可以看出str1和str2有着相同位置的共同元素(“l"和"e”).我们可以保留这两个位置的元素而替换另外两个位置的元素.所以我们这里love到life的编辑距离就是2.
接下来我们就要系统地总结一下关于此类问题的所有情况,并利用动态规划法去求解这个问题.

问题分析

我们以 str1 = "s_{1}s_{2}...s_{i-1}s_{i}...s_{m}"
和str2 ="t_{1}t_{2}...t_{j-1}t_{j}...t_{n}"为例,探讨这个问题的所有可能的情况.
记dp[i][j]为str1的前i个字符(str1[:i])到str2的前j个字符(str2[:j])的编辑距离.
当我们考虑dp[i][j]的时候,很自然地,它是建立在前面字符串的基础上得到的,也就是说它与dp[i-1][j], dp[i][j-1], dp[i-1][j-1]有关.接下来分别讨论这三种关系.
(1)dp[i][j]与dp[i-1][j]有关.
如果我们知道"s_{1}s_{2}...s_{i-1}"到"t_{1}t_{2}...t_{j-1}t_{j}"的编辑距离dp[i-1][j],欲求dp[i][j],最简单的办法就是令str1删去一个元素str1[i-1],也就是s_{i},操作数+1.此时dp[i][j]满足:
dp[i][j]\leqslant dp[i-1][j] + 1;

(2)dp[i][j]与dp[i][j-1]有关.
同理.如果我们知道"s_{1}s_{2}...s_{i-1}s_{i}"到"t_{1}t_{2}...t_{j-1}"的编辑距离dp[i][j-1],欲求dp[i][j],最简单的办法就是令str1添加一个元素str2[j-1],也就是t_{j},操作数+1.此时dp[i][j]满足:
dp[i][j]\leqslant dp[i][j-1] + 1;

(3)dp[i][j]与dp[i-1][j-1]有关.
如果str1[i-1] == str2[j-1], 即s_{i} == t_{j} , 则dp[i][j] = dp[i-1][j-1], 因为这相当于在str1和str2后面同时加上s_{i}和t_{j}嘛. 如果str1[i-1] != str2[j-1]的话,最快我们只需要把str1[i-1]替换成str2[j-1]即可,所以
dp[i][j]\leqslant dp[i-1][j-1] + 1

由此,我们总结道,当str1[i-1] == str2[j-1]时.
dp[i][j] = min\{dp[i,j-1] + 1, dp[i, j-1] +1, dp[i-1][j-1]\}
当str1[i-1] != str2[j-1]时,
dp[i][j] = min\{dp[i,j-1] + 1, dp[i, j-1] +1, dp[i-1][j-1]+1\}

我们采用动态规划算法来实现求字符串的编辑距离.一开始,我们设计一个二维数组,长为len(strs2)+1,宽为len(strs1)+1.第一行和第一列用来存放初始的值.以第一行为例,遍历第一行的所有列,它一定满足dp[0][j] = j(j = 0, 1, …n-1),因为这就相当于从空转换到长度为j的字符串需要进行的操作只有增加j个元素. 队列来说, dp[i][0] = i亦然.
有了第一行和第一列的元素,我们就可以按行填入数组了.根据前面的讨论.我们很容易就能够填满整个数组.最后dp[m][n]就是我们所求的strs1到strs2的编辑距离.
如果我们的str1 = “python”, str2 = “pycharm”,那么生成这个二维数组的过程如下所示.

代码实现

实现代码如下:

    class EditDistance:
    #返回三个元素中最小的那个元素
    def mins(self, a, b, c):
        if a < b:
            tmp = a
        tmp = b
        if tmp < c:
            return tmp
        return c
    
    #建立动态规划的数组并且填满它
    def edit(self, s1, s2):
        if s1 == None and s2 == None:
            return 0
        if s1 == None:
            return len(s2)
        if s2 == None:
            return len(s1)
    
        len1 = len(s1)
        len2 = len(s2)
    
        dp = [([None] * (len2+1)) for i in range(len1+1)]
        i = 0
        while i < len1 + 1:
            dp[i][0] = i
            i += 1
        i = 0
        while i < len2 + 1:
            dp[0][i] = i
            i += 1
        i = 1
        while i < len1 + 1:
            j = 1
            while j < len2 + 1:
                if list(s1)[i-1] == list(s2)[j-1]:
                    dp[i][j] = self.mins(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1])
                else:
                    dp[i][j] = self.mins(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1] + 1)
                j += 1
            i += 1
        dis = dp[len1][len2]
        print("从"+s1+"到"+s2+"的编辑距离数组为:\n")
        for i in range(len(dp)):
            for j in range(len(dp[1])):
                print("%2d" % dp[i][j], end="")
            print()
        return dis
    
    #主方法
    if __name__ == "__main__":
    s1 = "python"
    s2 = "pycharm"
    ed = EditDistance()
    print("编辑距离为:" + str(ed.edit(s1, s2)))
    
    
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    

程序结果显示如下:

加油!