文本比较算法Ⅴ——回顾贴,对前面几篇文章的回顾与质疑-阿里云开发者社区

开发者社区> nothingfinal> 正文

文本比较算法Ⅴ——回顾贴,对前面几篇文章的回顾与质疑

简介:
+关注继续查看

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

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

  文本比较算法Ⅲ——计算文本的相似度

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

  在写了本系列的前面几篇文章之后。有些网友质疑文章的正确性。在仔细的推敲之下,这些网友指正的不无道理。下面举一个反例,来质疑前面文章的正确性。

  文本:A:481234781;B:4411327431

  先按照LD算法,计算LD矩阵  

    4 4 1 1 3 2 7 4 3 1
  0 1 2 3 4 5 6 7 8 9 10
4 1 0 1 2 3 4 5 6 7 8 9
8 2 1 1 2 3 4 5 6 7 8 9
1 3 2 2 1 2 3 4 5 6 7 8
2 4 3 3 2 2 3 3 4 5 6 7
3 5 4 4 3 3 2 3 4 5 5 6
4 6 5 4 4 4 3 3 4 4 5 6
7 7 6 5 5 5 4 4 3 4 5 6
8 8 7 6 6 6 5 5 4 4 5 6
1 9 8 7 6 6 6 6 5 5 5 5

  可知,LD(A,B)=5,最佳匹配为

  A:4812347_81

  B:4411327431

  再按照LCS算法,计算LCS矩阵 

    4 4 1 1 3 2 7 4 3 1
  0 0 0 0 0 0 0 0 0 0 0
4 0 1 1 1 1 1 1 1 1 1 1
8 0 1 1 1 1 1 1 1 1 1 1
1 0 1 1 2 2 2 2 2 2 2 2
2 0 1 1 2 2 2 3 3 3 3 3
3 0 1 1 2 2 3 3 3 3 4 4
4 0 1 2 2 2 3 3 3 4 4 4
7 0 1 2 2 2 3 3 4 4 4 4
8 0 1 2 2 2 3 3 4 4 4 4
1 0 1 2 3 3 3 3 4 4 4 5

  可知,LCS(A,B)=5,匹配为

  A:4_81_234781

  B:44113274_31

  不是最佳匹配,而蓝色部分41241的确是最长公共子序列。只是和LD算法算出的最长公共子序列不一样而已。这个说明,最长公共子序列不是唯一的。问题出在哪?出在白色部分的第7行第8列这个单元格的回溯上,在这个单元格,有两个方向可以选,一个是向上,一个是向左,在前文中说到,回溯时优先考虑左上角、上方、下方的顺序。这个是不完全正确的。本例中,这个单元格向左回溯能得到最佳匹配。

 

  然后看看,Nakatsu算法的L矩阵

 

    4 8 1 2 3 4 7 8 1
  i=0 i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8 i=9
k=0 0 0 0 0 0 0 0 0 0 0
k=1 V 1 1 1 1 1 1 1 1 1
k=2 V V V 3 3 3 2 2 2 2
k=3 V V V V 6 5 5 5 5 3
k=4 V V V V V 9 8 7 7 7
k=5 V V V V V V V V V 10
k=6 V V V V V V V V V V
k=7 V V V V V V V V V V
k=8 V V V V V V V V V V
k=9 V V V V V V V V V V

  正如网友Sumtec指正,红色部分才是最长公共子序列的下标。

  出于好奇,我分析了L矩阵中那些数值

  L(k,i)=j→LCS(i,j)=k

  于是在LCS中,把这些对应值表示出来

  

    4 4 1 1 3 2 7 4 3 1
  0 0 0 0 0 0 0 0 0 0 0
4 0 1 1 1 1 1 1 1 1 1 1
8 0 1 1 1 1 1 1 1 1 1 1
1 0 1 1 2 2 2 2 2 2 2 2
2 0 1 1 2 2 2 3 3 3 3 3
3 0 1 1 2 2 3 3 3 3 4 4
4 0 1 2 2 2 3 3 3 4 4 4
7 0 1 2 2 2 3 3 4 4 4 4
8 0 1 2 2 2 3 3 4 4 4 4
1 0 1 2 3 3 3 3 4 4 4 5

  可以看出,L矩阵的元素表示每一行每个值出现的最左边的位置。这个能求出最长公共子序列。不过,能否求出最佳匹配,还得思量一番。

 

  最近在研究国外的两篇论文,估计研究完了,应该会有所收获。

  《A longest common subsequence algorithm suitable for similar text strings》

  《An almost-linear time and linear space algorithm for the longest common subsequence problem》

 

  在这里打个广告。这两篇论文,在网上能找到下载页面,但因为没有帐号,所以一直无法下载。昨天在“小米粒资源网”上发帖求助,不过半小时而已,就有人帮你下载,共享给你。效果非常好,在这里也向帮我下载的网友致敬。如果,你需要找一些学术论文(无论是中文的还是英文的),不妨在“小米粒资源网”试试,也许会有意想不到的惊喜。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10092 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13893 0
文本比较算法Ⅴ——回顾贴,对前面几篇文章的回顾与质疑
  文本比较算法Ⅰ——LD算法   文本比较算法Ⅱ——Needleman/Wunsch算法   文本比较算法Ⅲ——计算文本的相似度   文本比较算法Ⅳ——Nakatsu算法   在写了本系列的前面几篇文章之后。
636 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
11893 0
文本比较算法Ⅷ——再议Nakatsu算法
  研究文本比较算法已经一段时间了。把思路重新理了理。   在“文本比较算法Ⅳ——Nakatsu算法”中提到“对角线上的数字就是最长公共子序列的下标”。   在“文本比较算法Ⅶ——线性空间求最长公共子序列的Nakatsu算法”中提到“每行最左边不为V的数字就是最长公共子序列的下标”。
636 0
文本比较算法Ⅲ——计算文本的相似度
  在“文本比较算法Ⅰ——LD算法”中,介绍了编辑距离的计算。   在“文本比较算法Ⅱ——Needleman/Wunsch算法”中,介绍了最长公共子串的计算。   在给定的字符串A和字符串B,LD(A,B)表示编辑距离,LCS(A,B)表示最长公共子串的长度。
701 0
文本比较算法Ⅱ——Needleman/Wunsch算法
  在“文本比较算法Ⅰ——LD算法”中介绍了基于编辑距离的文本比较算法——LD算法。   本文介绍基于最长公共子串的文本比较算法——Needleman/Wunsch算法。   还是以实例说明:字符串A=kitten,字符串B=sitting   那他们的最长公共子串为ittn(注:最长公共子串不需要连续出现,但一定是出现的顺序一致),最长公共子串长度为4。
633 0
+关注
nothingfinal
软件开发,安全加密
1069
文章
341
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载