动态规划-用编辑距离解释

分手后的思念是犯贱 2022-04-23 05:38 301阅读 0赞

# 动态规划-用编辑距离解释 #

### 文章目录 ###

*  动态规划-用编辑距离解释
 *   *  前言
     *  状态转移
     *  递归实现
     *  迭代实现
     *  代码优化
     *  动态规划
     *  感谢

## 前言 ##

什么是编辑距离？

我们把“从字符串A到字符串B”的最少操作次数称作**编辑距离**。操作包含了：插入，删除，替换。比如字符串A = “abc”，字符串B = “abcd”，那么从A到B只需要增加一个字母“d”，所以编辑距离为1；同样的，从B到A只需要删除“d”，所以编辑距离也为1。

## 状态转移 ##

将需要求解的问题，转移成子问题的过程，叫做**状态转移**。刻画状态转移的表达式称为**状态转移方程式**。

仍拿计算两个字符串的编辑距离为例。如果我们已知字符串A = “abc”，字符串B = “abc”，那么它们的编辑距离等于字符串“ab”与字符串“ab”的编辑距离。这是两个字符串最后一个字母相同时的处理方式，其他情况就得用其他方式。如已知 A = “abc” 与 B = “abcd”，求A和B之间的编辑距离。有以下方式做参考：

第一种方式，**对字符串A插入操作**，需要插入的值是B字符串的最后一个字母，所以问题变成了求“abcd”与“abcd”的编辑距离，现在最后一个字母相同，可以用之前得到的结论，继而问题成了求“abc”与“abc”的编辑距离。这样看来，其实是把最初的问题转移了：求“abc”与“abcd”编辑距离 = 求“abc”与“abc”的编辑距离 + 1。“+1”是因为我们对字符串A做了一个插入操作。

第二种方式，**对字符串A删除操作**。问题成了这样：求“abc”与“abcd”的编辑距离 = 求“ab”与“abcd”的编辑距离 + 1。

第三种方式，**对字符串A替换操作**。替换操作是比较隐晦的，不易看出来（对电脑而言），我们需要额外举例。现在字符串A = “abcd” 字符串B = “abce”，肉眼能够分辨，将字符串A最后一个字母“d”换成“e”，A就变成B了。可计算机没那么聪明，它需要一个字母一个字母的去比较。当同时去掉字符串A与字符串B的最后一个字母，如果剩下字符串相同，那么我们认为两个字符串之间的转换可以通过一个替换操作完成。

以上三种方式中，我们**总是只保留结果最小的值**。编辑距离的定义对此做了说明——需要最小操作数。每一次子问题中的最优解，保证了最终结果最优。

综上所述，得到状态转移方程式如下：

""" strA strB 表示A B两个字符串 get_edit_distance(strA, strB) 表示计算strA、strB之间的编辑距离 """
    if strA[-1] == strB[-1]:  # 当最后一个字母相同时
        distance = get_edit_distance(strA[:-1], strB[:-1])
    else:  # 当最后一个字母不同时
        distance = min(  # 只保留最优解的结果
            get_edit_distance(strA, strB[:-1]) + 1,  # 插入操作
            get_edit_distance(strA[:-1], strB) + 1,  # 删除操作
            get_edit_distance(strA[:-1], strB[:-1]) + 1,  # 替换操作
        )

## 递归实现 ##

有了上面的转移方程式，利用递归计算编辑距离就比较容易了（但它效率实在不高）：

def get_edit_distance(strA, str2):
        if len(strB) == 0:  # 考虑字符串B为空字符串时
            return len(strA)
        elif len(strA) == 0:  # 考虑字符串A为空字符串时
            return len(strB)
        else:
            if strA[-1] == strB[-1]:
                return get_edit_distance(strA[:-1], strB[:-1])
            else:
                return min(
                    get_edit_distance(strA, strB[:-1]) + 1,
                    get_edit_distance(strA[:-1], strB) + 1,
                    get_edit_distance(strA[:-1], strB[:-1]) + 1
                )

## 迭代实现 ##

迭代其实是递归的反向实现。使用递归时，我们要从字符串的最后一个字母入手，迭代则需要从第一个字母入手。我们可以绘制一张表格，用于描述两个字符串的编辑距离的变化。这里字符串A = “mouuse”，字符串B = “mouse”。表格如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70]

根据上述表格，我们可以很轻易得出A到B过程的子问题中的编辑距离。比如“mou”与“mouse”的编辑距离是2，“mouu”与“m”的编辑距离是3。我们接下来编写的程序，其目的就是去完成这张表。

这里有一个点需要注意，因为需要考虑空字符串，所以我们绘制的表格的大小不是`len(strA) * len(strB)`，而是`(len(strA)+1) * (len(strB)+1)`。

另外，Python创建一个二维数组可以用一个“土办法”：

d = [[0]*(len(strB)+1) for __ in range(len(strA)+1)]

下面是完整实现：

def get_edit_distance(strA, strB):
        d = [[0]*(len(strB)+1) for __ in range(len(strA)+1)]
        
        # 当 strB 为空字符串时
        for i, __ in enumerate("a" + strA):  # 'a' 为填充物，表示从 strA 为空字符串的时候开始
            d[i][0] = i
        
        # 当 strA 为空字符串时
        for j, __ in enumerate("a" + strB):  # 'a' 为填充物，表示从 strB 为空字符串的时候开始
            d[0][j] = j
        
        # 注意range的第一个参数是1，因为我们得从第二行第二列的位置开始填表
        # 第一行与第一列已经在前面初始化了
        for i in range(1, len(strA)+1):
            for j in range(1, len(strB)+1):
                if strA[i-1] == strB[j-1]:  # 与递归不同，不是从最后一个字母开始比较
                    d[i][j] = d[i-1][j-1]
                else:
                    # 在插入、删除、替换操作中保留最优解
                    d[i][j] = min(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+1)
        return d[-1][-1]

## 代码优化 ##

对上面代码继续分析。

当最后一个字母相同时，状态转移方式为`d[i][j] = d[i-1][j-1]`，在表格中可以看到位置关系如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70 1]

当最后一个字母不相同时，状态转移方程式为`d[i][j] = min(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+1)`，在表格中可以看到位置关系如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70 2]

也就是说，计算两个字符串的编辑距离，其实只需要保留左、上相邻元素，以及左上角相邻元素。所以我们不需要二维数组，一个一维已经够用，这样可以降低空间复杂度。

这里我建议对两个输入字符串的长度做比较，选出最短，用来作为一维数组的长度，尽可能减少内存开销：

def get_edit_distance(strA, strB):
        strMaxlen = strA if len(strA) >= len(strB) else strB
        strMinlen = strA if strMaxlen != strA else strB
        d = [0] * (len(strMinlen)+1)
        # ...

然后对这个一维数组初始化。此刻我们需要明白一维数组的意义，现在的一维数组表示：存放当较长字符串为空字符串时，较短字符串中每个子字符串的编辑距离。所以初始化如下：

def get_edit_distance(strA, strB):
        # ...
        for i, __ in enumerate("a"+strMinlen):
            d[i] = i
        # ...

由于我们数组d现在是一维的，只能保留一个维度的数据，而且这个数组总是存放“旧数据”。比如当我们计算“mouu”与“mouse”的编辑距离时，数组d中存放的是“mou”与“mouse”的编辑距离。接下来是代码最核心部分，也就是如何保留需要的三个位置中的数据：

def get_edit_distance(strA, strB):
        # ...
    	for i in range(1, len(strMaxlen)+1):
    	    # 由于数组d中的数据总是`旧数据`，对于新一行的第二个元素，d[0]就是其左上角元素
    	    leftTop = d[0]
    	    # 由于总是从第二个元素开始，所以第一个元素需要自己填写
    	    d[0] = i  # `for i in range(1, len(strMaxlen)+1)` 等价于 `for i, __ in enumerate("a"+strMaxlen)`
    	   
    	    for j in range(1, len(strMinlen)+1):
    	        # 当前位置元素在被新数据替换前，是下个位置的左上角元素，因此用临时变量存储起来
    	        temp = d[j]
    	        if strMaxlen[i-1] == strMinlen[j-1]:
    	            d[j] = leftTop
    	        else:
    	            d[j] = min(d[j-1]+1, d[j]+1, leftTop+1)
    	        leftTop = temp
    	# ...

这里我想对 **“当前位置元素在被新数据替换前，是下个位置的左上角元素”** 说明一下。当我们的数组d中存放的数据是“4 3 2 1 1 2”时，新一行的数据填写会从左到右开始，所以当我们更新索引为n的元素之前，该位置上的值就是上一行中索引为n时的值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70 3]

完整代码如下：

def get_edit_distance(strA, strB):
        strMaxlen = strA if len(strA) >= len(strB) else strB
        strMinlen = strA if strMaxlen != strA else strB
        d = [0] * (len(strMinlen)+1)  # 通过不断地刷新横排，达到空间优化地目的
        
        for i, __ in enumerate("a"+strMinlen):
            d[i] = i
    
        for i in range(1, len(strMaxlen)+1):
            leftTop = d[0]  # 充当左上角角色：d[i-1][j-1]
            d[0] = i  # 每一行的最左值
            for j in range(1, len(strMinlen)+1):
                temp = d[j]
                if strMaxlen[i-1] == strMinlen[j-1]:
                    d[j] = leftTop
                else:
                    d[j] = min(d[j-1]+1, d[j]+1, leftTop+1)
                leftTop = temp
    
        return d[len(strMinlen)]

## 动态规划 ##

那么什么是动态规划呢？

答：在各种局部解中选出可能达到最优的局部解，放弃其他局部解。寻找最优解的过程就是动态规划。

上述计算两个字符串的编辑距离，就是在用动态规划思想。其核心是：**状态转移方程式**。当你能够找出合适的方程式时，动态规划的脉络随之清晰。

## 感谢 ##

*  参考极客时间《程序员的数学基础课》之[动态规划][Link 1]
 *  参考网友明无梦的[《编辑距离》][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70]: /images/20220323/72b9d217122942fdbfd8b3089bc7e08d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70 1]: /images/20220323/45413577f86c45c28a5fb9c430aca28c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70 2]: /images/20220323/d11a484ef2ce427f9609a944c2ca0d8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70 3]: /images/20220323/0637277aa8084c3ba762389477d8a76f.png
[Link 1]: https://time.geekbang.org/column/article/75807
[Link 2]: https://www.dreamxu.com/books/dsa/dp/edit-distance.html