Как работает Pythons SequenceMatcher?

Question

Я немного озадачен двумя разными ответами, возвращенными SequenceMatcher в зависимости от порядка аргументов. Почему это так?

пример

SequenceMatcher не является коммутативным:

>>> from difflib import SequenceMatcher
>>> SequenceMatcher(None, "Ebojfm Mzpm", "Ebfo ef Mfpo").ratio()
0.6086956521739131

>>> SequenceMatcher(None, "Ebfo ef Mfpo", "Ebojfm Mzpm").ratio()
0.5217391304347826

Answer 1

SequenceMatcher.ratio внутренне использует SequenceMatcher.get_matching_blocks чтобы рассчитать соотношение, я проведу вас по шагам, чтобы увидеть, как это происходит:

SequenceMatcher.ratio

Возвращает список троек, описывающих совпадающие подпоследовательности. Каждая тройка имеет форму (i, j, n) и означает, что a[i:i+n] == b[j:j+n], Тройки монотонно увеличиваются в i а также j,

Последняя тройка является фиктивной и имеет значение (len(a), len(b), 0), Это единственная тройка с n == 0, If (i, j, n) а также (i', j', n') являются смежными тройками в списке, а вторая не последняя тройка в списке, то i+n != i' или же j+n != j'; другими словами, смежные тройки всегда описывают несмежные равные блоки.

ratio внутренне использует SequenceMatcher.get_matching_blocks результаты и суммирует размеры всех совпадающих последовательностей, возвращаемых SequenceMatcher.get_matching_blocks, Это точный исходный код difflib.py:

matches = sum(triple[-1] for triple in self.get_matching_blocks())

Приведенная выше строка является критической, потому что результат вышеприведенного выражения используется для вычисления отношения. Мы увидим это в ближайшее время и как это повлияет на расчет отношения.

---

m1 = SequenceMatcher(None, "Ebojfm Mzpm", "Ebfo ef Mfpo")
m2 = SequenceMatcher(None, "Ebfo ef Mfpo", "Ebojfm Mzpm")

matches1 = sum(triple[-1] for triple in m1.get_matching_blocks()) # matches1=7
matches2 = sum(triple[-1] for triple in m2.get_matching_blocks()) #matches=6

Как видите, у нас есть 7 и 6. Это просто суммы совпадающих подпоследовательностей, возвращаемых get_matching_blocks, Почему это важно? Вот почему, соотношение рассчитывается следующим образом (это из difflib исходный код):

def _calculate_ratio(matches, length):
    if length:
        return 2.0 * matches / length
    return 1.0

length является len(a) + len(b) где a это первая последовательность и b будучи второй последовательностью.

Хорошо, достаточно разговоров, нам нужны действия:

>>> length = len("Ebojfm Mzpm") + len("Ebfo ef Mfpo") 
>>> m1.ratio()
0.6086956521739131
>>> (2.0 * matches1 / length)  == m1.ratio()
True

Аналогично для m2:

>>> 2.0 * matches2 / length
0.5217391304347826 
>>> (2.0 * matches2 / length) == m2.ratio()
True

---

Примечание: не все SequenceMatcher(None a,b).ratio() == SequenceMatcher(None b,a).ratio() являются False иногда они могут быть True:

>>> s1 = SequenceMatcher(None, "abcd", "bcde").ratio()
>>> s2 = SequenceMatcher(None, "bcde", "abcd").ratio()
>>> s1 == s2
True

Если вам интересно, почему, это потому, что

sum(triple[-1] for triple in self.get_matching_blocks())

одинаково для обоих SequenceMatcher(None, "abcd", "bcde") а также SequenceMatcher(None, "bcde", "abcd") который 3.

Answer 2

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

По сути, все сводится к тому, что в общем случае

1. из заданной пары строк может быть извлечено более одной общей подпоследовательности одинаковой длины, и

2. более длинные общие подпоследовательности могут казаться менее естественными для эксперта-человека, чем более короткие.

Поскольку вы озадачены этим конкретным случаем, давайте проанализируем общую идентификацию подпоследовательности для следующей пары строк:

• my stackru mysteries
• mystery

Для меня естественное совпадение "MYSTER", следующее:

my stackru MYSTERies
.................MYSTERy..

Однако самое длинное совпадение полностью покрывает более короткую из двух строк следующим образом:

MY STackovERflow mYsteries
MY.ST.....ER......Y.......

Недостаток такого совпадения состоит в том, что оно вводит несколько совпадающих подблоков, тогда как (более короткое) естественное совпадение является смежным.

Поэтому алгоритмы различий настроены таким образом, чтобы их результаты были более приятными для конечного пользователя. В результате они не являются на 100% математически элегантными и поэтому не обладают свойствами, которые можно ожидать от чисто академического (а не практического) инструмента.

ДокументацияSequenceMatcher содержит соответствующую заметку:

class difflib.SequenceMatcher

Это гибкий класс для сравнения пар последовательностей любого типа, при условии что элементы последовательности могут быть хэшируемыми. Базовый алгоритм появился раньше и немного сложнее, чем алгоритм, опубликованный в конце 1980-х годов Ратклиффом и Обершелпом под гиперболическим названием "сопоставление с образцом гештальта". Идея состоит в том, чтобы найти самую длинную непрерывную совпадающую подпоследовательность, которая не содержит "ненужных" элементов (алгоритм Ratcliff и Obershelp не работает с мусором). Эта же идея затем применяется рекурсивно к частям последовательностей слева и справа от соответствующей подпоследовательности. Это не приводит к минимальным последовательностям редактирования, но имеет тенденцию давать совпадения, которые "выглядят правильно" для людей.

Answer 3

      from difflib import SequenceMatcher

texto1 = 'BRASILIA~DISTRITO FEDERAL, DF'
texto2 = 'BRASILIA-DISTRITO FEDERAL, '

tamanho_texto1 = len(texto1)
tamanho_texto2 = len(texto2)
tamanho_tot = tamanho_texto1 + tamanho_texto2

tot = 0
if texto1 <= texto2:
    for x in range(len(texto1)):
        y = texto1[x]

        if y in texto2:
            tot += 1
else:
    for x in range(len(texto2)):
        y = texto2[x]

        if y in texto1:
            tot += 1
        
print('sequenceM = ',SequenceMatcher(None, texto1,     texto2).ratio())
print('Total calculado = ',2*tot/tamanho_tot)