动态规划（dp）-最短编辑距离

2019-11-22 本文已影响0人 FluenceYHL

应该是我接触的第一个动态规划的算法，可以说是很经典了，Levenstein 距离。

问题描述

设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:
(1)删除一个字符;
(2)插入一个字符；
(3)将一个字符改为另一个字符。
将字符串 A 变换为字符串 B 所用的最少字符操作数，称为字符串 A 到 B 的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2个字符串 A 和 B,计算出它们的编辑距离d(A,B)

input

输入数据的第一行是一个正整数，表示一共有几组数据。

每组数据有两行，每行一个字符串。

每个字符串长度不超过1000

字符串中只含小写英文字母

output

对于每组数据，请输出一个整数表示两个字符串的编辑距离(最短编辑距离)

Sample Input :
10 AGTCTGACGC
11 AGTAAGTAGGC
5 abcdy
4 abds
7 dewjfsr
4 ejfr
Sample output
4
2
3

推导

$dp[ i ][ j ]=Min\left\{ \begin{aligned} dp[i - 1][j] + 1\\ dp[i][j - 1] + 1 \\ dp[i - 1][j - 1] & & {当 A[i - 1] = B[j - 1]} \\ dp[i - 1][j - 1] + 1& & {当 A[i - 1] \neq B[j - 1]} \\ \end{aligned} \right.$
假设求 'abcy' 和 'aby' 的编辑距离

$dp[i - 1][j] + 1$ ，

删除'abcy'中的y —— 也可以理解为在求 'abc' 和 'aby' 编辑距离的基础上，在 'abc' 尾部插入一个 y，推导而来

$dp[i][j - 1] + 1$

删除 'aby' 中的 y, —— 也可以理解为在求 'abcy' 和 'ab'编辑距离的基础上，在 ’ab' 尾部插入一个 y，推导而来

$dp[i - 1][j - 1] \qquad{ A[i - 1] = B[j - 1]}$

因为 'abcy' 第 i 个字符 'y' 和 'aby' 中当前第 j 个字符 'y' 相等，所以，可以认为在求 'abc' 和 'ab' 编辑距离的基础上没有任何编辑操作，后接一个空字符。

$dp[i - 1][j - 1] + 1 \qquad{ A[i - 1] \neq B[j - 1]}$

模板

求最短编辑距离 POJ 3356

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Min(a , b , c) (a < b ? (a < c ? a : c) : (b < c ? b : c))
int dp[1010][1010];
char s1[1010] , s2[1010];

int main(){
    // freopen("Levenshtein.in", "r", stdin);
    int n , m , i , j , cost;
    while(~scanf("%d%s%d%s" , &n, s1 , &m, s2)){
        memset(dp, 0, sizeof(dp));
        for(i = 0; i <= n; ++i) dp[i][0] = i;  // 另一个字符串长度为 0 时，长度就是本字符串当前长度
        for(i = 0; i <= m; ++i) dp[0][i] = i;
        for(i = 1; i <= n; ++i)
            for(j = 1; j <= m; ++j){
                // 若当前字符相等，dp[i][j] = dp[i - 1][j - 1]；否则，替换当前字符，编辑次数 +1
                cost = s1[i - 1] == s2[j - 1] ? 0 : 1;    
                dp[i][j] = Min(dp[i-1][j] + 1 , dp[i][j - 1] + 1 , dp[i - 1][j - 1] + cost);
            }    
        printf("%d\n", dp[n][m]);
    }
    return 0;
}

分析：

dp[i][j] 代表的是句子 s1 到了第 i 个字符，s2 到了第 j 个字符的编辑距离，例如：
s1 = 'abcy'
s2 = 'aby'
dp[3][2] 代表 s1的子句 'abc'，和 s2 的子句 'ab' 的(最短)编辑距离，是 1
根据循环特性，可得 0 <= i < 3，0 <= j < 2，dp[i][j] 都推导出来了。

for(i = 0; i <= n; ++i) dp[i][0] = i;
初始化推导的首项(类似数组的推导，一般都具有首项)，当两个句子中有一个句子为空，最短编辑距离就是非空的句子长度，在这里，i 代表的是当前的非空句子长度。

cost = s1[i - 1] == s2[j - 1] ? 0 : 1;
因为字符串从下标0开始存储，所以 s1[i - 1] 代表句子 s1 当前的字符，s2[j - 1] 同理。
(1). 如果 s1 和 s2 当前的字符相等，那么 dp[i][j] 有可能是 dp[i - 1[j - 1]，例子：
求 'abcy' 和 'aby' 的编辑距离，已知 'abc' 和 'ab' 的编辑距离是 1，恰好最后一个字符 'y' 相等，那么 'abcy' 和 'aby' 的编辑距离可能依旧是 1.
(2). 如果 s1 和 s2 当前的字符不相等，说明，在已知 dp[i - 1][j - 1] 的基础，至少还要再编辑一次(替换)，编辑次数 + 1

dp[i][j] = Min(dp[i-1][j] + 1 , dp[i][j - 1] + 1 , dp[i - 1][j - 1] + cost);
dp[i][j] 可以有三种可能性，从中选最小的距离作为当前的最短编辑距离。

优化 or 变体

1. 滚动数组，降低空间复杂度

观察主循环

for(i = 1; i <= n; ++i)
    for(j = 1; j <= m; ++j){
         cost = s1[i - 1] == s2[j - 1] ? 0 : 1;   
         dp[i][j] = Min(dp[i-1][j] + 1 , dp[i][j-1] + 1 , dp[i-1][j-1] + cost);
    }

外循环是 i，i 代表逐行；可以发现，每次推导 dp[i][j] ，都只利用了 dp[i - 1] 的信息，也就是说，推导第 i 层，只需要记录第 i - 1层的状态，所以也只需要存储第 i - 1 层的信息。
原来的 dp[1005][1005] 存储的是所有层的状态，现在减少到相邻两层 dp[2][1005]，也就是 dp[0][1005] 和 dp[1][1005]，假设偶数层都存储在 dp[0][1005]，奇数层都存储在 dp[1][1005]。
通过判断奇偶数 %2，但位运算 &1 可以略微加速，实现类似“滚动”的效果。
故修改代码如下：

#include <stdio.h>
#include <string.h>
#define Min(a , b , c) (a < b ? (a < c ? a : c) : (b < c ? b : c))
int dp[2][1010];
char s1[1010] , s2[1010];

int main(){
    // freopen("Levenshtein.in", "r", stdin);
    int n , m , i , j , cost;
    while(~scanf("%d%s%d%s" , &n, s1 , &m, s2)){
        memset(dp, 0, sizeof(dp));
        for(i = 0; i <= m; ++i) 
            dp[0][i] = i;
        for(i = 1; i <= n; ++i) {
            dp[i & 1][0] = i;    // 因为 dp 只能记录相邻两层的状态，所以不能像原来一样初始化
            for(j = 1; j <= m; ++j){
                // 若当前字符相等，dp[i][j] = dp[i - 1][j - 1]；否则，替换当前字符，编辑次数 +1
                cost = s1[i - 1] == s2[j - 1] ? 0 : 1;     
                dp[i & 1][j] = Min(dp[(i-1) & 1][j] + 1 , dp[i & 1][j-1] + 1 , dp[(i-1) & 1][j-1] + cost);
            }   
        }
        printf("%d\n", dp[n & 1][m]);
    }
    return 0;
}

前后对比：

可以看出，时间消耗一样，但内存消耗缩小到原来的十几分之一。滚动数组对于这种情况能节省极大内存。同时，也能看出位运算 & 对于程序速度的影响其实很细微。
但滚动数组也存在缺点，因为只记录了相邻两层的状态，所以不能找回推导的路径( A如何编辑得到 B )。

递归

根据推导方程，递归的回溯过程是正向的推导。代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Min(a, b, c) (a < b ? (a < c ? a : c) : (b < c ? b : c))
int dp[1010][1010];
char s1[1010], s2[1010];

int edit_distance(const int i, const int j) {
    // 判断边界条件
    if(i == 0) return j;
    if(j == 0) return i;
    // 判断当前两个句子的字符是否一样，是否需要额外的编辑操作
    const int cost = s1[i - 1] == s2[j - 1] ? 0 : 1;
    const int a = edit_distance(i - 1, j) + 1;
    const int b = edit_distance(i, j - 1) + 1;
    const int c = edit_distance(i - 1, j - 1) + cost;
    return Min(a, b, c);
}

int main(){
    // freopen("Levenshtein.in", "r", stdin);
    int n, m;
    while(~scanf("%d%s%d%s", &n, s1, &m, s2))
        printf("%d\n", edit_distance(n, m));
    return 0;
}

但是根据题目要求，字符串长度可达 1000，这对于递归来说深度太大，压栈参数多，在 OJ 上会超时，但是递归过程很明晰。
注：又掉进了一个坑！

return Min(
    edit_distance(i - 1, j) + 1,
    edit_distance(i, j - 1) + 1,
    edit_distance(i - 1, j - 1) + cost
);

define 宏定义和递归不可以一起用，宏定义是展开，会计算多次递归，浪费时间与空间！

内容扩展

1. 应用场景

可以用于模糊搜索、找相似度较高的句子，应用有拼写检查、求相似度等。
例如给定两个句子：

A = “最佳的编辑软件” 和
B = “最佳的游戏软件”，

二者的最短编辑距离是 2 (2次替换)，那么二者的相似度可以用 1 - 编辑距离/ [len(A) + len(B)]表示，这里是

1 - 2 / (7 + 7) = 1 - 0.1428 = 0.8571，

编辑距离越短，表示这两个句子经过越少次数的插入或替换等操作即可相互转换，相似度越高

2. 存在的问题

字符串编辑距离只考虑到了句子在“字形”上的距离，并没有考虑到每个字符(短语)背后代表的深层含义，在上个例子中：

“编辑”和“游戏”编辑距离是2，但二者在语义上的差距较大；
考虑“休闲”和“游戏”，字形上的编辑距离也是2，但是二者在语义上无疑更近一步。

对于搜索等任务来说，用户更渴望得到在语义上更相近的答案。
这也是传统文本搜索的弊病，没考虑语义距离；

3. 更好的距离衡量

那么如何衡量词语之间的语义距离呢？词向量给出了答案：word2vec。

基本原理可以直观理解为：

利用向量代表一个词语，将词语映射到“语义空间”，两个词语之间的距离可以通过它们的向量距离来衡量。
如果表达【游戏】对【编辑】与【休闲】的不同距离呢？共现频率的统计，经常出现在一起的词语在语义空间上应该是相近的，例如“游戏”和“休闲”经常出现[在一起开黑、网吧]等相关的上下文中，那么“游戏”和“休闲”在语义空间上就是相似的。但“编辑”和“游戏”几乎不会出现在相似的上下文中，二者的语义距离就很大了。通过梯度下降等算法不断拟合以上的情况，使得【游戏】与【休闲】的向量距离更小，但【游戏】与【编辑】之间的向量距离更大。

类似的算法

最大上升子序列
 最大公共子序列