http://www.cnblogs.com/grenet/category/287355.html

文本比較算法

文本比較算法Ⅷ——再議Nakatsu算法 摘要: 研究文本比較算法已經一段時間了。把思路重新理了理。 在“文本比較算法Ⅳ——Nakatsu算法”中提到“對角線上的數字就是最長公共子序列的下标”。 在“文本比較算法Ⅶ——線性空間求最長公共子序列的Nakatsu算法”中提到“每行最左邊不為V的數字就是最長公共子序列的下标”。 以上兩個結論，網友Sumtec都提出了質疑，并提出了反例。經過本人的驗算，Sumtec是正确的，我的文章有問題。 不過，不能說Nakatsu算法有問題。在“文本比較算法Ⅶ——線性空間求最長公共子序列的Nakatsu算法”中的前半部分詳細闡述了Nakatsu算法的計算過程，這個是沒有問題的。隻是本人急于将其優化成線性空間，而. 閱讀全文 posted @  2011-03-15 15:15 萬倉一黍 閱讀(1705) |  評論 (11)  編輯 文本比較算法Ⅶ——線性空間求最長公共子序列的Nakatsu算法 摘要: 在參閱《A Longest Common Subsequence Algorithm Suitable for Similar Text Strings》（Narao Nakatsu，Yahiko Kambayashi，Shuzo Yajima著）後。發現該算法可以利用線性空間求出最長公共子序列。該算法的時間占用O（n（m-p+1）），p為最長公共子序列的長度。 字元串A和字元串B，計算LCS(A,B) 定義一：設M=Len(A)，N=Len(B)，不妨設M≤N。 定義二：A=a1a2……aM，表示A是由a1a2……aM這M個字元組成 B=b1b2……bN，表示B是由b1b2……bN這N個字. 閱讀全文 posted @  2011-03-11 09:31 萬倉一黍 閱讀(1738) |  評論 (12)  編輯 文本比較算法Ⅵ——用線性空間計算最大公共子序列（翻譯貼） 摘要: 研究文本比較算法有一段時間了。近日研讀了《A Linear Space Algorithm for Computing Maximal Common Subsequences》（D.S.Hirschberg著）。文章寫于1975年。很多其他的論文都會引用這篇論文，可見這篇論文的品質。同時，該文作者D.S.Hirschberg也寫了很多有關LCS的文章，也都是經典中的經典。 在研讀這篇文章之後，我将它翻譯成中文。由于本人的英語與文法都還不行，故翻譯的品質也就一般了，也歡迎廣大網友指正。Introduction導論 The problem of finding a longest common . 閱讀全文 posted @  2011-02-27 18:51 萬倉一黍 閱讀(12054) |  評論 (7)  編輯 文本比較算法Ⅴ——回顧貼，對前面幾篇文章的回顧與質疑 摘要: 文本比較算法Ⅰ——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 . 閱讀全文 posted @  2011-02-22 12:23 萬倉一黍 閱讀(2435) |  評論 (9)  編輯 文本比較算法Ⅳ——Nakatsu算法 摘要: 在“文本比較算法Ⅰ——LD算法”、“文本比較算法Ⅱ——Needleman/Wunsch算法”中介紹的LD算法和LCS算法都是基于動态規劃的。它們的時間複雜度O(MN)、空間複雜度O(MN)（在基于計算比對字元串情況下，是不可優化的。如果隻是計算LD和LCS，空間占用可以優化到O(M)）。 Nakatsu算法在計算比對字元串的情況下，有着良好的時間複雜度O(N(M-P))和空間複雜度O(N2)，而且在采取适當的優化手段時，可以将空間複雜度優化到O(N)，這是一個很誘人的結果。下面将全面介紹Nakatsu算法。 字元串A和字元串B，計算LCS(A,B) 定義一：設M=Len(A)，N=Len(B. 閱讀全文 posted @  2010-06-07 15:49 萬倉一黍 閱讀(2182) |  評論 (8)  編輯 文本比較算法Ⅲ——計算文本的相似度 摘要: 在“文本比較算法Ⅰ——LD算法”中，介紹了編輯距離的計算。 在“文本比較算法Ⅱ——Needleman/Wunsch算法”中，介紹了最長公共子串的計算。 在給定的字元串A和字元串B，LD(A,B)表示編輯距離，LCS(A,B)表示最長公共子串的長度。 如何來度量它們之間的相似度呢？ 不妨設S(A,B)來表示字元串A和字元串B的相似度。那麼，比較合理的相似度應該滿足下列性質。 性質一：0≤S(A,B)≤100%，0表示完全不相似，100%表示完全相等 性質二：S(A,B)=S(B,A) 目前，網上介紹的各種相似度的計算，都有各自的不盡合理的地方。 計算公式一：S(A,B)=1/(LD(A,B)+. 閱讀全文 posted @  2010-06-04 09:29 萬倉一黍 閱讀(2766) |  評論 (2)  編輯 文本比較算法Ⅱ——Needleman/Wunsch算法 摘要: 在“文本比較算法Ⅰ——LD算法”中介紹了基于編輯距離的文本比較算法——LD算法。 本文介紹基于最長公共子串的文本比較算法——Needleman/Wunsch算法。 還是以執行個體說明：字元串A=kitten，字元串B=sitting 那他們的最長公共子串為ittn（注：最長公共子串不需要連續出現，但一定是出現的順序一緻），最長公共子串長度為4。 定義： LCS(A,B)表示字元串A和字元串B的最長公共子串的長度。很顯然，LSC(A,B)=0表示兩個字元串沒有公共部分。 Rev(A)表示反轉字元串A Len(A)表示字元串A的長度 A+B表示連接配接字元串A和字元串B 性質： LCS(A,A)=Len. 閱讀全文 posted @  2010-06-03 09:38 萬倉一黍 閱讀(3306) |  評論 (8)  編輯 文本比較算法Ⅰ——LD算法 摘要: 在日常應用中，文本比較是一個比較常見的問題。文本比較算法也是一個老生常談的話題。 文本比較的核心就是比較兩個給定的文本（可以是位元組流等）之間的差異。目前，主流的比較文本之間的差異主要有兩大類。一類是基于編輯距離（Edit Distance）的，例如LD算法。一類是基于最長公共子串的（Longest Common Subsequence），例如Needleman/Wunsch算法等。 LD算法（Levenshtein Distance）又成為編輯距離算法（Edit Distance）。他是以字元串A通過插入字元、删除字元、替換字元變成另一個字元串B，那麼操作的過程的次數表示兩個字元串的差異。 . 閱讀全文