文本比较算法Ⅱ——Needleman/Wunsch算法

简介:

 在“文本比较算法Ⅰ——LD算法”中介绍了基于编辑距离的文本比较算法——LD算法。

  本文介绍基于最长公共子串的文本比较算法——Needleman/Wunsch算法。

  还是以实例说明:字符串A=kitten,字符串B=sitting

  那他们的最长公共子串为ittn(注:最长公共子串不需要连续出现,但一定是出现的顺序一致),最长公共子串长度为4。

  

  定义:

  LCS(A,B)表示字符串A和字符串B的最长公共子串的长度。很显然,LSC(A,B)=0表示两个字符串没有公共部分。

  Rev(A)表示反转字符串A

  Len(A)表示字符串A的长度

  A+B表示连接字符串A和字符串B

 

  性质:

  LCS(A,A)=Len(A)

  LCS(A,"")=0

  LCS(A,B)=LCS(B,A)

  0≤LCS(A,B)≤Min(Len(A),Len(B))

  LCS(A,B)=LCS(Rev(A),Rev(B))

  LCS(A+C,B+C)=LCS(A,B)+Len(C)

  LCS(A+B,A+C)=Len(A)+LCS(B,C)

  LCS(A,B)≥LCS(A,C)+LCS(B,C)

  LCS(A+C,B)≥LCS(A,B)+LCS(B,C)

 

  为了讲解计算LCS(A,B),特给予以下几个定义

  A=a1a2……aN,表示A是由a1a2……aN这N个字符组成,Len(A)=N

  B=b1b2……bM,表示B是由b1b2……bM这M个字符组成,Len(B)=M

  定义LCS(i,j)=LCS(a1a2……ai,b1b2……bj),其中0≤i≤N,0≤j≤M

  故:  LCS(N,M)=LCS(A,B)

      LCS(0,0)=0

      LCS(0,j)=0

      LCS(i,0)=0

 

  对于1≤i≤N,1≤j≤M,有公式一

  若ai=bj,则LCS(i,j)=LCS(i-1,j-1)+1

  若ai≠bj,则LCS(i,j)=Max(LCS(i-1,j-1),LCS(i-1,j),LCS(i,j-1))

 

  计算LCS(A,B)的算法有很多,下面介绍的Needleman/Wunsch算法是其中的一种。和LD算法类似,Needleman/Wunsch算法用的都是动态规划的思想。在Needleman/Wunsch算法中还设定了一个权值,用以区分三种操作(插入、删除、更改)的优先级。在下面的算法中,认为三种操作的优先级都一样。故权值默认为1。

  

  举例说明:A=GGATCGA,B=GAATTCAGTTA,计算LCS(A,B)

  第一步:初始化LCS矩阵

    G A A T T C A G T T A
  0 0 0 0 0 0 0 0 0 0 0 0
G 0                      
G 0                      
A 0                      
T 0                      
C 0                      
G 0                      
A 0                      

  第二步:利用公式一,计算矩阵的第一行

    G A A T T C A G T T A
  0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0                      
A 0                      
T 0                      
C 0                      
G 0                      
A 0                      

   第三步:利用公式一,计算矩阵的其余各行

    G A A T T C A G T T A
  0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1 2 2 2 2
A 0 1 2 2 2 2 2 2 2 2 2 2
T 0 1 2 2 3 3 3 3 3 3 3 3
C 0 1 2 2 3 3 4 4 4 4 4 4
G 0 1 2 2 3 3 3 4 5 5 5 5
A 0 1 2 3 3 3 3 4 5 5 5 6

  则,LCS(A,B)=LCS(7,11)=6

  可以看出,Needleman/Wunsch算法实际上和LD算法是非常接近的。故他们的时间复杂度和空间复杂度也一样。时间复杂度为O(MN),空间复杂度为O(MN)。空间复杂度经过优化,可以优化到O(M),但是一旦优化就丧失了计算匹配字串的机会了。由于代码和LD算法几乎一样。这里就不再贴代码了。

  

  还是以上面为例A=GGATCGA,B=GAATTCAGTTA,LCS(A,B)=6

  他们的匹配为:

    A:GGA_TC_G__A

    B:GAATTCAGTTA

  如上面所示,蓝色表示完全匹配,黑色表示编辑操作,_表示插入字符或者是删除字符操作。如上面所示,蓝色字符有6个,表示最长公共子串长度为6。

  利用上面的Needleman/Wunsch算法矩阵,通过回溯,能找到匹配字串

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

    G A A T T C A G T T A
  0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1 2 2 2 2
A 0 1 2 2 2 2 2 2 2 2 2 2
T 0 1 2 2 3 3 3 3 3 3 3 3
C 0 1 2 2 3 3 4 4 4 4 4 4
G 0 1 2 2 3 3 3 4 5 5 5 5
A 0 1 2 3 3 3 3 4 5 5 5 6

  第二步:回溯单元格,至矩阵的左上角

    若ai=bj,则回溯到左上角单元格

    G A A T T C A G T T A
  0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1 2 2 2 2
A 0 1 2 2 2 2 2 2 2 2 2 2
T 0 1 2 2 3 3 3 3 3 3 3 3
C 0 1 2 2 3 3 4 4 4 4 4 4
G 0 1 2 2 3 3 3 4 5 5 5 5
A 0 1 2 3 3 3 3 4 5 5 5 6

     若ai≠bj,回溯到左上角、上边、左边中值最大的单元格,若有相同最大值的单元格,优先级按照左上角、上边、左边的顺序

    G A A T T C A G T T A
  0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1 2 2 2 2
A 0 1 2 2 2 2 2 2 2 2 2 2
T 0 1 2 2 3 3 3 3 3 3 3 3
C 0 1 2 2 3 3 4 4 4 4 4 4
G 0 1 2 2 3 3 3 4 5 5 5 5
A 0 1 2 3 3 3 3 4 5 5 5 6

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

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

    G A A T T C A G T T A
  0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1 2 2 2 2
A 0 1 2 2 2 2 2 2 2 2 2 2
T 0 1 2 2 3 3 3 3 3 3 3 3
C 0 1 2 2 3 3 4 4 4 4 4 4
G 0 1 2 2 3 3 3 4 5 5 5 5
A 0 1 2 3 3 3 3 4 5 5 5 6

    依照上面的回溯法则,回溯到矩阵的左上角

  第三步:根据回溯路径,写出匹配字串

    若回溯到左上角单元格,将ai添加到匹配字串A,将bj添加到匹配字串B

    若回溯到上边单元格,将ai添加到匹配字串A,将_添加到匹配字串B

    若回溯到左边单元格,将_添加到匹配字串A,将bj添加到匹配字串B

    搜索晚整个匹配路径,匹配字串也就完成了

 

  可以看出,LD算法和Needleman/Wunsch算法的回溯路径是一样的。这样找到的匹配字串也是一样的。

  不过,Needleman/Wunsch算法和LD算法一样,若要找出匹配字串,空间的复杂度就一定是O(MN),在文本比较长的时候,是极为耗用存储空间的。故若要计算出匹配字串,还得用其他的算法,留待后文介绍。

 

  

 

  

 

     本文转自万仓一黍博客园博客,原文链接:http://www.cnblogs.com/grenet/archive/2010/06/03/1750454.html,如需转载请自行联系原作者

相关文章
|
数据采集 算法 数据可视化
基于Python的k-means聚类分析算法的实现与应用,可以用在电商评论、招聘信息等各个领域的文本聚类及指标聚类,效果很好
本文介绍了基于Python实现的k-means聚类分析算法,并通过微博考研话题的数据清洗、聚类数量评估、聚类分析实现与结果可视化等步骤,展示了该算法在文本聚类领域的应用效果。
500 1
|
机器学习/深度学习 存储 人工智能
文本情感识别分析系统Python+SVM分类算法+机器学习人工智能+计算机毕业设计
使用Python作为开发语言,基于文本数据集(一个积极的xls文本格式和一个消极的xls文本格式文件),使用Word2vec对文本进行处理。通过支持向量机SVM算法训练情绪分类模型。实现对文本消极情感和文本积极情感的识别。并基于Django框架开发网页平台实现对用户的可视化操作和数据存储。
293 0
文本情感识别分析系统Python+SVM分类算法+机器学习人工智能+计算机毕业设计
|
机器学习/深度学习 自然语言处理 算法
解读未知:文本识别算法的突破与实际应用
解读未知:文本识别算法的突破与实际应用
解读未知:文本识别算法的突破与实际应用
|
机器学习/深度学习 数据采集 算法
Python基于KMeans算法进行文本聚类项目实战
Python基于KMeans算法进行文本聚类项目实战
|
数据采集 自然语言处理 数据可视化
基于Python的社交媒体评论数据挖掘,使用LDA主题分析、文本聚类算法、情感分析实现
本文介绍了基于Python的社交媒体评论数据挖掘方法,使用LDA主题分析、文本聚类算法和情感分析技术,对数据进行深入分析和可视化,以揭示文本数据中的潜在主题、模式和情感倾向。
1591 0
|
文字识别 算法 Java
文本,保存图片09,一个可以用id作为图片名字的pom插件,利用雪花算法生成唯一的id
文本,保存图片09,一个可以用id作为图片名字的pom插件,利用雪花算法生成唯一的id
|
算法 数据可视化 搜索推荐
基于python的k-means聚类分析算法,对文本、数据等进行聚类,有轮廓系数和手肘法检验
本文详细介绍了基于Python实现的k-means聚类分析算法,包括数据准备、预处理、标准化、聚类数目确定、聚类分析、降维可视化以及结果输出的完整流程,并应用该算法对文本数据进行聚类分析,展示了轮廓系数法和手肘法检验确定最佳聚类数目的方法。
465 0
|
算法 JavaScript
「AIGC算法」将word文档转换为纯文本
使用Node.js模块`mammoth`和`html-to-text`,该代码示例演示了如何将Word文档(.docx格式)转换为纯文本以适应AIGC的文本识别。流程包括将Word文档转化为HTML,然后进一步转换为纯文本,进行格式调整,并输出到控制台。转换过程中考虑了错误处理。提供的代码片段展示了具体的实现细节,包括关键库的导入和转换函数的调用。
283 0
|
文字识别 算法 Shell
突破边界:文本检测算法的革新与应用前景
突破边界:文本检测算法的革新与应用前景
突破边界:文本检测算法的革新与应用前景
|
人工智能 自然语言处理 算法
Similarities:精准相似度计算与语义匹配搜索工具包,多维度实现多种算法,覆盖文本、图像等领域,支持文搜、图搜文、图搜图匹配搜索
Similarities:精准相似度计算与语义匹配搜索工具包,多维度实现多种算法,覆盖文本、图像等领域,支持文搜、图搜文、图搜图匹配搜索
Similarities:精准相似度计算与语义匹配搜索工具包,多维度实现多种算法,覆盖文本、图像等领域,支持文搜、图搜文、图搜图匹配搜索

热门文章

最新文章