研究文本比较算法已经一段时间了。把思路重新理了理。
在“文本比较算法Ⅳ——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的下标，又省去了计算匹配的时间。
有谁能给出计算最佳匹配的建设性意见吗？
本文转自万仓一黍博客园博客，原文链接：http://www.cnblogs.com/grenet/archive/2011/03/15/1984927.html，如需转载请自行联系原作者
