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

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

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

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

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

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

• my stackoverflow mysteries
• mystery

Для меня естественным матчем является "MYSTER" , а именно:

 my stackoverflow MYSTERies .................MYSTERy.. 

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

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

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

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

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

class difflib.SequenceMatcher

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

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 .