saenai no heroine

最短编辑距离 minimal edit distance

dynamic programming
字数统计: 1,391阅读时长: 6 min
2019/02/10 Share

动态规划

什么是动态规划

动态规划与递归相似的是，它们都是通过将问题划分成更小的子问题，直到子问题足够小以至于我们可以直接计算出答案，再一步步往上回溯直到得到原本的问题的答案。
与递归需要检查所有的情况不同，为了完成我们的目标有时候也许我们只需要局部的最优解。而动态规划就是通过计算局部最优解并舍弃其他的局部解最后计算得到整个问题的最优解。
在动态规划中我们将规模不同的具有最优子结构的子问题称作状态，而描述从某一个状态到另外一个状态的表达式被我们称作状态转移方程。

最短编辑距离

编辑距离是指将一个字符串转化到另外一个字符串所需要的插入、替换、删除操作的最少次数。
但是为什么要用动态规划这样一个算法来计算最短编辑距离呢？
试想一下，如果我们简单地使用递归或者是迭代的方法计算最短编辑距离，由于递归需要遍历所有的可能性，所以递归通常需要大量的时间进行计算，而在实际生产中，用户可能会因为过长的等待时间而流失。

动态规划的优点在于它只保存了局部最优解而并不是所有的解，所以在内存资源的消耗上以及计算复杂度上具有较大优势。
判断一个问题能否用动态规划算法解决在于，这个问题是否具有最优子结构。

对于最短编辑距离问题，考虑这样两个字符串：str1a 和 str2b。
这里我们用d[i][j]来代表将一个长度为i的字符串转化为一个长度为j的字符串的最短编辑距离。
假设字符串str1a的长度为i，字符串str2b的长度为j。

根据之前所提到的编辑字符串的操作共有：替换、插入、删除 三种。
对于这三种不同的情况对应的最短编辑距离计算过程如下所示：
首先我们要明确当前的目标是什么？——计算字符串str1a（长度为i）转换到字符串str2b（长度为j）的最短编辑距离。

  • 替换的情况：str1a中的str1被转换成str2之后，再将(str1 -> str2)a中的a替换为b。此时的编辑距离为d[i -1][j - 1] + 1(a != b) / 0(a == b)。
  • 删除的情况：首先，str1a中的str1将被转换为str2b，转换后的字符串为(str1 -> str2b)a，再将str2ba中的a删去即可得到str2b。这种情况的编辑距离为d[i - 1][j] + 1。
  • 插入的情况：既然是要做插入的操作，那么字符串str1a将首先被转化为另外一个字符串之后再插入一个字符，那么转化后的字符串就是str2，即str1a -> str2，再在str2的末尾插入b得到str2b。编辑距离为d[i][j - 1] + 1。

分析完所有的子状态后，现在我们可以写出最短编辑距离的状态转移方程了。

1
2
3
d[i][j] = min(d[i][j - 1]) + 1, d[i - 1][j] + 1, d[i - 1][j - 1] + 1) // if a != b
or
d[i][j] = min(d[i][j - 1]) + 1, d[i - 1][j] + 1, d[i - 1][j - 1] + 0) // if a == b

Python实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def minEditDistance_recursive(sourceStr, targetStr):
    len_s = len(sourceStr)
    len_t = len(targetStr)
    # base condition
    if len_s == 0 and len_t == 0:
        return 0
    elif len_s != 0 and len_t == 0:
        return len_s
    elif len_s == 0 and len_t != 0:
        return len_t
    else:
        if sourceStr[-1] == targetStr[-1]:
            replaceDistance = 0
        else:
            replaceDistance = 1
        return min(
            minEditDistance_recursive(sourceStr[: -1], targetStr[:]) + 1, \
            minEditDistance_recursive(sourceStr[:], targetStr[: -1]) + 1, \
            minEditDistance_recursive(sourceStr[: -1], targetStr[: -1]) + replaceDistance \
            )


def minEditDistance_iterative(sourceStr, targetStr):
    len_src = len(sourceStr)
    len_tar = len(targetStr)
    d = [[None for j in range(len_tar + 1)] for i in range(len_src + 1)]
    for i in range(len(sourceStr) + 1):
        d[i][0] = i
    for j in range(len(targetStr) + 1):
        d[0][j] = j
    for i in range(1, len(sourceStr) + 1):
        for j in range(1, len(targetStr) + 1):
            r = 0
            if sourceStr[i - 1] != targetStr[j - 1]:
                r = 1
            d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + r)
    return d[len_src][len_tar]


str1 = "o"
str2 = "hello"
print(minEditDistance_recursive(str1, str2))
print(minEditDistance_iterative(str1, str2))

在使用Python创建二维数组的时候需要注意s * n返回的是将s中的元素复制n次后的结果，
比如[[1]] * 3将返回[[1], [1], [1]]。但是复制后的结果中的每一个元素都是指向原本的s中的元素的指针/引用，
比如：

1
2
3
4
5
6
>>> ls = [[None]] * 3
>>> ls
    [[None], [None], [None]]
>>> ls[0][0] = 0
>>> ls
    [[0], [0], [0]]

下面这个例子与上一个例子的不同之处在于ls[0] = 5将ls[0]指向了一个新的object，所以在之后对于ls[0]做的操作对于ls中剩下的元素将不会产生影响。
Remember everything in Python is a object.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
In [1]: ls = [[]] * 5

In [2]: ls
Out[2]: [[], [], [], [], []]

In [3]: ls[0] = 5

In [4]: ls
Out[4]: [5, [], [], [], []]

In [5]: ls[0] = []

In [6]: ls
Out[6]: [[], [], [], [], []]

In [7]: ls[0].append(5)

In [8]: ls
Out[8]: [[5], [], [], [], []]

In [9]: ls[1].append(1)

In [10]: ls
Out[10]: [[5], [1], [1], [1], [1]]

详细内容参见Python documentation：
Built-in Types/Sequence Types — list, tuple, range
如何创建一个多维数组

CATALOG
  1. 1. 动态规划
    1. 1.1. 什么是动态规划
    2. 1.2. 最短编辑距离
Total : 8
2020
2019
Invalid date
2019
2018
C++ dynamic programming 读书笔记