算法計算betweem文本

Question

我一直在研究在尋找一個有效的解決方案，這兩種斑點％的差異。我研究了差異引擎（谷歌的diff-match-patch，python的diff）和一些最長的常見鏈算法。

我希望在得到關於如何解決這個問題，你們的建議。特別推薦的任何算法或庫？

謝謝。

Answer 1

我不知道什麼是「最長的公共[鏈？子？]]」與「百分比差異」的事，尤其是在你預期不同的兩個字符串之間一個非常小的差異％留言看了之後中間是一個字符（所以它們最長的公共子字符串大約是字符串長度的一半）。

忽略「最長公共」不協調，並限定由最大長度劃分的字符串（倍當然100 ;-)，那之間的編輯距離「百分比差」：

def levenshtein_distance(first, second): 
    """Find the Levenshtein distance between two strings.""" 
    if len(first) > len(second): 
     first, second = second, first 
    if len(second) == 0: 
     return len(first) 
    first_length = len(first) + 1 
    second_length = len(second) + 1 
    distance_matrix = [[0] * second_length for x in range(first_length)] 
    for i in range(first_length): 
     distance_matrix[i][0] = i 
    for j in range(second_length): 
     distance_matrix[0][j]=j 
    for i in xrange(1, first_length): 
     for j in range(1, second_length): 
      deletion = distance_matrix[i-1][j] + 1 
      insertion = distance_matrix[i][j-1] + 1 
      substitution = distance_matrix[i-1][j-1] 
      if first[i-1] != second[j-1]: 
       substitution += 1 
      distance_matrix[i][j] = min(insertion, deletion, substitution) 
    return distance_matrix[first_length-1][second_length-1] 

def percent_diff(first, second): 
    return 100*levenshtein_distance(a, b)/float(max(len(a), len(b))) 

a = "the quick brown fox" 
b = "the quick vrown fox" 
print '%.2f' % percent_diff(a, b) 

的Levenshtein函數從Stavros' blog。在這種情況下的結果是5.26（百分比差異）。

Answer 2

最長公共鏈？也許這將有助於：http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Answer 3

除了difflib和其他常見的子序列庫，如果它是自然語言文本，您可以查看詞幹，它將詞彙歸一化爲它們的根形式。您可以在Natural Language Toolkit（http://www.nltk.org/）庫中找到多個實現。您還可以使用N-Grams（http://en.wikipedia.org/wiki/N-gram）在語義上比較自然語言文本的斑點。

Answer 4

link text另一個感興趣的領域可能會在這裏描述的Levenshtein距離。