среда, 16 мая 2012 г.

difflib – Сравнение последовательностей

Предназначение:
Сравнение последовательностей, в особенности строк текста
Доступно в:
2.1 и более поздних версиях
Модуль difflib содержит инструменты для поиска и обработки различий между последовательностями. Особенно это полезно для сравнения текста. Он содержит функции, которые могут отображать отчёт о различиях используя различные общепринятые форматы.
Все примеры далее будут использовать данные строки из модуля difflib_data.py:
  1: text1 = """Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
  2: eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitor
  3: tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec
  4: mauris eget magna consequat convallis. Nam sed sem vitae odio
  5: pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
  6: metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
  7: urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
  8: suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
  9: adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristique
 10: enim. Donec quis lectus a justo imperdiet tempus."""
 11: text1_lines = text1.splitlines()
 12: 
 13: text2 = """Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
 14: eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
 15: tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec
 16: mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
 17: pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
 18: metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
 19: urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
 20: suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
 21: adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
 22: imperdiet tempus. Suspendisse eu lectus. In nunc. """
 23: text2_lines = text2.splitlines()

Сравнение текста


Класс Differ работает с последовательностями строк текста и выводит отчёт о разнице между ними в приемлемом для человека варианте.
Вывод, предоставляемый Differ похож на результат команды diff. Он включает входные данные обоих списков и маркеры, которые обозначают изменения.

  • Знак - перед строкой означает, что эта строка присутствует в первой последовательности, но отсутствует во второй.
  • Знак + перед строкой означает что строка присутствует во второй последовательности, но не в первой.
  • Если в строке есть дополнительные изменения в новой версии, то в выводе будет присутствовать строка со знаком ?, в которой будут помечены эти изменения.
  • Если строка не изменилась, она выводится с дополнительным отступом слева так, что она будет располагаться на том же уровне, что и строки с изменениями.

Для сравнения текста разбейте его на последовательность отдельных строк и передайте их compare().
  1: import difflib
  2: from difflib_data import *
  3: 
  4: d = difflib.Differ()
  5: diff = d.compare(text1_lines, text2_lines)
  6: print '\n'.join(diff)
Так как начало обоих сегментов одинаково, первая строка будет выведена без каких-либо дополнительных знаков:
1:   Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer

Во второй строчке появилась дополнительная запятая. Поэтому будут показаны обе версии строки и будет выведена дополнительная строка, под номером 4, в которой будет указан столбец, где содержится разница между строчками:
2: - eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitor
3: + eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
4: ?                                                         +
5:

Строки 6-9 показывают удаление лишнего пробела:
6: - tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec
7: ?                                                             -
8:
9: + tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec

Теперь мы видим более сложные изменения – замена нескольких слов в фразе:
10: - mauris eget magna consequat convallis. Nam sed sem vitae odio
11: ?                                              - --
12:
13: + mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
14: ?                                            +++ +++++   +
15:

Последние предложения в нашем тексте претерпели значительные изменения, так что отличия между ними отображены простым удалением старых вариантов строк и добавлением новых (строки 20-23):
16:   pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
17:   metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
18:   urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
19:   suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
20: - adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristique
21: - enim. Donec quis lectus a justo imperdiet tempus.
22: + adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
23: + imperdiet tempus. Suspendisse eu lectus. In nunc.

Функция ndiff() создаёт такой же вывод:
import difflib
from difflib_data import *

diff = difflib.ndiff(text1_lines, text2_lines)
print '\n'.join(list(diff))

Обработка специально предназначена для текстовых данных и подавления “шума” на входе.
$ python difflib_ndiff.py

  Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
- eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitor
+ eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
?                                                         +

- tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec
?                                                             -

+ tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec
- mauris eget magna consequat convallis. Nam sed sem vitae odio
?                                             ------

+ mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
?                                            +++        +++++++++

  pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
  metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
  urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
  suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
- adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristique
- enim. Donec quis lectus a justo imperdiet tempus.
+ adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
+ imperdiet tempus. Suspendisse eu lectus. In nunc.

Другие форматы вывода

В то время, как класс Differ выводит все строки исходных данных, unified diff выводит только изменённые строки и немного дополнительной информации. В Python 2.3 добавлена функция unified_diff() для получения такого формата вывода:
  1: import difflib
  2: from difflib_data import *
  3: 
  4: diff = difflib.unified_diff(text1_lines, text2_lines, lineterm='')
  5: print '\n'.join(list(diff))
  6: 
Результат должен оказаться знакомым тем, кто работает с различными версиями программ контроля версий:
$ python difflib_unified.py

---
+++
@@ -1,10 +1,10 @@
 Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
-eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitor
-tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec
-mauris eget magna consequat convallis. Nam sed sem vitae odio
+eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
+tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec
+mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
 pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
 metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
 urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
 suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
-adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristique
-enim. Donec quis lectus a justo imperdiet tempus.
+adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
+imperdiet tempus. Suspendisse eu lectus. In nunc.

Использование процедуры context_diff() даст Вам похожий результат:
$ python difflib_context.py

***
---
***************
*** 1,10 ****
  Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
! eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitor
! tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec
! mauris eget magna consequat convallis. Nam sed sem vitae odio
  pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
  metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
  urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
  suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
! adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristique
! enim. Donec quis lectus a justo imperdiet tempus.
--- 1,10 ----
  Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
! eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
! tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec
! mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
  pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
  metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
  urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
  suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
! adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
! imperdiet tempus. Suspendisse eu lectus. In nunc.

HTML результат

HtmlDiff создаёт результат в формате HTML с той же информацией, что и Diff.
  1: import difflib
  2: from difflib_data import *
  3: 
  4: d = difflib.HtmlDiff()
  5: print d.make_table(text1_lines, text2_lines)

В этом примере мы используем make_table(), который всего лишь возвращает тег table, содержащий информацию об отличиях. Метод make_file()создаст полностью отформатированный HTML файл.
Примечание: тут не отображён результат, так как он слишком большой. 

 


Лишние данные


Все функции, которые проводят анализ на различие принимают аргументы, задающие строки и символы, которые должны быть проигнорированы. Например, они могут быть использованы для пропуска разметки или лишних пробелов.
  1: # Это пример, взятый из difflib.py.
  2: 
  3: from difflib import SequenceMatcher
  4: 
  5: A = " abcd"
  6: B = "abcd abcd"
  7: 
  8: print 'A = %r' % A
  9: print 'B = %r' % B
 10: 
 11: print '\nWithout junk detection:'
 12: 
 13: s = SequenceMatcher(None, A, B)
 14: i, j, k = s.find_longest_match(0, 5, 0, 9)
 15: print '  i = %d' % i
 16: print '  j = %d' % j
 17: print '  k = %d' % k
 18: print '  A[i:i+k] = %r' % A[i:i+k]
 19: print '  B[j:j+k] = %r' % B[j:j+k]
 20: 
 21: print '\nTreat spaces as junk:'
 22: 
 23: s = SequenceMatcher(lambda x: x==" ", A, B)
 24: i, j, k = s.find_longest_match(0, 5, 0, 9)
 25: print '  i = %d' % i
 26: print '  j = %d' % j
 27: print '  k = %d' % k
 28: print '  A[i:i+k] = %r' % A[i:i+k]
 29: print '  B[j:j+k] = %r' % B[j:j+k]
 30: 

По умолчанию Differ обрабатывает все строки и символы без исключения, но для подавления “шума” можно использовать SequenceMatcher. ndiff() по умолчанию игнорируе пустые строки и знаки табуляции.
$ python difflib_junk.py

A = ' abcd'
B = 'abcd abcd'

Without junk detection:
  i = 0
  j = 4
  k = 5
  A[i:i+k] = ' abcd'
  B[j:j+k] = ' abcd'

Treat spaces as junk:
  i = 1
  j = 0
  k = 4
  A[i:i+k] = 'abcd'
  B[j:j+k] = 'abcd'

Сравнение произвольных типов


Класс SequenceMatcher сравнивает две последовательности любых типов, если их значения. Он использует алгоритм для поиска набольшего общего блока в последовательностях, игнорируя “мусор”, который не относится к реальным данным.
  1: import difflib
  2: from difflib_data import *
  3: 
  4: s1 = [ 1, 2, 3, 5, 6, 4 ]
  5: s2 = [ 2, 3, 5, 4, 6, 1 ]
  6: 
  7: print 'Initial data:'
  8: print 's1 =', s1
  9: print 's2 =', s2
 10: print 's1 == s2:', s1==s2
 11: print
 12: 
 13: matcher = difflib.SequenceMatcher(None, s1, s2)
 14: for tag, i1, i2, j1, j2 in reversed(matcher.get_opcodes()):
 15: 
 16:     if tag == 'delete':
 17:         print 'Remove %s from positions [%d:%d]' % (s1[i1:i2], i1, i2)
 18:         del s1[i1:i2]
 19: 
 20:     elif tag == 'equal':
 21:         print 'The sections [%d:%d] of s1 and [%d:%d] of s2 are the same' % \
 22:             (i1, i2, j1, j2)
 23: 
 24:     elif tag == 'insert':
 25:         print 'Insert %s from [%d:%d] of s2 into s1 at %d' % \
 26:             (s2[j1:j2], j1, j2, i1)
 27:         s1[i1:i2] = s2[j1:j2]
 28: 
 29:     elif tag == 'replace':
 30:         print 'Replace %s from [%d:%d] of s1 with %s from [%d:%d] of s2' % (
 31:             s1[i1:i2], i1, i2, s2[j1:j2], j1, j2)
 32:         s1[i1:i2] = s2[j1:j2]
 33: 
 34:     print 's1 =', s1
 35:     print 's2 =', s2
 36:     print
 37: 
 38: print 's1 == s2:', s1==s2

В данном примере мы сравниваем два списка из чисел и используем get_opcodes() для получения инструкций по преобразованию оригинального писка в его новую версию. Модификации применяются в обратном порядке, так что индексы списка остаются точными после добавления или удаления.
$ python difflib_seq.py

Initial data:
s1 = [1, 2, 3, 5, 6, 4]
s2 = [2, 3, 5, 4, 6, 1]
s1 == s2: False

Replace [4] from [5:6] of s1 with [1] from [5:6] of s2
s1 = [1, 2, 3, 5, 6, 1]
s2 = [2, 3, 5, 4, 6, 1]

The sections [4:5] of s1 and [4:5] of s2 are the same
s1 = [1, 2, 3, 5, 6, 1]
s2 = [2, 3, 5, 4, 6, 1]

Insert [4] from [3:4] of s2 into s1 at 4
s1 = [1, 2, 3, 5, 4, 6, 1]
s2 = [2, 3, 5, 4, 6, 1]

The sections [1:4] of s1 and [0:3] of s2 are the same
s1 = [1, 2, 3, 5, 4, 6, 1]
s2 = [2, 3, 5, 4, 6, 1]

Remove [1] from positions [0:1]
s1 = [2, 3, 5, 4, 6, 1]
s2 = [2, 3, 5, 4, 6, 1]

s1 == s2: True

SequenceMatcher работает как со встроенными классами, так и с пользовательскими классами, если они хешируемые.

Комментариев нет:

Отправить комментарий