文本比较算法Ⅰ |
您所在的位置:网站首页 › java文本比对算法 › 文本比较算法Ⅰ |
在日常应用中,文本比较是一个比较常见的问题。文本比较算法也是一个老生常谈的话题。 文本比较的核心就是比较两个给定的文本(可以是字节流等)之间的差异。目前,主流的比较文本之间的差异主要有两大类。一类是基于编辑距离(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算法的代码,用的是VB2005。代码格式修正于2012年1月6日。 Public Class clsLD Private Shared mA() As Char Private Shared mB() As Char Public Shared Function LD(ByVal A As String, ByVal B As String) As Integer mA = A.ToCharArray mB = B.ToCharArrayDim L(A.Length, B.Length) As Integer Dim i As Integer, j As Integer For i = 1 To A.Length L(i, 0) = i Next For j = 1 To B.Length L(0, j) = j Next For i = 1 To A.Length For j = 1 To B.Length If mA(i - 1) = mB(j - 1) Then L(i, j) = L(i - 1, j - 1) Else L(i, j) = Min(L(i - 1, j - 1), L(i - 1, j), L(i, j - 1)) + 1 End If Next Next Return L(A.Length, B.Length) End Function Public Shared Function Min(ByVal A As Integer, ByVal B As Integer, ByVal C As Integer) As Integer Dim I As Integer = A If I > B Then I = B If I > C Then I = C Return I End FunctionEnd Class
这个LD算法时间复杂度为O(MN),空间复杂度为O(MN),如果进行优化的话,空间复杂度可以为O(M),优化的代码这里不再详述了。参看“计算字符串的相似度(VB2005)” 我们往往不仅仅是计算出字符串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 搜索晚整个匹配路径,匹配字串也就完成了
从上面可以看出,LD算法在不需要计算出匹配字串的话,时间复杂度为O(MN),空间复杂度经优化后为O(M) 不过,如果要计算匹配字符串的话,时间复杂度为O(MN),空间复杂度由于需要利用LD矩阵计算匹配路径,故空间复杂度仍然为O(MN)。这个在两个字符串都比较短小的情况下,能获得不错的性能。不过,如果字符串比较长的情况下,就需要极大的空间存放矩阵。例如:两个字符串都是20000字符,则LD矩阵的大小为20000*20000*2=800000000Byte=800MB。呵呵,这是什么概念?故,在比较长字符串的时候,还有其他性能更好的算法。留待后文详述。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |