文本比较算法Ⅰ——LD算法

  在日常应用中,文本比较是一个比较常见的问题。文本比较算法也是一个老生常谈的话题。

  文本比较的核心就是比较两个给定的文本(可以是字节流等)之间的差异。目前,主流的比较文本之间的差异主要有两大类。一类是基于编辑距离(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矩阵  

 

    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                      

 

  第二步:利用上述的公式一,计算第一行

 

    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                      

 

  第三步,利用上述的公示一,计算其余各行 

    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.ToCharArray

    Dim 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 Function
End 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矩阵,通过回溯,能找到匹配字串

  第一步:定位在矩阵的右下角  

    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,则回溯到左上角单元格

    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,回溯到左上角、上边、左边中值最小的单元格,若有相同最小值的单元格,优先级按照左上角、上边、左边的顺序

    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

    若当前单元格是在矩阵的第一行,则回溯至左边的单元格

    若当前单元格是在矩阵的第一列,则回溯至上边的单元格

    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。呵呵,这是什么概念?故,在比较长字符串的时候,还有其他性能更好的算法。留待后文详述。

时间: 2024-11-08 22:20:10

文本比较算法Ⅰ——LD算法的相关文章

文本比较算法Ⅳ——Nakatsu算法

在"文本比较算法Ⅰ--LD算法"."文本比较算法Ⅱ--Needleman/Wunsch算法"中介绍的LD算法和LCS算法都是基于动态规划的.它们的时间复杂度O(MN).空间复杂度O(MN)(在基于计算匹配字符串情况下,是不可优化的.如果只是计算LD和LCS,空间占用可以优化到O(M)). Nakatsu算法在计算匹配字符串的情况下,有着良好的时间复杂度O(N(M-P))和空间复杂度O(N2),而且在采取适当的优化手段时,可以将空间复杂度优化到O(N),这是一个很诱人

数据结构教程 第三课 算法及算法设计要求

本课主题: 算法及算法设计要求 教学目的: 掌握算法的定义及特性,算法设计的要求 教学重点: 算法的特性,算法设计要求 教学难点: 算法设计的要求 授课内容: 一.算法的定义及特性 1.定义: ispass(int num[4][4]) { int i,j; for(i=0;i<4;i++) for(j=0;j<4;j++) if(num[i][j]!=i*4+j+1)/*一条指令,多个操作*/ return 0; return 1; }/*上面是一个类似华容道游戏中判断游戏是否结束的算法*/

《算法帝国》:被算法和算法交易改变的未来

当我们用崭新的视角去观察与思考,世界就会变成另外的模样.这是我们筹备举办"改变未来的算法与算法交易"研讨会的初衷. 美国雄霸全球依赖华尔街与硅谷等强大支柱,而近年来,算法对华尔街的渗透与控制体现出颠覆未来产业生态的力量.图灵公司出版的<算法帝国>一书中介绍,2000年,华尔街通过计算机程序交易的比率不足美国股市交易量的10%:2008年上半年,自动化电子交易占了全美股市交易量的60%:现在,华尔街70%以上的交易依靠所谓的黑盒子或者算法交易(闪电交易)运行.银行家和股票经纪

算法——贪心算法

贪心算法 贪心算法通过一系列的选择来得到问题的解.它所做的每一个选择都是当前状态下局部的最好选择,即贪心选择. 贪心选择的一般特征:贪心选择性质和最优子结构性质. 贪心选择性质: 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到.这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别.在动态规划算法中,每步所做的选择往往依赖于相关子问题的解.因而只有在解出相关子问题后,才能做出选择.而在贪心算法中,仅在当前状态下做出最好选择,即局部最优选择.

缓存淘汰算法--LRU算法

[本文转载于缓存淘汰算法--LRU算法] 1. LRU 1.1. 原理 LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是"如果数据最近被访问过,那么将来被访问的几率也更高". 1.2. 实现 最常见的实现是使用一个链表保存缓存数据,详细算法实现如下: 1. 新数据插入到链表头部: 2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部: 3. 当链表满的时候,将链表尾部的数据丢弃. 1.3. 分析 [命中率] 当

重新想象 Windows 8 Store Apps (31) - 加密解密: 哈希算法, 对称算法

原文:重新想象 Windows 8 Store Apps (31) - 加密解密: 哈希算法, 对称算法 [源码下载] 重新想象 Windows 8 Store Apps (31) - 加密解密: 哈希算法, 对称算法 作者:webabcd 介绍重新想象 Windows 8 Store Apps 之 加密解密 hash 算法(MD5, SHA1, SHA256, SHA384, SHA512) hmac 算法(MD5, SHA1, SHA256, SHA384, SHA512) 本地数据的加密解

最短路径算法-Dijkstra算法的应用之单词转换(词梯问题)(转)

一,问题描述 在英文单词表中,有一些单词非常相似,它们可以通过只变换一个字符而得到另一个单词.比如:hive-->five:wine-->line:line-->nine:nine-->mine..... 那么,就存在这样一个问题:给定一个单词作为起始单词(相当于图的源点),给定另一个单词作为终点,求从起点单词经过的最少变换(每次变换只会变换一个字符),变成终点单词. 这个问题,其实就是最短路径问题. 由于最短路径问题中,求解源点到终点的最短路径与求解源点到图中所有顶点的最短路径复

文本比较算法Ⅸ——Primal-Dual算法

研究文本比较算法有一段时间.看到Primal-Dual算法,作为不同的求LCS算法,介绍如下. 原文在<An almost-linear time and linear space algorithm for the longest common subsequence problem>   比较文本: A=a1a2a3--am B=b1b2b3--bn   定义集合P={(i,j)|ai=bj} 则P={p1,p2,--,pl}       pk表示(ik,jk),1≤k≤l   定义三个比

Windows 8 Store Apps学习(31) 加密解密: 哈希算法, 对称算法

介绍 重新想象 Windows 8 Store Apps 之 加密解密 hash 算法(MD5, SHA1, SHA256, SHA384, SHA512) hmac 算法(MD5, SHA1, SHA256, SHA384, SHA512) 本地数据的加密解密 对 称算法(AES, DES, 3DES, RC2, RC4) 示例 1.演示如何使用 hash 算法(MD5, SHA1, SHA256, SHA384, SHA512) Crypto/Hash.xaml.cs /* * 演示如何使用