在日常应用中,文本比较是一个比较常见的问题。文本比较算法也是一个老生常谈的话题。
文本比较的核心就是比较两个给定的文本(可以是字节流等)之间的差异。目前,主流的比较文本之间的差异主要有两大类。一类是基于编辑距离 (Edit Distance)的,例如LD算法。一类是基于最长公共子串的(Longest Common Subsequence),例如Needleman/Wunsch算法等。
LD算法(Levenshtein Distance)又成为编辑距离算法(Edit Distance)。他是以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。
例如:字符串A:kitten如何变成字符串B:sitting。
第一步:kitten——》sitten。k替换成s
第二步:sitten——》sittin。e替换成i
第三步:sittin——》sitting。在末尾插入g
故kitten和sitting的编辑距离为3
定义说明:
LD(A,B)表示字符串A和字符串B的编辑距离。很显然,若LD(A,B)=0表示字符串A和字符串B完全相同
Rev(A)表示反转字符串A
Len(A)表示字符串A的长度
A+B表示连接字符串A和字符串B
有下面几个性质:
LD(A,A)=0
LD(A,"")=Len(A)
LD(A,B)=LD(B,A)
0≤LD(A,B)≤Max(Len(A),Len(B))
LD(A,B)=LD(Rev(A),Rev(B))
LD(A+C,B+C)=LD(A,B)
LD(A+B,A+C)=LD(B,C)
LD(A,B)≤LD(A,C)+LD(B,C)(注:像不像“三角形,两边之和大于第三边”)
LD(A+C,B)≤LD(A,B)+LD(B,C)
为了讲解计算LD(A,B),特给予以下几个定义
A=a1a2……aN,表示A是由a1a2……aN这N个字符组成,Len(A)=N
B=b1b2……bM,表示B是由b1b2……bM这M个字符组成,Len(B)=M
定义LD(i,j)=LD(a1a2……ai,b1b2……bj),其中0≤i≤N,0≤j≤M
故: LD(N,M)=LD(A,B)
LD(0,0)=0
LD(0,j)=j
LD(i,0)=i
对于1≤i≤N,1≤j≤M,有公式一
若ai=bj,则LD(i,j)=LD(i-1,j-1)
若ai≠bj,则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1
举例说明:A=GGATCGA,B=GAATTCAGTTA,计算LD(A,B)
第一步:初始化LD矩阵
LD算法矩阵
G
A
A
T
T
C
A
G
T
T
A
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
G
1 |
|
|
|
|
|
|
|
|
|
|
|
G
2 |
|
|
|
|
|
|
|
|
|
|
|
A
3 |
|
|
|
|
|
|
|
|
|
|
|
T
4 |
|
|
|
|
|
|
|
|
|
|
|
C
5 |
|
|
|
|
|
|
|
|
|
|
|
G
6 |
|
|
|
|
|
|
|
|
|
|
|
A
7 |
|
|
|
|
|
|
|
|
|
|
|
第二步:利用上述的公式一,计算第一行
LD算法矩阵
G
A
A
T
T
C
A
G
T
T
A
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
G
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
G
2 |
|
|
|
|
|
|
|
|
|
|
|
A
3 |
|
|
|
|
|
|
|
|
|
|
|
T
4 |
|
|
|
|
|
|
|
|
|
|
|
C
5 |
|
|
|
|
|
|
|
|
|
|
|
G
6 |
|
|
|
|
|
|
|
|
|
|
|
A
7 |
|
|
|
|
|
|
|
|
|
|
|
第三步,利用上述的公示一,计算其余各行
LD算法矩阵
G
A
A
T
T
C
A
G
T
T
A
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
G
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
G
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
6 |
7 |
8 |
9 |
A
3 |
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
8 |
T
4 |
3 |
2 |
2 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
C
5 |
4 |
3 |
3 |
2 |
2 |
2 |
3 |
4 |
5 |
6 |
7 |
G
6 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
3 |
4 |
5 |
6 |
A
7 |
6 |
5 |
4 |
4 |
4 |
4 |
3 |
4 |
4 |
5 |
5 |
则LD(A,B)=LD(7,11)=5。
这个LD算法时间复杂度为O(MN),空间复杂度为O(MN);
我们往往不仅仅是计算出字符串A和字符串B的编辑距离,还要能得出他们的匹配结果。
以上面为例A=GGATCGA,B=GAATTCAGTTA,LD(A,B)=5
他们的匹配为:
A:GGA_TC_G__A
B:GAATTCAGTTA
如上面所示,蓝色表示完全匹配,黑色表示编辑操作,_表示插入字符或者是删除字符操作。如上面所示,黑色字符有5个,表示编辑距离为5。
利用上面的LD矩阵,通过回溯,能找到匹配字串
第一步:定位在矩阵的右下角
LD算法矩阵
G
A
A
T
T
C
A
G
T
T
A
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
G
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
G
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
6 |
7 |
8 |
9 |
A
3 |
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
8 |
T
4 |
3 |
2 |
2 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
C
5 |
4 |
3 |
3 |
2 |
2 |
2 |
3 |
4 |
5 |
6 |
7 |
G
6 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
3 |
4 |
5 |
6 |
A
7 |
6 |
5 |
4 |
4 |
4 |
4 |
3 |
4 |
4 |
5 |
5 |
第二步:回溯单元格,至矩阵的左上角
若ai=bj,则回溯到左上角单元格
LD算法矩阵
G
A
A
T
T
C
A
G
T
T
A
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
G
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
G
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
6 |
7 |
8 |
9 |
A
3 |
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
8 |
T
4 |
3 |
2 |
2 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
C
5 |
4 |
3 |
3 |
2 |
2 |
2 |
3 |
4 |
5 |
6 |
7 |
G
6 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
3 |
4 |
5 |
6 |
A
7 |
6 |
5 |
4 |
4 |
4 |
4 |
3 |
4 |
4 |
5 |
5 |
若ai≠bj,回溯到左上角、上边、左边中值最小的单元格,若有相同最小值的单元格,优先级按照左上角、上边、左边的顺序
LD算法矩阵
G
A
A
T
T
C
A
G
T
T
A
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
G
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
G
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
6 |
7 |
8 |
9 |
A
3 |
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
8 |
T
4 |
3 |
2 |
2 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
C
5 |
4 |
3 |
3 |
2 |
2 |
2 |
3 |
4 |
5 |
6 |
7 |
G
6 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
3 |
4 |
5 |
6 |
A
7 |
6 |
5 |
4 |
4 |
4 |
4 |
3 |
4 |
4 |
5 |
5 |
若当前单元格是在矩阵的第一行,则回溯至左边的单元格
若当前单元格是在矩阵的第一列,则回溯至上边的单元格
LD算法矩阵
G
A
A
T
T
C
A
G
T
T
A
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
G
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
G
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
6 |
7 |
8 |
9 |
A
3 |
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
8 |
T
4 |
3 |
2 |
2 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
C
5 |
4 |
3 |
3 |
2 |
2 |
2 |
3 |
4 |
5 |
6 |
7 |
G
6 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
3 |
4 |
5 |
6 |
A
7 |
6 |
5 |
4 |
4 |
4 |
4 |
3 |
4 |
4 |
5 |
5 |
依照上面的回溯法则,回溯到矩阵的左上角
第三步:根据回溯路径,写出匹配字串
若回溯到左上角单元格,将ai添加到匹配字串A,将bj添加到匹配字串B
若回溯到上边单元格,将ai添加到匹配字串A,将_添加到匹配字串B
若回溯到左边单元格,将_添加到匹配字串A,将bj添加到匹配字串B
搜索晚整个匹配路径,匹配字串也就完成了
参考来源:http://www.cnblogs.com/grenet/archive/2010/06/01/1748448.html
分享到:
相关推荐
文本比较算法Ⅰ——LD算法.doc
计算机算法——设计与分析导论(第三版).pdf 英文版
遗传算法——理论、应用与软件实现 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。由于其具有健壮性,特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。以遗传...
求全局最优化的几种确定性算法——杨永健,CAJ版本,用于数学建模参考
本书全面系统的介绍了遗传算法的基本理论和方法,重点介绍了遗传算法的经典应用和国内外的新发展。
基于LD文本比较算法而实现的小程序,LD文本比较算法请参照以下英文网址
数据结构算法——Visual.C.6.0程序集].侯识忠.清晰。 节省硬盘资源,放在这里留用。
用MATLAB实现进化策略算法——求特定方程的极小值.pdf
带你入门常见的机器学习分类算法——逻辑回归、朴素贝叶斯、KNN、SVM、决策树.pdf带你入门常见的机器学习分类算法——逻辑回归、朴素贝叶斯、KNN、SVM、决策树.pdf带你入门常见的机器学习分类算法——逻辑回归、朴素...
带你入门常见的机器学习分类算法——逻辑回归、朴素贝叶斯、KNN、SVM、决策树.docx带你入门常见的机器学习分类算法——逻辑回归、朴素贝叶斯、KNN、SVM、决策树.docx带你入门常见的机器学习分类算法——逻辑回归、...
广义神经网络的聚类算法——网络入侵聚类.rar
王小平《遗传算法——理论、应用与软件实现》书籍 pdg格式
遗传算法——理论、应用与软件实现
动态规划算法——C++实现经典案例——初级
python 智能算法——简单例子蚁群算法.py
自动识别技术 实验报告1 曼切斯特编码碰撞检测算法 ——曼切斯特编码碰撞检测的python实现算法 曼彻斯特编码(Manchester Encoding),也叫做相位编码(PE)是一个同步时钟编码技术,被物理层用来编码一个同步位流的...
人工免疫算法——matlab,免责声明,朋友分享
python 智能算法——简单例子免疫算法.py
客户运营核心大数据与算法——刘忠义
贪心算法——用最少硬币找出n分钱的问题,以及代码。终于解决了