文章目录

1. 1. 编辑距离
   1. 1.1. 问题的描述
   2. 1.2. 思路与解法
   3. 1.3. 例子

编辑距离

---

我们都用过在线字典，应该会有这样一个体验：在输入我们想要单词的前几个字母时，输入框下的提示框会给我们推荐若干个字母相近的单词。或者另一种用户体验：拼写检查。那么这些单词推荐是怎么实现的呢？程序是怎么知道我们想要的单词的呢？这里就需要引入编辑距离(Edit distance)的概念了。

问题的描述

---

简单来讲，两个单词的编辑距离就是单词a通过增加字母、删减字母和修改字母等操作变成单词b，在这个过程中总共进行了多少次操作便是这两个单词的编辑距离。

比如snowy和sunny两个单词，我们可以这样来进行编辑：

方法1	方法2
S - N O W Y	- S N O W - Y
S U N N - Y	S U N - - N Y
Cost: 3	Cost: 5

对齐是一种很简单的方法，

对于方法1来说，增加U、将O改为N、删除W，共3步，所以编辑距离是3。

对于方法2来说，增加S、将S改为U、删除O、删除W、增加N，共5步，所以编辑距离是5。

思路与解法

---

我们可以抽象一下，求两个单词的编辑距离实际上就是求两个字符串的编辑距离。编辑距离的操作只有增、删、改三个操作，求出最少的操作数，那么就得到了两个字符串的编辑距离。

这里我们使用动态规划(Dynamic Programming)。

进一步抽象，两个字符串表示为a[1…m]，b[1…n]。既然是使用动态规划，那么我们需要记录在运算过程的中间结果。这里使用E[i][j]表示字符串ai[1…i]与字符串bj[1…j]的编辑距离。

那么最优子结构为E[i][j] = min{E[i-1][j]+1,E[i][j-1]+1,E[i-1][j-1]+diff(i,j)}，其中diff(i,j)表示当a[i]=b[j]，返回1；a[i]<>b[j]，返回0。

针对三种编辑操作，那么最优子结构应该是对这三种操作所得到的编辑距离进行求最小值。

1. 当编辑操作为字符串a[1…i-1]增加字符a[i]才能得到字符串b[1…j]，那么E[i][j]需要E[i-1][j]加1；
2. 当编辑操作为字符串a[1…i]删减字符a[i]才能得到字符串b[1…j-1]，那么E[i][j]需要E[i][j-1]加1；
3. 当编辑操作为修改，即当a[i]=b[j]时，那么E[i][j]需要E[i-1][j-1]+1；如果不等时，E[i][j]等于E[i-1][j-1]。

最后对这三个操作的结果进行求最小值即可。

例子

---

讲好了思路，那么我们举个例子：两个单词分别为EXPONENTIAL和POLYNOMIAL。

子结构E[4][3]表示EXPO与POL的最小编辑距离。

1. E[i-1][j]+1，即EXP与POL的最小编辑距离
2. E[i][j-1]+1，即EXPO与PO的最小编辑距离
3. E[i-1][j-1]+1(因为O不等于L)，即EXP与PO的最小编辑距离。

下面的图是EXPONENTIAL和POLYNOMIAL所有子结构，整个求解过程就是填个二维矩阵：