今天分享一下编辑距离的相关东西
定义
首先说一下 什么是编辑距离? 在信息论语言学计算机科学中, 编辑距离是一个测量两个序列之间差异的度量通俗地说, 编辑距离就是从字符串 X 转换到 Y 需要的插入删除替换的最小个数对于只有插入删除替换操作的编辑距离, 是被 Levenshtein 首先提出和定义的, 所以这个编辑距离又叫作 Levenshtein 距离在后来, 又有一些基本操作被提了出来, 例如, 在输入文本的时候一个常见的错误就是会将相邻的字符的顺序输入反了, 所以交换两个相邻位置的字符也被提出作为编辑距离的一个基本单位当然还有一些其他的基本编辑操作被提了出来, 这里就不多做叙述在此次的文章中, 我们着重以 Levenshtein 距离为例做解说
属性
当然, 对于这些所谓的基本操作, 是有着硬性的要求的:
(1)每一个编辑操作的代价是正值比如我们的基本操作代价都是 1
(2)对于每一个操作, 它都有一个反向的操作, 且代价是一样的比如说插入和删除是一对反向操作, 代价都是 1.
在这些属性的要求下, 度量公式应该要满足如下的操作:
(1)d(a,b)=0 当且仅当 a=b 的时候, 这个是显而易见的, 这个是无需做任何操作的
(2)当 ab 的时候, d(a,b)>0, 因为这个至少需要一个非零成本的操作
(3)d(a,b)=d(b,a), 由于每个操作和它对应的你操作的成本是相等的, 这个是显而易见的
(4)三角不等式: d(a, c) d(a, b) + d(b, c)
举例
例如, kitten sitting 的编辑距离为 3
- kitten sitten (substitution of "s" for "k")
- sitten sittin (substitution of "i" for "e")
- sittin sitting (insertion of "g" at the end).
算法处理
对于编辑距离的处理上, 很多算法被提了出来, 并且在不断地改善中
(1)递归
这是一个简单但是相对低效的方法在这个方法中, 设 a=a1....an,b=b1....bm, 编辑距离为 dmn, 递归推倒定义如下:
实现的代码如下(主要参考的维基百科):
- #include<iostream>
- using namespace std;
- int getMin(int num1, int num2, int num3)
- {
- if (num1> num2)
- num1 = num2;
- if (num1> num3)
- num1 = num3;
- return num1;
- }
- // len_s and len_t are the number of characters in string s and t respectively
- int LevenshteinDistance(const char *s, int len_s, const char *t, int len_t)
- {
- int cost;
- /* base case: empty strings */
- if (len_s == 0) return len_t;
- if (len_t == 0) return len_s;
- /* test if last characters of the strings match */
- if (s[len_s-1] == t[len_t-1])
- cost = 0;
- else
- cost = 1;
- /* return minimum of delete char from s, delete char from t, and delete char from both */
- return getMin(LevenshteinDistance(s, len_s - 1, t, len_t ) + 1,
- LevenshteinDistance(s, len_s , t, len_t - 1) + 1,
- LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);
- }
- int main()
- {
- const char *str1 = "kitten";
- const char *str2 = "sitting";
- cout <<LevenshteinDistance(str1,strlen(str1) , str2, strlen(str2)) << endl;;
- return 0;
- }
首先解释一下公式和代码的相关思想:
(1)如果 ai+1=bj+1(两个串的最后一个字母是相同的), 那么 d(a[i+1],b[j+1])=d(a[i],b[j])
(2)在 ai+1bj+1 的时候, 那么 d(a[i+1],b[j+1])=1+min{d(a[i],b[j]),d(a[i],b[j+1]),d(a[i+1],b[j])}
(3)d(a[0],b[j])=j (0<=j<=n) , 当 a 的长度为 0 的时候
d(a[i],b[0])=i (0<=i<=m), 当 b 的长度为 0 的时候
这个递推的思想就是从两个字符串的末尾开始比对, 然后根据相应的情况进行递归这个算法是很低效的, 因为它在递归的过程中会重复计算很多子串的编辑距离, 这就像斐波那契数列的低效是一样的, 所以同样的一种提升方法就是将中间的子串的编辑距离存储下来, 这在下一个方法中将介绍
(2)矩阵迭代(动态规划)
在这里, 我们使用一个二维的矩阵 (可以使用二维数组进行表示) 去存放两个字符串中第一个字符串的所有前缀和第二个字符串的所有前缀情况下的编辑距离, 然后就可以使用动态规划的思想, 最终就可以计算出两个字符串之间的编辑距离关于此动态规划的方程其实在算法 (1) 中已经给出了, 所以此处就不在赘述了
下面先直接上代码:
- int LevenshteinDistance(const string &str1, const string &str2)
- {
- int row = str1.size()+1, col = str2.size()+1;
- int cost;
- vector<vector<int>> dist(row, vector<int>(col, 0));
- // 此处相当于算法 1 中的 str2 长度为 0 的时候
- for (int i = 1; i <row; i++)
- {
- dist[i][0] = i;
- }
- // 此处相当于算法 1 中 str1 长度为 0 的时候
- for (int j = 1; j < col; j++)
- {
- dist[0][j] = j;
- }
- for (int i = 1; i < row; i++)
- {
- for (int j = 1; j < col; j++)
- {
- // 此处和算法 1 中同样
- if (str1[i - 1] == str2[j - 1])
- cost = 0;
- else
- cost = 1;
- // 此处是将算法 1 中的递归改写
- dist[i][j] = getMin(dist[i - 1][j] + 1, dist[i][j - 1] + 1, dist[i - 1][j - 1] + cost);
- }
- }
- /* 此代码可用于查看 dist 表
- for (int i = 0; i < row; i++)
- {
- for (int j = 0; j < col; j++)
- {
- cout << dist[i][j] << " ";
- }
- cout << endl;
- }
- */
- return dist[row-1][col-1];
- }
下面是两个比对的例子的 dist 表, 可以自己运行代码去进行体会:
此代码中大部分是从算法 1 中改写过来的, 所以就不多做啰嗦了需要注意的就是 dist 表的大小, 在这里可以看出 dist 表的大小是比单词大出一个圈的, 也就是相对于单词的行和列而言, 要多 1 行一列从上图也是可以看出来的, 第一行第一列是需要空出来代表字符串为空的那个时候
(3)两行矩阵迭代
此算法是在算法 2 的基础上进行的一个空间上的改进, 从算法 2 中我们可以看出, 如果我们不需要存储编辑距离的路径的话, 那么我们完全可以不需要使用如此大的矩阵, 而只需要原来矩阵的两行, 然后进行不断地迭代, 最终便可以得到编辑距离
对于此处的矩阵的两行, 我们使用的时候是这样的, 比如说从头开始的时候, 我们用一个矩阵存储第一行中的距离值, 此时存储的值就是当字符串 str1 长度为 0 时, 所要存储的距离值, 然后第二后就用来存储我们上图中的 S 对应的行的值, 当 s 行处理完后, 则将此行的值和第一行交换, 然后进行第三行迭代, 依次类推, 直至结束对于动态规划部分, 我们可以这样看, 如图所示, 我们看图中标出的右下角的 2, 它是可以通过三种方法得到的, 如图中 3 个箭头所指的方向, 斜着的箭头对应的是替换操作, 两边的箭头对应的是插入和删除操作, 这样我们只需要得到取三个中成本最小的进行距离的更新即可
具体代码如下:
- int LevenshteinDistance(const string &str1, const string &str2)
- {
- vector<int> pre(str1.size()+1, 0);
- vector<int> cur(str1.size() + 1, 0);
- for (int i = 1; i < pre.size(); i++)
- {
- pre[i] = i;
- }
- for (int i = 0; i < str2.size(); i++)
- {
- cur[0] = i + 1;
- for (int j = 0; j < str1.size(); j++)
- {
- int insertCost = cur[j] + 1;
- int deleteCost = pre[j + 1] + 1;
- int substitudeCost;
- if (str1[j] == str2[i])
- substitudeCost = pre[j];
- else
- substitudeCost = pre[j] + 1;
- cur[j + 1] = getMin(deleteCost, insertCost, substitudeCost);
- }
- swap(pre, cur);
- }
- return pre[pre.size() - 1];
- }
(4)对于算法 3 中的方法, Hirschberg 算法通过结合此方法和分治算法, 以同样的时间和空间复杂度完成了编辑距离的计算, 并且能够得到最佳的编辑序列, 由于时间问题在这里就不提供了, 有兴趣的话可以参考 Hirschberg's algorithm, 里面是在算法 3 的基础上进行了分治算法的结合
来源: http://blog.csdn.net/qq_29883591/article/details/79681006