測量兩個字符串序列間相似度的算法

如何測量兩個字符串序列之間的相似度 - 百分比？測量兩個字符串序列間相似度的算法

我有兩個文本文件，並在文件中有序列是這樣寫

第一個文件：

AAA BBB DDD CCC GGG MMM AAA MMM

第二個文件：

BBB DDD CCC MMM AAA MMM

如何根據字符串的順序來衡量這兩個文件之間的相似度？

例如在上面的例子中，由於字符串的順序，兩個文件具有相似性，但是在文件-2中缺少一些字符串。什麼算法最適合解決這個問題，以便我可以測量兩個串中串的頻率不相似的順序是多少？

來源

2012-06-01 Dheeraj Agarwal

您可以使用Levenstein Distance算法。它分析將一個字符串轉換爲另一個字符串需要多少次編輯。 This文章解釋得非常好，並提供了一個示例實現。

從Codeproject複製粘貼：

1. Set n to be the length of s. ("GUMBO") 
    Set m to be the length of t. ("GAMBOL") 
    If n = 0, return m and exit. 
    If m = 0, return n and exit. 
    Construct two vectors, v0[m+1] and v1[m+1], containing 0..m elements. 
2. Initialize v0 to 0..m. 
3. Examine each character of s (i from 1 to n). 
4. Examine each character of t (j from 1 to m). 
5. If s[i] equals t[j], the cost is 0. 
    If s[i] is not equal to t[j], the cost is 1. 
6. Set cell v1[j] equal to the minimum of: 
    a. The cell immediately above plus 1: v1[j-1] + 1. 
    b. The cell immediately to the left plus 1: v0[j] + 1. 
    c. The cell diagonally above and to the left plus the cost: v0[j-1] + cost. 
7. After the iteration steps (3, 4, 5, 6) are complete, the distance is found in the cell v1[m].

來源

2012-06-01 05:58:00 alexn

您可以使用Python的SequenceMatcher.ratio函數測量序列相似性範圍[0, 1]的浮動。如果T是兩個序列中元素的總數，並且M是匹配的數量，這是2.0 * M/T。主要代碼如下：

from difflib import SequenceMatcher 
text1 = 'AAA BBB DDD CCC GGG MMM AAA MMM' 
text2 = 'BBB DDD CCC MMM AAA MMM' 
s = SequenceMatcher(None, text1, text2) 
similarity = s.ratio() * 100

我希望這可以幫到你！

來源

2015-02-19 08:00:03 AubreHarmon

測量兩個字符串序列間相似度的算法

回答

相關問題