Алгоритм вычисления процентной разницы между двумя блоками текста

Question

Я занимаюсь поиском эффективного решения этой проблемы. Я изучил разные двигатели (diff-match-patch google, diff для python) и некоторые наиболее длинные алгоритмы общей цепочки.

Я надеялся на то, что вы, ребята, предложите, как решить эту проблему. Любой алгоритм или библиотека, в частности, вы хотели бы порекомендовать?

Спасибо.

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) 

Функция Левенштейна - от 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/). Вы также можете сравнить blobs текста на естественном языке семантически, используя N-граммы (http://en.wikipedia.org/wiki/N-gram).

Answer 4

link text Другой интересной областью может быть расстояние Левенштейна, описанное здесь.