字符串编辑距离

题目描述

    给定一个源串和目标串，能够对源串进行如下操作：

    ·在任意位置上插入一个字符；

    ·替换任意字符；

    ·删除任意字符。

    写一个程序，实现返回最小操作次数，使得对源串进行上述这些操作后等于目标串（源串和目标串的长度都小于2000），这就是字符串编辑距离问题。

分析与解法

    本题常见的求解思路是用动态规划。假如令 dp[i][j]表示源串 S[0..i]和目标串 T[0..j]的最短编辑距离，其边界 dp[0][j]=j，dp[i][0]=i，那么可以得出状态转移方程：

dp[i][j] =min{dp[i−1][j] + 1 , S[i]不在T[0..j]中

            dp[i−1][j−1] + 1/0 , S[i]在T[j]

            dp[i][j−1] + 1 , S[i]在T[0..j−1]中

}

    接下来，重点解释一下上述三个式子的含义。

    关于“dp[i−1][j] + 1，S[i]不在T[0..j]中”的说明

S[i]没有落在T[0..j]中，即S[i]在中间的某一次编辑操作中被删除了。因为删除操作没有前后相关性，不妨将其在第1次操作中删除。除首次操作时删除外，后续编辑操作都是将长度为i−1的字符串编辑成长度为j的字符串，即dp[i−1][j]，故dp[i][j]=dp[i−1][j] + 1。

    关于“dp[i−1][j−1] + 0/1，S[i]在T[j]中”的说明

    若S[i]经过编辑最终落在T[j]的位置，则要么S[i] == T[j]，S[i]直接落在T[j]（这种情况，编辑操作实际上是将长度为i−1的S′串，编辑成长度为j−1的T’串，即dp[i−1][j−1]），要么S[i] ≠ T[j]，即S[i]落在T[j]后，要将S[i]修改成T[j]（即在上一种情况的基础上增加一次修改操作，即dp[i−1][j−1] + 1）。

    关于“dp[i][j−1] + 1，S[i]在T[0…j−1]中”的说明

    若S[i]落在了T[1..j−1]的某个位置，不妨认为是k，根据最小编辑步数的定义，在k+1到j−1位置的字符必然是通过插入新字符完成的。因为共插入了j−k个字符，所以编辑次数为j−k次。而字符串S[1..i]经过编辑得到了T[1..k]，编辑次数为dp[i][k]，故dp[i][j]=dp[i][k] + (j−k)。

    因为最后的j−k次是插入操作，所以可以将j−k逐次归约到dp[i][k]中，即dp[i][k]+(j−k)=dp[i][k+1]+( j−k−1)归约到插入操作为1次，得到dp[i][k]+(j−k)=dp[i][k+1]+ ( j−k−1)=dp[i][k+2]+(j−k−2)=…=dp[i][k+(j−k−1)]+(j−k) − (j−k−1)=dp[i][j−1]+1。

    上述的解释清晰规范，但是为什么这样做呢？

    换一个角度来看，这其实就是字符串对齐的思路。例如，把字符串"ALGORITHM"变成"ALTRUISTIC"，可以先把相关字符各自对齐，如图5-1所示。

    然后把图5-1中上面的源串S[0..i]="ALGORITHM"编辑成下面的目标串T[0..j]= "ALTRUISTIC"时，需要枚举字符串S和T最后一个字符S[i]和T[j]对应的四种情况，即“字符-空白”“空白 字符”“字符 字符”“空白 空白”。

    由于其中的“空白 空白”是多余的编辑操作，所以事实上只存在以下三种情况。

（1）源串S有字符X，目标串T空白，即“S：字符X，T：空白”。要让S变成T，则意味着源串S要删除字符X，可得方程dp[i−1][j]+1。

（2）源串S空白，目标串T有字符Y，即“S：空白，T：字符Y”。要让S变成T，则意味着源串S要插入字符Y，可得方程dp[i][ j−1]+1。

（3）源串S中的字符X与目标串T中的字符Y对应，即“S：字符X，T：字符Y”。要让S变成T，则意味着要把源串S中的字符X替换成目标串T中的字符Y，可得方程dp[i−1][j−1]+(s[i] ==t[j]?0:1)。

    综上所述，如果用dp[i][j]表示源串S[0..i]和目标串T[0..j]的最短编辑距离，则可以写出简单的深度优先状态方程：

dp[i][j]=min{dp[i−1][j]+1, dp[i][j−1]+1, dp[i−1][j−1]+(S[i]==T[j] ? 0 : 1) }

参考代码如下：

// dp[i][j]表示源串S[0..i)和目标串target[0..j)的编辑距离
int EditDistance(char *S, char *T)
{
    int srcLength = strlen(S);
    int targetLength = strlen(T);
    int i, j;
    // 边界dp[i][0] = i，dp[0][j] = j
    for (i = 1; i <= srcLength; ++i)
    {
        dp[i][0] = i;
    }
    for (j = 1; j <= targetLength; ++j)
    {
        dp[0][j] = j;
    }
    for (i = 1; i <= srcLength; ++i)
    {
        for (j = 1; j <= targetLength; ++j)
        {
            if (S[i - 1] == T[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[srcLength][targetLength];
}
           

举一反三

    另类编辑距离

    传统的编辑距离里面有三种操作，即插入、删除、替换。假定现在编辑距离只允许两种操作，即插入一个字符和删除一个字符。请求出两个字符串的这种编辑距离，即把一个字符串变成另外一个字符串的最少操作次数。假定每个字符串长度不超过1000，只由大写

英文字母组成。

    寻找编辑距离3以内的数

    有1亿个数，输入1个数，找出与它的编辑距离在3以内的数。

问题扩展

实际上，“编辑距离”问题在搜索引擎中有着重要的用途。例如，搜索引擎关键字查询中拼写错误的提示，如图5-2所示，当输入Jult后，因为没有Jult这个单词，所以搜索引擎猜测你可能是输入错误，继而会提示你是不是找July。