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

文章目录

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

前言

什么是编辑距离？

我们把“从字符串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”。表格如下：
在这里插入图片描述

根据上述表格，我们可以很轻易得出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]，在表格中可以看到位置关系如下：
在这里插入图片描述

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

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

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

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时的值。
在这里插入图片描述

完整代码如下：

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)]