Как работает Pythons SequenceMatcher?
Я немного озадачен двумя различными ответами, возвращаемыми 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
- Оценка сходства двух списков со строками
- сравнение строк в питоне, но не расстояние Левенштейна (я думаю)
- Сравнение рядов матричных чисел
- Целочисленный диапазон числа сравнения в Python
- Можно ли использовать pandas.dataframe.isin () с числовым параметром допуска?
Мой ответ не дает точных подробностей наблюдаемой проблемы, но содержит общее объяснение того, почему такие вещи могут происходить с свободно определенными различными методами.
По сути, все сводится к тому, что в общем случае,
-
более чем одна общая подпоследовательность одной длины может быть извлечена из заданной пары строк и
-
более длинные общие подпоследовательности могут казаться менее естественными для человеческого эксперта, чем более короткие.
Поскольку вы в этом конкретном случае озадачены, проанализируем общую идентификацию подпоследовательности по следующей паре строк:
-
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 .
- Правильно соскабливание и отображение японских символов с использованием Python Django BeautifulSoup и Curl
- Как скомпилировать Mod_Python 3.3.1 для Python 2.6 и Apache 2.2 в Windows?
- Преобразование других значений времени в формат даты и времени в Python
- Как Python сравнивает строку и int?
- Используйте сравнение Python 2 Dict в Python 3
- Как сравнить Enums в Python?
- Использование python для поиска повторяющихся имен в txt-файле
- python, как найти, если словарь содержит данные из другого словаря
- Сравнивая массивы NumPy так, чтобы NaN сравнивали равные
- Сравнение 2 списков, состоящих из словарей с уникальными ключами в python
- Сравнение производительности в Python: равное и не равное