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

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

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

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

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

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

　　文本：A：481234781；B：4411327431

　　先按照LD算法，计算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矩阵

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矩阵

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中，把这些对应值表示出来

L矩阵在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》

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