разница

Эта статья о служебной программе. Общие сведения о сравнении файлов см. в разделе Сравнение файлов . О различиях в Википедии см. Help:Diff . Чтобы узнать о других значениях, см. DIFF .

разница

Оригинальный автор(ы)	Дуглас Макилрой ( AT&T Bell Laboratories )
Разработчик(и)	Различные с открытым исходным кодом и коммерческие разработчики разработчики
Первоначальный выпуск	июнь 1974 г ( 1974-06 )
Написано в	С
Операционная система	Unix , Unix-подобные , V , Plan 9 , Inferno
Платформа	Кросс-платформенный
Тип	Команда
Лицензия	План 9: МОЯ лицензия

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

Обычно diff используется для отображения изменений между двумя версиями одного и того же файла. Современные реализации также поддерживают двоичные файлы . Вывод называется «diff» или « patch» , поскольку результат можно применить с помощью Unix . программы пластырь . Вывод подобных утилит сравнения файлов также называется «diff»; Подобно использованию слова « grep » для описания процесса поиска, слово «diff» стало общим термином для расчета разницы данных и их результатов. Стандарт POSIX определяет поведение утилит «diff» и «patch», а также их форматы файлов.

История

diff был разработан в начале 1970-х годов для операционной системы Unix, которая возникла в Bell Labs в Мюррей-Хилл, штат Нью-Джерси. Это была часть пятой редакции Unix, выпущенной в 1974 году. и был написан Дугласом Макилроем и Джеймсом Хантом . Это исследование было опубликовано в статье 1976 года, написанной в соавторстве с Джеймсом Хантом, который разработал первоначальный прототип разница . Алгоритм, описанный в этой статье, стал известен как алгоритм Ханта – Шиманского .

Работе Макилроя предшествовала и оказала на нее влияние Джонсона программа сравнения GECOS Стива и Майка Леска . программа доказательства . Доказательство также зародилось в Unix и, как и diff , производил построчные изменения и даже использовал угловые скобки («>» и «<») для представления вставки и удаления строк в выводе программы. Однако эвристика , использованная в этих ранних приложениях, была сочтена ненадежной. Потенциальная полезность инструмента сравнения побудила Макилроя исследовать и разработать более надежный инструмент, который можно было бы использовать в различных задачах, но который хорошо справлялся бы с ограничениями по обработке и размеру аппаратного обеспечения PDP-11 . Его подход к проблеме стал результатом сотрудничества с людьми из Bell Labs, включая Альфреда Ахо , Эллиота Пинсона, Джеффри Уллмана и Гарольда С. Стоуна.

В контексте Unix использование ed line предоставлен редактор diff с естественной способностью создавать пригодные для использования на компьютере «сценарии редактирования». Эти сценарии редактирования, сохраненные в файле, могут быть восстановлены вместе с исходным файлом с помощью внесен полностью в измененный файл. Это значительно уменьшило объем вторичной памяти , необходимой для поддержки нескольких версий файла. Макилрой подумывал о написании постпроцессора для diff , где можно было спроектировать и реализовать множество выходных форматов, но он нашел более экономичным и простым использование diff отвечает за генерацию синтаксиса и входных данных в обратном порядке, принимаемых команда ред .

В 1984 году Ларри Уолл создал отдельную утилиту patch . размещение исходного кода в группах новостей mod.sources и net.sources . Эта программа изменяет файлы, используя вывод diff и имеет возможность сопоставлять контекст.

Руководство по переносимости X/Open, выпуск 2, 1987 г., включает в себя различия. Контекстный режим был добавлен в POSIX.1-2001 (выпуск 6). Унифицированный режим был добавлен в POSIX.1-2008 (выпуск 7).

В В первые годы существования diff обычное использование включало сравнение изменений в исходном коде программного обеспечения и разметке технических документов, проверку результатов отладки программ, сравнение списков файловых систем и анализ ассемблерного кода компьютера. Результат, предназначенный для Целью ed было обеспечение сжатия последовательности изменений, вносимых в файл. Система контроля исходного кода (SCCS) и ее возможность архивировать версии появились в конце 1970-х годов как следствие хранения сценариев редактирования из разница .

Алгоритм

Операция diff основан на решении проблемы самой длинной общей подпоследовательности .

В этой задаче даны две последовательности пунктов:

a b c d f g h j q z

a b c d e f g i j k r x y z

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

a b c d  f  g  j  z

Из самой длинной общей подпоследовательности можно получить лишь небольшой шаг diff -подобный вывод: если элемент отсутствует в подпоследовательности, но присутствует в первой исходной последовательности, он должен быть удален (на что указывают знаки «-» ниже). Если он отсутствует в подпоследовательности, но присутствует во второй исходной последовательности, он должен быть вставлен (на что указывают знаки «+»).

e   h i   q   k r x y
+   - +   -   + + + +

Использование

The diff Команда вызывается из командной строки, передавая ей имена двух файлов: diff original new. Вывод команды представляет изменения, необходимые для преобразования исходного файла в новый файл.

Если original и new — каталоги, то diff будет запущен для каждого файла, существующего в обоих каталогах. Вариант, -r, рекурсивно спустится по всем совпадающим подкаталогам для сравнения файлов между каталогами.

В любом из примеров в статье используются следующие два файла, исходный и новый :

оригинал :

This part of the
document has stayed the
same from version to
version.  It shouldn't
be shown if it doesn't
change.  Otherwise, that
would not be helping to
compress the size of the
changes.

This paragraph contains
text that is outdated.
It will be deleted in the
near future.

It is important to spell
check this dokument. On
the other hand, a
misspelled word isn't
the end of the world.
Nothing in the rest of
this paragraph needs to
be changed. Things can
be added after it.

новый :

This is an important
notice! It should
therefore be located at
the beginning of this
document!

This part of the
document has stayed the
same from version to
version.  It shouldn't
be shown if it doesn't
change.  Otherwise, that
would not be helping to
compress the size of the
changes.

It is important to spell
check this document. On
the other hand, a
misspelled word isn't
the end of the world.
Nothing in the rest of
this paragraph needs to
be changed. Things can
be added after it.

This paragraph contains
important new additions
to this document.

Команда diff original new производит следующий нормальный вывод различий :

0a1,6
> This is an important
> notice! It should
> therefore be located at
> the beginning of this
> document!
>
11,15d16
< This paragraph contains
< text that is outdated.
< It will be deleted in the
< near future.
<
17c18
< check this dokument. On
---
> check this document. On
24a26,29
>
> This paragraph contains
> important new additions
> to this document.

Примечание. Здесь выходные данные различий показаны цветами, чтобы их было легче читать. Утилита diff не выдает цветной результат; его вывод представляет собой обычный текст . Однако многие инструменты могут отображать выходные данные цветами, используя подсветку синтаксиса .

В этом традиционном формате вывода а означает добавленный , д для удаленных и с для измененного . Номера строк исходного файла появляются перед а / д / с и элементы нового файла появятся позже. Знаки «меньше» и «больше» (в начале добавленных, удаленных или измененных строк) указывают, в каком файле появляются строки. Дополнительные строки добавляются в исходный файл и появляются в новом файле. Строки удаления удаляются из исходного файла и отсутствуют в новом файле.

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

Варианты вывода

Редактировать сценарий

Сценарий ed по-прежнему может быть создан современными версиями diff с помощью команды -e вариант. Результирующий сценарий редактирования для этого примера выглядит следующим образом:

24a

This paragraph contains
important new additions
to this document.
.
17c
check this document. On
.
11,15d
0a
This is an important
notice! It should
therefore be located at
the beginning of this
document!

.

Чтобы преобразовать содержимое исходного файла в содержимое нового файла, используя ed , мы должны добавить две строки в этот файл различий, одна строка содержит w (запись), и один, содержащий q (выйти) команда (например, с помощью printf "w\nq\n" >> mydiff). Здесь мы дали файлу различий имя mydiff , и преобразование произойдет при запуске. ed -s original < mydiff.

Формат контекста

В дистрибутиве Unix в Беркли обязательно добавлялся формат контекста ( -c) и возможность рекурсивного обращения к структурам каталогов файловой системы ( -r), добавив эти функции в версию 2.8 BSD, выпущенную в июле 1981 года. Контекстный формат diff, представленный в Беркли, помог распространять исправления для исходного кода, которые могли быть изменены минимально.

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

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

А " !" представляет собой изменение между строками, которые соответствуют в двух файлах, тогда как " +" представляет собой добавление строки, а " -" удаление строки. Пробел представляет собой неизмененную строку. В начале исправления указывается информация о файле, включая полный путь и отметку времени, разделенную символом табуляции. В начале каждого фрагмента указаны номера строк. которые применяются к соответствующим изменениям в файлах. Диапазон номеров, отображаемый между наборами из трех звездочек, применяется к исходному файлу, а наборы из трех тире применяются к новому файлу. Диапазоны фрагментов указывают начальные и конечные номера строк в соответствующем файле. .

Команда diff -c original new производит следующий вывод:

*** /path/to/original	timestamp
--- /path/to/new	timestamp
***************
*** 1,3 ****
--- 1,9 ----
+ This is an important
+ notice! It should
+ therefore be located at
+ the beginning of this
+ document!
+
  This part of the
  document has stayed the
  same from version to
***************
*** 8,20 ****
  compress the size of the
  changes.

- This paragraph contains
- text that is outdated.
- It will be deleted in the
- near future.

  It is important to spell
! check this dokument. On
  the other hand, a
  misspelled word isn't
  the end of the world.
--- 14,21 ----
  compress the size of the
  changes.

  It is important to spell
! check this document. On
  the other hand, a
  misspelled word isn't
  the end of the world.
***************
*** 22,24 ****
--- 23,29 ----
  this paragraph needs to
  be changed. Things can
  be added after it.
+
+ This paragraph contains
+ important new additions
+ to this document.

Примечание. Здесь выходные данные различий показаны цветами, чтобы их было легче читать. Утилита diff не выдает цветной результат; его вывод представляет собой обычный текст . Однако многие инструменты могут отображать выходные данные цветами, используя подсветку синтаксиса .

Единый формат

Единый формат (или unidiff ) наследует технические улучшения, внесенные в формат контекста, но создает меньшую разницу со старым и новым текстом, представленным непосредственно рядом. Унифицированный формат обычно вызывается с помощью " -u . Многие проекты специально требуют, чтобы Параметр командной строки . Этот вывод часто используется в качестве входных данных для программы исправления «diff-файлы» отправлялись в унифицированном формате, что делает унифицированный формат различий наиболее распространенным форматом для обмена между разработчиками программного обеспечения.

Унифицированные контекстные различия были первоначально разработаны Уэйном Дэвисоном в августе 1990 года (в формате unidiff , который появился в 14 томе comp.sources.misc). Ричард Столлман добавил унифицированную поддержку различий в утилиту diff проекта GNU Project месяц спустя, и эта функция дебютировала в GNU diff 1.15, выпущенном в январе 1991 года. С тех пор GNU diff обобщил формат контекста, чтобы разрешить произвольное форматирование различий.

Формат начинается с того же двухстрочного заголовка , что и формат контекста, за исключением того, что исходному файлу предшествует " --- " и новому файлу предшествует " +++ ". После этого идут один или несколько фрагментов изменений , которые содержат различия строк в файле. Неизмененным контекстным строкам предшествует символ пробела, строкам добавления предшествует знак плюс , а строкам удаления - знак минус .

Чанк начинается с информации о диапазоне , за которым сразу же следует добавление строк, удаление строк и любое количество контекстных строк. Информация о диапазоне окружена двойным знаком at и объединяет в одну строку то, что отображается в двух строках в формате контекста ( выше ). Формат строки информации о диапазоне следующий:

@@ -l,s +l,s @@ optional section heading

Информация о диапазоне фрагментов содержит два диапазона фрагментов. Диапазону фрагмента исходного файла предшествует символ минус, а диапазону нового файла — символ плюс. Каждый диапазон фрагментов имеет формат l,s , где l — номер начальной строки, а s — количество строк, к которым применяется фрагмент изменения для каждого соответствующего файла. Во многих версиях GNU diff в каждом диапазоне можно опускать запятую и завершающее значение s , и в этом случае s по умолчанию равно 1. Обратите внимание, что единственное действительно интересное значение — это номер строки l первого диапазона; все остальные значения могут быть вычислены из разницы.

Диапазон фрагментов для оригинала должен представлять собой сумму всех контекстных и удаленных (включая измененные) фрагментов. Диапазон фрагментов для нового файла должен представлять собой сумму всех контекстных и дополнительных (в том числе измененных) строк фрагментов. Если информация о размере фрагмента не соответствует количеству строк в фрагменте, то разницу можно считать недействительной и отклонить.

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

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

-check this dokument. On
+check this document. On

Команда diff -u original new производит следующий вывод:

--- /path/to/original	timestamp
+++ /path/to/new	timestamp
@@ -1,3 +1,9 @@
+This is an important
+notice! It should
+therefore be located at
+the beginning of this
+document!
+
 This part of the
 document has stayed the
 same from version to
@@ -8,13 +14,8 @@
 compress the size of the
 changes.

-This paragraph contains
-text that is outdated.
-It will be deleted in the
-near future.
-
 It is important to spell
-check this dokument. On
+check this document. On
 the other hand, a
 misspelled word isn't
 the end of the world.
@@ -22,3 +23,7 @@
 this paragraph needs to
 be changed. Things can
 be added after it.
+
+This paragraph contains
+important new additions
+to this document.

Примечание. Здесь выходные данные различий показаны цветами, чтобы их было легче читать. Утилита diff не выдает цветной результат; его вывод представляет собой обычный текст . Однако многие инструменты могут отображать выходные данные цветами, используя подсветку синтаксиса .

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

Расширения

Существуют некоторые модификации и расширения форматов различий, которые используются и понимаются определенными программами и в определенных контекстах. Например, некоторые системы контроля версий , такие как Subversion, указывают номер версии, «рабочую копию» или любой другой комментарий вместо или в дополнение к метке времени в разделе заголовка различий.

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

Index: path/to/file.cpp

Особый случай файлов, которые не заканчиваются новой строкой, не обрабатывается. Ни утилита unidiff, ни стандарт POSIX diff не определяют способ обработки файлов этого типа. (Действительно, такие файлы не являются «текстовыми» файлами по строгим определениям POSIX. ) GNU diff и git выдают «\ Нет новой строки в конце файла» (или переведенную версию) в качестве диагностики, но такое поведение непереносимо. Патч GNU, похоже, не обрабатывает этот случай, а git-apply справляется.

Программа исправлений не обязательно распознает выходные данные различий, специфичные для конкретной реализации. Однако известно, что патч GNU распознает патчи git и действует немного по-другому.

Реализации и сопутствующие программы

Изменения, произошедшие с 1975 года, включают улучшения основного алгоритма, добавление полезных функций к команде и разработку новых форматов вывода. Базовый алгоритм описан в статьях «Разностный алгоритм O(ND) и его вариации». Юджина Майерса и в «Программе сравнения файлов» Уэбба Миллера и Майерса. Алгоритм был независимо открыт и описан в книге «Алгоритмы приблизительного сопоставления строк » ​​Эско Укконена . Первые версии программы diff были разработаны для сравнения строк текстовых файлов, ожидая, что символ новой строки будет разделять строки. К 1980-м годам поддержка двоичных файлов привела к изменению дизайна и реализации приложений.

GNU diff и diff3 включены в пакет diffutils вместе с другими утилитами, связанными с различиями и исправлениями .

Форматеры и интерфейсы

Постпроцессоры sdiff и diffmk отображают параллельные списки различий и применяют метки изменений к печатным документам соответственно. Оба были разработаны где-то в Bell Labs в 1981 году или ранее.

Diff3 сравнивает один файл с двумя другими файлами путем согласования двух различий. Первоначально он был задуман Полом Дженсеном для согласования изменений, внесенных двумя людьми, редактирующими общий источник. Он также используется системами контроля версий, например RCS , для слияния .

В Emacs есть Ediff для отображения изменений, которые патч внесет в пользовательский интерфейс, который сочетает в себе возможности интерактивного редактирования и объединения файлов патчей.

Vim предоставляет vimdiff для сравнения от двух до восьми файлов, причем различия выделяются цветом. Исторически вызывая программу diff, современный vim использует git fork кода библиотеки xdiff (LibXDiff), обеспечивая повышенную скорость и функциональность.

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

colordiff — это Perl-оболочка для diff, которая выдает тот же результат, но с раскраской добавленных и удаленных битов. diff-so-fancy и diff-highlight — более новые аналоги. «дельта» — это переписанная версия Rust, которая одновременно выделяет изменения и основной код.

Patchutils содержит инструменты, которые объединяют, переупорядочивают, сравнивают и исправляют контекстные и унифицированные различия.

Алгоритмические производные

Утилиты, сравнивающие исходные файлы по их синтаксической структуре, были созданы в основном как инструменты исследования некоторых языков программирования; некоторые доступны в качестве коммерческих инструментов. Кроме того, к бесплатным инструментам, выполняющим различия с учетом синтаксиса, относятся:

• C++: зограф, на основе AST.
• HTML: Дейзидифф, html-разница.
• XML: xmldiffpatch от Microsoft и xmldiffmerge от IBM.
• JavaScript : astii (на основе AST).
• Многоязычность: Pretty Diff (форматирование кода, а затем сравнение)

spiff — это вариант diff , который игнорирует различия в вычислениях с плавающей запятой с ошибками округления и пробелами , которые обычно не имеют отношения к сравнению исходного кода. Bellcore написала оригинальную версию. Порт HPUX — это самая последняя общедоступная версия. spiff не поддерживает двоичные файлы. spiff выводит на стандартный вывод в стандартном формате diff и принимает входные данные на C , Bourne Shell , Fortran , Modula-2 и Lisp языках программирования .

LibXDiff — это библиотека LGPL , которая обеспечивает интерфейс для многих алгоритмов 1998 года. Первоначально был реализован улучшенный алгоритм Майерса с отпечатком Рабина (по состоянию на финальную версию 2008 года), но форк git и libgit2 с тех пор расширил репозиторий множеством своих собственных. Один алгоритм, называемый «гистограммой», обычно считается намного лучшим, чем исходный алгоритм Майерса, как по скорости, так и по качеству. Это современная версия LibXDiff, используемая Vim.

См. также

• Сравнение инструментов сравнения файлов
• Дельта-кодирование
• Разностный оператор
• Изменить расстояние
  • Расстояние Левенштейна
• История управления конфигурацией программного обеспечения
• Проблема самой длинной общей подпоследовательности
• Сравнение файлов Microsoft
• Microsoft Виндифф
• Контроль версий
• Управление конфигурацией программного обеспечения

Другие бесплатные инструменты сравнения файлов

• cmp
• связь
• tkdiff
• WinMerge (Microsoft Windows)
• сливаться
• Довольно разница

Дальнейшее чтение

• Пол Хекель (апрель 1978 г.). «Методика выделения различий между файлами» . Коммуникации АКМ . 21 (4): 264–268. дои : 10.1145/359460.359467 . S2CID   207683976 . Метод изоляции различий между файлами
• Общая реализация алгоритма Майерса SES/LCS с уточнением линейного пространства Хиршберга (исходный код C)

Внешние ссылки

• diff: сравнить два файла – Справочник по оболочке и утилитам, Единая спецификация UNIX , Версия 4 от The Open Group
• diff(1) – Plan 9 , том 1 Руководство программиста
• diff(1) – Inferno по общим командам Руководство
• Сравнение файлов в Curlie
• Реализация JavaScript