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

文本比较算法Ⅰ——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》

 

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

作者:万仓一黍
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
上一篇:文本比较算法Ⅷ——再议Nakatsu算法


下一篇:《嵌入式系统数字视频处理权威指南》——第2章 视频处理介绍2.1数字视频:像素和分辨率