文本比較算法Ⅷ——再議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，如需轉載請自行聯系原作者