difflib возвращает разное соотношение в зависимости от последовательности последовательностей

Question

Кто-нибудь знает, почему эти два возвращают разные отношения.

>>> import difflib 
>>> difflib.SequenceMatcher(None, '10101789', '11426089').ratio() 
0.5 
>>> difflib.SequenceMatcher(None, '11426089', '10101789').ratio() 
0.625 

Answer 1

This дает некоторые идеи о том, как соответствующие работы.

>>> import difflib 
>>> 
>>> def print_matches(a, b): 
...  s = difflib.SequenceMatcher(None, a, b) 
...  for block in s.get_matching_blocks(): 
...   print "a[%d] and b[%d] match for %d elements" % block 
...  print s.ratio() 
... 
>>> print_matches('01017', '14260') 
a[0] and b[4] match for 1 elements 
a[5] and b[5] match for 0 elements 
0.2 
>>> print_matches('14260', '01017') 
a[0] and b[1] match for 1 elements 
a[4] and b[2] match for 1 elements 
a[5] and b[5] match for 0 elements 
0.4 

Похоже, что он соответствует максимально возможному для первой последовательности ко второму и продолжается от матчей. В этом случае ('01017', '14260') правое совпадение находится на 0, последнем символе, поэтому дальнейшие совпадения справа не возможны. В этом случае ('14260', '01017'), совпадение 1s и 0 все еще доступны для соответствия справа, поэтому найдено два совпадения.

Я думаю, что алгоритм сопоставления является коммутативным по отношению к отсортированным последовательностям.

Answer 2

В последнее время я работал с difflib, и хотя этот ответ опаздывает, я подумал, что он может добавить немного специи к ответу, предоставленному hughdbrown, поскольку он показывает, что происходит визуально.

Перед тем, как перейти к фрагмент кода, позвольте мне процитировать documentation

Идея заключается в том, чтобы найти самую длинную непрерывную сопрягая подпоследовательность, не содержит элементов «мусора»; эти «нежелательные» элементы - это те, которые в некотором смысле неинтересны, например пустые строки или пробелы. (Обработка нежелательной почты является расширением алгоритма Ratcliff и Obershelp ). Затем эта же идея применяется рекурсивно к частям последовательностей слева и справа от подпоследовательности . Это не дает минимальных последовательностей редактирования, но имеет тенденцию , чтобы получить совпадения, которые «выглядят правильно» для людей.

Я думаю, сравнивая первую строку против вторых, а затем найти матчи выглядит правильнодостаточно люди. Это хорошо объясняется в ответе hughdbrown.

Теперь попробуйте и запустить этот фрагмент кода:

def show_matching_blocks(a, b): 
    s = SequenceMatcher(None, a, b) 
    m = s.get_matching_blocks() 
    seqs = [a, b] 

    new_seqs = [] 
    for select, seq in enumerate(seqs): 
     i, n = 0, 0 
     new_seq = '' 
     while i < len(seq): 
      if i == m[n][select]: 
       new_seq += '{' + seq[m[n][select]:m[n][select] + m[n].size] + '}' 
       i += m[n].size 
       n += 1 
      elif i < m[n][select]: 
       new_seq += seq[i:m[n][select]] 
       i = m[n][select] 
     new_seqs.append(new_seq) 
    for seq, n in zip(seqs, new_seqs): 
     print('{} --> {}'.format(seq, n)) 
    print('') 

a, b = '10101789', '11426089' 
show_matching_blocks(a, b) 
show_matching_blocks(b, a) 

Выход:

10101789 --> {1}{0}1017{89} 
11426089 --> {1}1426{0}{89} 

11426089 --> {1}{1}426{0}{89} 
10101789 --> {1}0{1}{0}17{89} 

Части внутри скобок ({}) являются совпадающие части. Я просто использовал SequenceMatcher.get_matching_blocks(), чтобы поместить соответствующие блоки в фигурные скобки для лучшей видимости. Вы можете четко видеть разницу, когда порядок отменен. В первом порядке есть 4 матча, поэтому соотношение составляет 2*4/16=0.5. Но когда порядок отменен, теперь есть 5 совпадений, поэтому отношение становится 2*5/16=0.625. Соотношение рассчитывается как заданное here in the documentation