Python Difflib Deltas и сравнение Ndiff

Я хотел сделать что-то вроде того, что, по моему мнению, делают системы управления изменениями: они сравнивают два файла и сохраняют небольшую разницу при каждом изменении файла. Я читал эту страницу: http://docs.python.org/library/difflib.html и это, видимо, не укладывается у меня в голове.

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

Разве нельзя добраться только до чистых изменений? Причина, по которой я спрашиваю, надеюсь, очевидна - для экономии места на диске.
Я мог бы просто каждый раз сохранять весь кусок кода, но было бы лучше сохранить текущий код один раз, а затем небольшие изменения изменений.

Я также все еще пытаюсь понять, почему многие функции difflib возвращают генератор вместо списка, в чем преимущество?

Подойдет ли мне difflib или мне нужно найти более профессиональный пакет с большим количеством функций?

# Python Difflib demo 
# Author: Neal Walters 
# loosely based on http://ahlawat.net/wordpress/?p=371
# 01/17/2011 

# build the files here - later we will just read the files probably 
file1Contents="""
for j = 1 to 10: 
   print "ABC"
   print "DEF" 
   print "HIJ"
   print "JKL"
   print "Hello World"
   print "j=" + j 
   print "XYZ"
"""

file2Contents = """
for j = 1 to 10: 
   print "ABC"
   print "DEF" 
   print "HIJ"
   print "JKL"
   print "Hello World"
   print "XYZ"
print "The end"
"""

filename1 = "diff_file1.txt" 
filename2 = "diff_file2.txt" 

file1 = open(filename1,"w") 
file2 = open(filename2,"w") 

file1.write(file1Contents) 
file2.write(file2Contents) 

file1.close()
file2.close() 
#end of file build 

lines1 = open(filename1, "r").readlines()
lines2 = open(filename2, "r").readlines()

import difflib

print "\n FILE 1 \n" 
for line in lines1:
  print line 

print "\n FILE 2 \n" 
for line in lines2: 
  print line 

diffSequence = difflib.ndiff(lines1, lines2) 

print "\n ----- SHOW DIFF ----- \n" 
for i, line in enumerate(diffSequence):
    print line

diffObj = difflib.Differ() 
deltaSequence = diffObj.compare(lines1, lines2) 
deltaList = list(deltaSequence) 

print "\n ----- SHOW DELTALIST ----- \n" 
for i, line in enumerate(deltaList):
    print line



#let's suppose we store just the diffSequence in the database 
#then we want to take the current file (file2) and recreate the original (file1) from it
#by backward applying the diff 

restoredFile1Lines = difflib.restore(diffSequence,1)  # 1 indicates file1 of 2 used to create the diff 

restoreFileList = list(restoredFile1Lines)

print "\n ----- SHOW REBUILD OF FILE1 ----- \n" 
# this is not showing anything! 
for i, line in enumerate(restoreFileList): 
    print line

Спасибо!

ОБНОВИТЬ:

contextDiffSeq = difflib.context_diff(lines1, lines2) 
contextDiffList = list(contextDiffSeq) 

print "\n ----- SHOW CONTEXTDIFF ----- \n" 
for i, line in enumerate(contextDiffList):
    print line

----- ПОКАЗАТЬ РАЗНИЦУ КОНТЕКСТА -----




* 5,9 **

 print "HIJ"

 print "JKL"

 print "Hello World"
  • напечатайте "j=" + j

    напечатать "XYZ"

--- 5,9 ----

 print "HIJ"

 print "JKL"

 print "Hello World"

 print "XYZ"
  • печать "Конец"

Еще одно обновление:

В старые времена Panvalet an Librarian, инструментов управления исходным кодом для мэйнфреймов, вы могли создать такой набор изменений:

++ADD 9
   print "j=" + j 

Что просто означает добавление строки (или строк) после строки 9. Затем есть такие слова, как ++ REPLACE или ++ UPDATE. http://www4.hawaii.gov/dags/icsd/ppmo/Stds_Web_Pages/pdf/it110401.pdf


person NealWalters    schedule 20.01.2011    source источник


Ответы (3)


Различия должны содержать достаточно информации, чтобы можно было вставить одну версию в другую, поэтому да, для вашего эксперимента с однострочным изменением в очень маленьком документе хранение всех документов может быть дешевле.

Библиотечные функции возвращают итераторы, чтобы облегчить работу клиентам, которым не хватает памяти или которым нужно просмотреть только часть результирующей последовательности. В Python это нормально, потому что каждый итератор можно преобразовать в список с очень коротким выражением list(an_iterator).

Большая часть различий выполняется в строках текста, но можно перейти к посимвольному, и difflib делает это. Взгляните на класс объектов Differ в difflib.

Повсюду примеры используют удобный для человека вывод, но различия управляются внутри гораздо более компактным, удобным для компьютера способом. Кроме того, различия обычно содержат избыточную информацию (например, текст удаляемой строки), чтобы сделать исправление и слияние изменений безопасными. Избыточность может быть удалена вашим собственным кодом, если вам это удобно.

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

Однажды я написал общий механизм сравнения вместе с одним из оптимальных алгоритмов примерно в 1250 строках Java (JRCS). Он работает для любой последовательности элементов, которую можно сравнить на равенство. Если вы хотите создать собственное решение, я думаю, что перевод/повторная реализация JRCS займет не более 300 строк Python.

Обработка вывода, созданного difflib, чтобы сделать его более компактным, также является опцией. Это пример из небольшого файла с тремя изменениями (добавление, изменение и удаление):

---  
+++  
@@ -7,0 +7,1 @@
+aaaaa
@@ -9,1 +10,1 @@
-c= 0
+c= 1
@@ -15,1 +16,0 @@
-    m = re.match(code_re, text)

То, что говорит патч, можно легко сжать до:

+7,1 
aaaaa
-9,1 
+10,1
c= 1
-15,1

Для вашего собственного примера сжатый вывод будет:

-8,1
+9,1
print "The end"

В целях безопасности может быть хорошей идеей оставить начальный маркер ('>') для строк, которые должны быть вставлены.

-8,1
+9,1
>print "The end"

Это ближе к тому, что вам нужно?

Это простая функция для уплотнения. Вам придется написать свой собственный код, чтобы применить патч в этом формате, но это должно быть просто.

def compact_a_unidiff(s):
    s = [l for l in s if l[0] in ('+','@')]
    result = []
    for l in s:
        if l.startswith('++'):
            continue
        elif l.startswith('+'):
            result.append('>'+ l[1:])
        else:
            del_cmd, add_cmd = l[3:-3].split()
            del_pair, add_pair = (c.split(',') for c in (del_cmd,add_cmd))
            if del_pair[1]  != '0':
                result.append(del_cmd)
            if add_pair[1] != '0':
                result.append(add_cmd)
    return result
person Apalala    schedule 20.01.2011
comment
Спасибо (см. обновление и примечание для @Karl выше). Я, вероятно, буду иметь дело с короткими примерами кода - в целом 10-20 строк - поэтому, думаю, мне лучше отказаться от концепции diff. И как бы вы сохранили diff в большом двоичном объекте базы данных? Сериализуйте его или выполните ''.join - person NealWalters; 20.01.2011
comment
Все зависит от цели. Почему вы хотите сравнить маленькие документы? Сколько документов? Сколько ревизий в каждом? Если взять под контроль diffing engine, то формат хранилища можно сделать намного компактнее любой из ревизий в среднем случае (вспомните quicksort). Если вы хотите использовать/показывать различия в определенные моменты времени, то для ваших небольших документов вы можете вычислять их на лету, когда они вам нужны, с помощью difflib. Дайте мне знать, что вы решили (мне нужен предлог, чтобы потратить день на перевод JRCS.Diff на Python). - person Apalala; 20.01.2011
comment
Основываясь на информации здесь, я просто собираюсь сохранить весь кусок кода на данный момент. Если мой проект расцветет, и у меня будет миллион пользователей, тогда я смогу побеспокоиться о стоимости дискового пространства для облачного хостинга, а затем настроить его. Если вы переводите на Python, постарайтесь сделать его независимым от C, чтобы он запускал Google App Engine (или две версии). - person NealWalters; 21.01.2011
comment
Добавил еще одно обновление в исходный пост. Я проснулся этим утром, думая о том, как старые инструменты для мэйнфреймов использовали для этого... - person NealWalters; 21.01.2011
comment
@NealWalters Формат, используемый RCS/CVS, также очень компактен и может использоваться со многими библиотеками. Я думаю, было бы неплохо еще немного поиграть с difflib. Например, вы можете попробовать использовать унифицированный формат без строк контекста и обработать вывод, чтобы сделать его более компактным. См. мое последнее редактирование для примера. - person Apalala; 21.01.2011
comment
@Apalala Да, это то, к чему я мог бы отправиться в будущем. Но, как я сказал выше, давайте посмотрим, смогу ли я вообще добиться успеха сайта, прежде чем я буду сжигать циклы для экономии места на диске. - person NealWalters; 21.01.2011

Я также все еще пытаюсь понять, почему многие функции difflib возвращают генератор вместо списка, в чем преимущество?

Ну, подумайте об этом на секунду - если вы сравниваете файлы, эти файлы могут теоретически (и будут на практике) быть довольно большими - возврат дельты в виде списка, например, означает чтение полных данных в память, что не умный поступок.

Что касается только возврата разницы, то в использовании генератора есть еще одно преимущество — просто перебирайте дельту и сохраняйте те строки, которые вас интересуют.

Если вы прочтете документацию difflib для дельт в стиле Differ, вы увидите абзац, который гласит:

Each line of a Differ delta begins with a two-letter code:
Code    Meaning
'- '    line unique to sequence 1
'+ '    line unique to sequence 2
'  '    line common to both sequences
'? '    line not present in either input sequence

Итак, если вам нужны только различия, вы можете легко отфильтровать их, используя str.startswith.

Вы также можете использовать difflib.context_diff для получения компактной дельты, которая показывает только изменения.

person Jim Brissom    schedule 20.01.2011

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

Преимущество возврата генератора состоит в том, что не нужно хранить все сразу в памяти. Это может быть полезно для сравнения очень больших файлов.

person Karl Bielefeldt    schedule 20.01.2011
comment
Спасибо, я все еще в шоке, что context_diff больше, чем file2. Похоже, что diff сказал бы что-то вроде добавления «print j= + j» в позиции 235 в любом внутреннем синтаксисе, который он хотел использовать. И можете ли вы сделать .restore из context_diff? - person NealWalters; 20.01.2011