Difflib возвращает различное соотношение в зависимости от порядка последовательностей

Question

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

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

Answer 1

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

>>> 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 в последнее время, и хотя этот ответ опоздал, я подумал, что он может добавить небольшую специю к ответу, предоставленному Хьюдбруун Как показывает, что происходит визуально.

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

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

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

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

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. Анкет Соотношение рассчитывается как дано Здесь, в документации