编辑距离动态规划c语言,第五章动态规划 – 5.2 字符串编辑距离 - 编程之法：面试和算法心得...

╰+攻爆jí腚メ 2022-10-15 01:58 2阅读 0赞

题目描述

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

在给定位置上插入一个字符

替换任意字符

删除任意字符

写一个程序，返回最小操作数，使得对源串进行这些操作后等于目标串，源串和目标串的长度都小于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\]中

接下来，咱们重点解释下上述3个式子的含义

关于dp\[i-1\]\[j\] + 1, s.t. 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.t. 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.t. 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”，那么把相关字符各自对齐后，如下图所示：

![20140616114324296][]

把图中上面的源串S\[0…i\] = “ALGORITHM”编辑成下面的目标串T\[0…j\] = “ALTRUISTIC”，我们枚举字符串S和T最后一个字符s\[i\]、t\[j\]对应四种情况：(字符-空白)(空白-字符)(字符-字符)(空白-空白)。

由于其中的(空白-空白)是多余的编辑操作。所以，事实上只存在以下3种情况：

下面的目标串空白，即S + 字符X，T + 空白，S变成T，意味着源串要删字符

dp\[i – 1, j\] + 1

上面的源串空白，S + 空白，T + 字符，S变成T，最后，在S的最后插入“字符”，意味着源串要添加字符

dp\[i, j – 1\] + 1

上面源串中的的字符跟下面目标串中的字符不一样，即S + 字符X，T + 字符Y，S变成T，意味着源串要修改字符

dp\[i – 1, j – 1\] + (s\[i\] == t\[j\] ? 0 : 1)

综上，可以写出简单的DP状态方程：

//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) \}

//分别表示：删除1个，添加1个，替换1个(相同就不用替换)。

参考代码如下：

//dp\[i\]\[j\]表示源串source\[0-i)和目标串target\[0-j)的编辑距离

int EditDistance(char \*pSource, char \*pTarget)

int srcLength = strlen(pSource);

int targetLength = strlen(pTarget);

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 (pSource\[i - 1\] == pTarget\[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\];

举一反三

1、传统的编辑距离里面有三种操作，即增、删、改，我们现在要讨论的编辑距离只允许两种操作，即增加一个字符、删除一个字符。我们求两个字符串的这种编辑距离，即把一个字符串变成另外一个字符串的最少操作次数。假定每个字符串长度不超过1000，只有大写英文字母组成。

2、有一亿个数，输入一个数，找出与它编辑距离在3以内的数，比如输入6(0110)，找出0010等数，数是32位的。

问题扩展

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

![29.7.jpg][]

当然，面试官还可以继续问下去，如请问，如何设计一个比较这篇文章和上一篇文章相似性的算法？

[20140616114324296]: https://img.blog.csdn.net/20140616114324296
[29.7.jpg]: https://www.wenjiangs.com/wp-content/uploads/2020/docimg18/29.7.jpg

编辑距离动态规划c语言,第五章动态规划 – 5.2 字符串编辑距离 - 编程之法：面试和算法心得...

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关动态规划之编辑距离总结篇

相关 leetcode 编辑距离动态规划

相关经典动态规划：编辑距离

相关算法Day10-动态规划之编辑距离

相关编辑距离动态规划c语言,第五章动态规划 – 5.2 字符串编辑距离 - 编程之法：面试和算法心得...

相关 ACM 动态规划编辑距离

相关动态规划之编辑距离问题*

相关动态规划法（十一）编辑距离

相关【leetcode】编辑距离（动态规划）

相关【动态规划】编辑距离