import difflib difflib.SequenceMatcher(isjunk=None, a='', b='', autojunk=True)
isjunk=None - функция, которая фильтрует мусорные элементы,a, b - сравниваемые последовательности,autojunk=True - отключение автоматической эвристики мусора.Конструктор класса SequenceMatcher() модуля difflib имеет необязательный аргумент isjunk должен быть None или функцией с одним аргументом, которая принимает элемент последовательности и возвращает True тогда и только тогда, когда элемент является “мусорным” и должен игнорироваться. Передача None для isjunk эквивалентна передаче lambda x: False, другими словами, никакие элементы не игнорируются.
Например если сравнивать строки как последовательности символов и при этом не надо учитывать пробелы или табуляции, то можно передать следующую лямбда-функцию:
lambda x: x in " \t"
Необязательные аргументы a и b - это сравниваемые последовательности. Обе по умолчанию пустые строки. Элементы обеих последовательностей должны быть хешируемыми.
Необязательный аргумент autojunk можно использовать для отключения автоматической эвристики мусора.
Объекты SequenceMatcher получают три атрибута данных:
bjunk - набор элементов b, для которых Isjunk=Truebpopular - набор не-мусорных элементов, считающихся популярными эвристикой, если она не отключенаb2j - словарь, отображающий остальные элементы b в список позиций, где они встречаются. Все три атрибута данных сбрасываются всякий раз, когда b сбрасывается с помощью методов set_seqs() или set_seq2(). Описание этих методов смотрите ниже.
SequenceMatcher() имеют следующие методы:set_seqs(a, b):Метод set_seqs(a, b) устанавливает две последовательности a, b для сравнения.
Класс SequenceMatcher() вычисляет и кэширует подробную информацию о второй b последовательности, поэтому, если нужно сравнить одну последовательность с разными последовательностями, используйте метод set_seq2(), чтобы задать последовательность один раз и вызвать метод set_seq1() повторно для сравнения с каждой новой последовательностью.
set_seq1(a):Метод set_seq1(a) устанавливает первую последовательность a для сравнения. Вторая сравниваемая последовательность b не изменяется.
set_seq2(b):Метод set_seq2(a) устанавливает вторую последовательность b для сравнения. Первая сравниваемая последовательность a не изменяется.
find_longest_match(alo, ahi, blo, bhi):Метод find_longest_match(alo, ahi, blo, bhi) найдет самый длинный соответствующий блок в a[alo:ahi] и b[blo:bhi].
Если isjunk был опущен или None, то метод find_longest_match() возвращает (i, j, k) такой, что a[i:i+k] равна b[j:j+k], где alo <= i <= i+k <= ahi и blo <= j <= j+k <= bhi. Для всех (i', j', k'), удовлетворяющих этим условиям, также выполняются дополнительные условия k >= k', i <= i', и если i == i', j <= j'. Другими словами, из всех совпадающих блоков вернется тот, который встретится раньше всего в последовательности a, а из всех совпадающих блоков, которые встречаются раньше всего в а, вернется тот, который встретится раньше всего в b.
>>> import difflib as df >>> s = df.SequenceMatcher(None, " abcd", "abcd abcd") >>> s.find_longest_match(0, 5, 0, 9) # Match(a=0, b=4, size=5)
Если был задан isjunk, то сначала определяется самый длинный совпадающий блок, как указано выше, но с ограничением, что в блоке не появляется "мусорный" элемент. Затем этот блок расширяется настолько, насколько это возможно, путем сопоставления только нежелательных элементов с обеих сторон. Таким образом, результирующий блок никогда не совпадает с мусором, за исключением того, что идентичный мусор оказывается рядом с совпадением.
Вот тот же пример, что и раньше, но с учетом того, что пробелы являются ненужными. Это препятствует непосредственному сопоставлению "abcd" с "abcd" в хвостовой части второй последовательности. Вместо этого только "abcd" может соответствовать, и соответствует самому левому "abcd" во второй последовательности:
>>> import difflib as df >>> s = df.SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd") >>> s.find_longest_match(0, 5, 0, 9) # Match(a=1, b=0, size=4)
Если блоки не совпадают, это возвращает (alo, blo, 0).
get_matching_blocks():Метод get_matching_blocks() возвращает список тройных кортежей, которые описывают непересекающиеся совпадающие подпоследовательности. Каждая тройка имеет вид (i, j, n) и означает, что a[i:i+n] == b[j:j+n]. Тройки монотонно увеличиваются в i и j.
Последний тройной кортеж является фиктивным и имеет значение (len(a), len(b), 0). Это единственный кортеж с n == 0. Если (i, j, n) и (i', j', n') являются смежными кортежами в списке, а второй не является последним кортежем в списке, то i+n < i' или j+n < j'. Другими словами, смежные тройные кортежи всегда описывают несмежные равные блоки.
>>> import difflib as df >>> s = df.SequenceMatcher(None, "abxcd", "abcd") >>> s.get_matching_blocks() # [ # Match(a=0, b=0, size=2), # Match(a=3, b=2, size=2), # Match(a=5, b=4, size=0) # ]
get_opcodes():Метод get_opcodes() возвращает список из кортежей с 5-ю элементами, которые описывают как получить последовательность a из последовательности b. Каждый кортеж имеет форму (tag, i1, i2, j1, j2). Первый кортеж имеет i1 == j1 == 0, а остальные кортежи имеют i1, равное i2 из предыдущего кортежа, а также j1, равное предыдущему j2.
Значения тегов tag - это строки, имеющие следующие значения:
'replace' - a[i1:i2] следует заменить на b[j1:j2].'delete' - a[i1:i2] должны быть удалены. Обратите внимание, что в этом случае j1 == j2.'insert' - b[j1:j2] должен быть вставлен в a[i1:i1]. Обратите внимание, что в этом случае i1 == i2.'equal' - a[i1:i2] == b[j1:j2] - подпоследовательности равны.>>> import difflib as df >>> a = "qabxcd" >>> b = "abycdf" >>> s = df.SequenceMatcher(None, a, b) >>> for tag, i1, i2, j1, j2 in s.get_opcodes(): ... print('{:7} a[{}:{}] --> b[{}:{}] {!r:>8} --> {!r}'.format( ... tag, i1, i2, j1, j2, a[i1:i2], b[j1:j2])) delete a[0:1] --> b[0:0] 'q' --> '' equal a[1:3] --> b[0:2] 'ab' --> 'ab' replace a[3:4] --> b[2:3] 'x' --> 'y' equal a[4:6] --> b[3:5] 'cd' --> 'cd' insert a[6:6] --> b[5:6] '' --> 'f'
get_grouped_opcodes(n=3):Метод get_grouped_opcodes() возвращает генератор групп с числом строк контекста до n.
Начиная с групп, возвращаемых get_opcodes(), этот метод разбивает меньшие кластеры изменений и устраняет промежуточные диапазоны, которые не имеют изменений.
Группы возвращаются в том же формате, что и get_opcodes().
ratio():Метод ratio() возвращает меру подобия/схожести последовательностей в виде числа с плавающей точкой в диапазоне [0, 1].
Где T - общее число элементов в обеих последовательностях, а M - число совпадений. Мера подобия последовательностей это 2.0*M/T. Обратите внимание, что мера подобия равная 1.0 будет, если последовательности идентичны, и 0.0, если они не имеют ничего общего.
Меру подобия/схожести вычислять дорого, если методы get_matching_blocks() или get_opcodes() еще не были вызваны. В этом случае нужно сначала вызвать методы quick_ratio() или real_quick_ratio(), чтобы получить верхнюю границу.
Важно: результат вызова метода ratio() может зависеть от порядка аргументов. Например:
>>> import difflib as df >>> df.SequenceMatcher(None, 'tide', 'diet').ratio() # 0.25 >>> df.SequenceMatcher(None, 'diet', 'tide').ratio() # 0.5
quick_ratio():Метод quick_ratio() относительно быстро возвращает верхнюю границу соотношения ratio().
real_quick_ratio():Метод real_quick_ratio() очень быстро возвращает верхнюю границу соотношения ratio(), но с большей погрешностью.
Три метода, которые возвращают отношение соответствия к общему количеству символов, могут давать разные результаты из-за разных уровней аппроксимации, хотя методы quick_ratio() и real_quick_ratio() так же хороши, как и ratio():
>>> import difflib as df >>> s = df.SequenceMatcher(None, "abcd", "bcde") >>> s.ratio() # 0.75 >>> s.quick_ratio() # 0.75 >>> s.real_quick_ratio() # 1.0
SequenceMatcher():В этом примере сравниваются две строки, считая пробелы ненужными:
import difflib as df s = df.SequenceMatcher(lambda x: x == " ", "private Thread currentThread;", "private volatile Thread currentThread;")
Метод ratio() возвращает число с плавающей точкой в [0, 1], измеряя сходство последовательностей. Как правило, значение ratio() выше 0,6 означает, что последовательности близки:
print(round(s.ratio(), 3)) # 0.866
Если нужно только совпадение последовательностей, удобно использовать метод get_matching_blocks():
for block in s.get_matching_blocks(): print("a[%d] and b[%d] match for %d elements" % block) # a[0] and b[0] match for 8 elements # a[8] and b[17] match for 21 elements # a[29] and b[38] match for 0 elements
Обратите внимание, что последний кортеж, возвращаемый get_matching_blocks(), всегда является фиктивным, (len(a), len(b), 0) и это единственный случай, когда в последнем кортеже число совпадающих элементов равно 0.
Если надо узнать, как изменить первую последовательность, что бы получить вторую, используйте метод get_opcodes():
for opcode in s.get_opcodes(): print("%6s a[%d:%d] b[%d:%d]" % opcode) # equal a[0:8] b[0:8] # insert a[8:8] b[8:17] # equal a[8:29] b[17:38]
SequenceMatcher.Алгоритм SequenceMatcher:
Базовый алгоритм SequenceMatcher() появился раньше и немного сложнее, чем алгоритм, опубликованный в конце 1980-х годов Ратклиффом и Обершелпом под гиперболическим названием "сопоставление с образцом гештальта". Идея состоит в том, чтобы найти самую длинную непрерывную совпадающую подпоследовательность, которая не содержит "мусорных" элементов. "Ненужные" элементы - это те элементы, которые в некотором смысле неинтересны, такие как пустые строки или пробелы. Обработка мусора является расширением алгоритма Ratcliff и Obershelp. Затем эта же идея рекурсивно применяется к фрагментам последовательностей слева и справа от совпадающей подпоследовательности.
Время:
Основной алгоритм Ratcliff-Obershelp - это кубическое время в худшем случае и квадратичное время в ожидаемом случае. SequenceMatcher() является квадратичным временем для наихудшего случая и имеет поведение ожидаемого случая, сложным образом зависящее от того, сколько элементов имеют общие последовательности, лучшее время линейно.
Автоматическая эвристика мусора:
SequenceMatcher поддерживает эвристику, которая автоматически обрабатывает определенные элементы последовательности как нежелательные. Эвристика подсчитывает, сколько раз каждый отдельный элемент появляется в последовательности. Если дубликаты элемента составляют более 1% последовательности, а длина последовательности составляет не менее 200 элементов, этот элемент помечается как "популярный" и рассматривается как нежелательный с целью сопоставления последовательности. Эту эвристику можно отключить, задав аргумент autojunk=False.