Введение

Стандартная утилита UNIX для сравнения файлов

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

Алгоритм

Операция основана на решении задачи поиска самой длинной общей подпоследовательности. Однако некоторые инструменты сравнения выделяют перемещенные строки.

Реализация и связанные с ней программы

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

Форматировщики и фронт-эндесы

Постпроцессоры sdiff и diffmk отображают списки различий рядом и, соответственно, отмечают изменения в печатных документах. Оба были разработаны в других подразделениях Bell Labs в 1981 году или ранее. Diff3 сравнивает один файл с двумя другими, объединяя два набора различий. Изначально он был разработан Полом Дженсеном для согласования изменений, внесенных двумя людьми при редактировании общего исходного файла. Он также используется системами контроля версий, например RCS, для слияния изменений. Emacs предоставляет Ediff для отображения изменений, которые внесет патч, в пользовательском интерфейсе, сочетающем интерактивное редактирование и возможности слияния для файлов патчей. Vim предлагает vimdiff для сравнения от двух до восьми файлов, с выделением различий цветом. Хотя исторически vim вызывал программу diff, современная версия использует форк библиотеки xdiff от Git (LibXDiff), что обеспечивает повышенную скорость и функциональность. GNU Wdiff – это надстройка над diff, которая показывает измененные слова или фразы в текстовом документе, даже при переносе строк или разной ширине столбцов. colordiff – это Perl-оболочка для 'diff', которая выдает тот же результат, но с цветовым выделением добавленных и удаленных фрагментов. diff so fancy и diff highlight – более новые аналогичные инструменты. "delta" – это переписанная на Rust программа, которая одновременно выделяет изменения и базовый код. Patchutils содержит инструменты для объединения, переупорядочивания, сравнения и исправления контекстных и унифицированных диффов.