文本比较算法Ⅷ——再议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)表示最佳匹配的长度。

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

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

　　

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

    本文转自万仓一黍博客园博客，原文链接：http://www.cnblogs.com/grenet/archive/2011/03/15/1984927.html，如需转载请自行联系原作者