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

数学基础 2019-01-24 6117 字 39 浏览 点赞

前言

什么是编辑距离呢?

我们把“从字符串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)]

动态规划

那么什么是动态规划呢?

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

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

感谢



本文由 Guan 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

还不快抢沙发

添加新评论