文本比较算法Ⅷ——再议Nakatsu算法

  研究文本比较算法已经一段时间了。把思路重新理了理。

  在“文本比较算法Ⅳ——Nakatsu算法”中提到“对角线上的数字就是最长公共子序列的下标”。

  在“文本比较算法Ⅶ——线性空间求最长公共子序列的Nakatsu算法”中提到“每行最左边不为V的数字就是最长公共子序列的下标”。

  以上两个结论,网友Sumtec都提出了质疑,并提出了反例。经过本人的验算,Sumtec是正确的,我的文章有问题。

  不过,不能说Nakatsu算法有问题。在“文本比较算法Ⅶ——线性空间求最长公共子序列的Nakatsu算法”中的前半部分详细阐述了Nakatsu算法的计算过程,这个是没有问题的。只是本人急于将其优化成线性空间,而忽视了证明,故而得出了错误的结论。

 

  为何执着于Nakatsu算法?还是有原因的。

 

  文本比较算法的核心是什么?是为了求出两个文本的最佳匹配

  何为两个文本的最佳匹配?匹配是两个文本的对应关系,它包含了相同的部分,包含了相异的部分(增加、删除、修改)。对于两个文本来说,匹配不是唯一的。那最佳匹配就是包含了最多的相同部分(最长公共子序列),同时长度又是最短的。

  例如:

  A:GGATCGA

  B:GAATTCAGTTA

  最佳匹配为

    A:GGA_TC_G__A

    B:GAATTCAGTTA

    (蓝色部分表示相同部分,黑色表示相异部分,下同)

 

  又例如:

  A:481234781

  B:4411327431

  最佳匹配为:

    A:48123478_1

    B:4411327431  

 

  在研究一系列的LD算法和LCS算法后发现,LD算法侧重于相异部分,LCS算法侧重于相同部分

  故曾经有个推论“两文本A、B的最佳匹配长度为LD(A,B)+LCS(A,B)的值

 

  很不幸,这个结论又是错的。给个反例

  A:11111112

  B:23333333

  LD(A,B)=8;LCS(A,B)=1

  最佳匹配为:

    A:11111112_______

    B:_______23333333

  最佳匹配的长度为15≠8+1

 

  故两个文本的相似度的计算公式应该为LCS(A,B)/MATCH(A,B)。MATCH(A,B)表示最佳匹配的长度。

 

  如果只是为了计算一个最长公共子序列。那么在“文本比较算法Ⅵ——用线性空间计算最大公共子序列(翻译贴)”中的Hirschberg算法就能很好的解决这个问题。但是要注意的是,不是每个最长公共子序列都能求出最佳匹配的。因此,Hirschberg算法对于求最佳匹配无能为力。

 

  我现在对于求最佳匹配的思路就是求出每一个最长公共子序列,依次算出各自的匹配,从中找到最佳匹配。

 

  我想,这个时候,Nakatsu算法派上用处了。可以知道,当最长公共子序列的长度为P时,Nakatsu算法占用的空间为P(m-P),是个二次空间,且知道当P为m/2时,占用空间最大,为m2/4。但好处是能遍历到所有的最长公共子序列(没有证明)。且每组解的值是指向B的下标,每组解的横坐标指向A的下标,又省去了计算匹配的时间。

  

  有谁能给出计算最佳匹配的建设性意见吗?

 

上一篇:Python-列表元素的判断and遍历


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