1. 问题描述
在很多应用场景下,需要用到两个串之间的距离或相似度的概念(这两个概念是相互对偶的:定义了其中的一个,可以导出另一个的定义,参见[1])。例如关键字推荐 —— 用户输入一个串,推荐给用户所有”类似的“串。
有很多种方法定义两个串之间的距离或相似度,例如 [2] 中第11章定义了很多串空间上的核函数,他们都可以用来度量两个串之间的相似度。编辑距离来源于近似字符串匹配问题。确定的字符串匹配问题寻求模式串 P 是否在文本串 T中出现,而近似字符串匹配允许出现少许误差。编辑距离的具体定义如下:
串 P 和串 T之间的编辑距离定义为为了将 P 变为 T 所需的最少的操作数,所允许的操作为:
- Substitution ------ 将 P 中的一个字符替换为 T 中出现的某个字符;
- Insertion ------ 往 P 中插入一个字符;
- Deletion ------ 删除 P 中的一个字符。
2. 动态规划解
用 D[i, j] 表示串 P[1, ..., i] 和串 T[1, ..., j] 之间的编辑距离,要将空串变为长度为i的串,只需连续进行 i 次 Insertion 操作即可。即有边界条件:
为了得到D[i, j]的递归方程,完成将 P[1, ..., i ] 和 T[1, ..., j ] 变成一样的最后一步操作,只能有以下三种可能:
- 第一种可能:用了 D[i - 1, j - 1] 步操作将 P[1, ..., i - 1] 和 T[1, ..., j - 1] 变成了一样,如果 Pi = Tj, 则完成任务,否则进行一次替换操作即可。因此
- 第二种可能:用了 D[i , j - 1] 步操作将 P[1, ..., i ] 和 T[1, ..., j - 1] 变成了一样,然后进行一次Insertion操作即可。此时
- 第三种可能:用了 D[i - 1 , j ] 步操作将 P[1, ..., i - 1 ] 和 T[1, ..., j ] 变成了一样,然后进行一次删除操作即可。此时
实际中D[i, j]应该是上述三种可能中的最小的。
3. c++实现
1 /* 计算由区间[beg1, end1)和[beg2, end2)指定的两个串之间的编辑距离
2 */
3 template<class Iter1, class Iter2>
4 int EditDist(const Iter1 &beg1, const Iter1 &end1, const Iter2 &beg2, const Iter2 &end2)
5 {
6 typedef std::vector<std::vector<int> > Matrix;
7 int m = end1 - beg1;
8 int n = end2 - beg2;
9 Matrix D(m + 1, std::vector<int>(n + 1));
10
11 for(int i = 0; i <= m; ++i)
12 D[i][0] = i;
13 for(int j = 0; j <= n; ++j)
14 D[0][j] = j;
15
16 Iter1 id1 = beg1;
17 for(int i = 1; i <=m; ++i, ++id1)
18 {
19 Iter2 id2 = beg2;
20 for(int j = 1; j <= n; ++j, ++id2)
21 D[i][j] = std::min(*id1 == *id2 ? D[i - 1][j - 1] : D[i - 1][j - 1] + 1,
22 std::min(D[i - 1][j] + 1, D[i][j - 1] + 1));
23 }
24 return D[m][n];
25 }
C++ Code
4. 分析和扩展
很显然,该算法的时间复杂度为 O(MN),空间复杂度也为 O(MN)。M和N分别为 P 和 T 的长度。
扩展一:允许三种操作的代价不一样,一般认为删除和插入操作的代价一样,而替换操作的代价比二者都高。此时边界条件和递归方程分别为:
扩展二: 允许第四种操作
Exchange ------ 交换 P 的相邻两个位置的字符
则,求递归方程时,会有第四种可能:用了D[i - 2, j - 2]步将 P[1, ..., i -2 ] 和 T[1, ..., j - 2] 变成了一样,而且 P[ i ] = T[ j -1 ], P[ i - 1 ] = T [ j ], P[ i ] ≠ P[ i - 1 ], 此时
参考资料
[1].Sergios Theodoridis, Konstantions Koutroumbas 模式识别(第四版)第11章
http://book.douban.com/subject/4603803/
[2]. 英)肖-泰勒 / (美)克瑞斯天尼 模式分析的核方法
http://book.douban.com/subject/1705547/
原文链接: https://www.cnblogs.com/ccvcgds/archive/2013/06/04/3116560.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/91162
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!