Diff

diff — утыліта для параўнання файлаў, якая выводзіць розніцу паміж двума файламі. Гэтая праграма парадкова выводзіць адрозненні паміж файламі (для тэкставых файлаў). Сучасныя рэалізацыі могуць параўноўваць таксама бінарныя файлы. Вынік працы падобных утыліт параўнання файлаў часта называецца «diff», таксама распаўсюджана назва «patch», таму што выніковы файл розніцы можна выкарыстаць з праграмай patch.

Пры наяўнасці розных версій аднаго файла ўтыліта diff дазваляе адсачыць змены ў навейшай версіі адносна папярэдняй.

Утыліта diff была распрацавана ў пачатку 1970-х гадоў для аперацыйнай сістэмы Unix, якая была плёнам працы AT & T Bell Labs, у Мюрэй Хіл (Нью-Джэрсі). Канчатковая версія, якая распаўсюджваецца з 5й Версіяй Unix у 1974, цалкам была напісана Дугласам Макілроем.

Праца diff заснавана на знаходжанні найбольшай агульнай падпаслядоўнасці (англ.: longest common subsequence, праблема LCS). Напрыклад, у вас ёсць дзве паслядоўнасці элементаў:

       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   k   q r x y 
       +   — +   +   — + + +

diff выклікаецца з каманднага радка з імёнамі двух файлаў у якасці аргументаў: diff original new . Вынік каманды ўяўляе сабой змены, якія трэба зрабіць у зыходным файле original, каб атрымаць новы файл new. Калі original і new — дырэкторыі, то diff аўтаматычна будзе прыменена да кожнага файла, які існуе ў абедзвюх дырэкторыях. Ва ўсіх прыкладах ў гэтым артыкуле выкарыстоўваюцца наступныя два файлы, original і new:

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 anything.

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 стварае наступны нармальны diff-вынік:

0a1,6
> This is an important
> notice! It should
> therefore be located at
> the beginning of this
> document!
>
8,14c14
< compress the size of the
< changes.
<
< This paragraph contains
< text that is outdated.
< It will be deleted in the
< near future.
---
> compress anything.
17c17
< check this dokument. On
---
> check this document. On
24a25,28
>
> This paragraph contains
> important new additions
> to this document.

У гэтым традыцыйным фармаце вываду a азначае дабаўлена (ад англ.: add),d — выдалена (ад англ.: delete),c — зменена (ад англ.: change). Перад літарамі a, d або c стаяць нумары радкоў зыходнага файла, пасля іх — нумары радкоў канчатковага файла. Перад кожным радком, які быў дабаўлены, выдалены або зменены, стаяць вуглавыя дужкі. Перадвызначана, агульныя для зыходнага і канчатковага файлаў нумары радкоў не паказваюцца. Радкі, якія былі перамешчаны, паказваюцца як дабаўленыя на сваім новым месцы і выдаленыя са свайго папярэдняга размяшчэння.^[1]

Большасць рэалізацый diff застаюцца вонкава нязменнымі з 1975 года. Мадыфікацыі ўключаюць у сябе паляпшэнні асноўнага алгарытму, даданне новых ключоў каманды, новыя фарматы вываду. Базавы алгарытм выкладзен у кнігах An O (ND) Difference Algorithm and its Variations Юджына В. Майерса,^[2] і ў A File Comparison Program Вэбба Міллера ды Майерса.^[3] Алгарытм быў незалежна адкрыт і апісан ў Algorithms for Approximate String Matching Е. Укканенам^[4] Першыя версіі праграмы diff былі распрацаваны для параўнання радкоў тэкставых файлаў, у якіх у якасці раздзяляльніка радкоў выкарыстоўваецца сімвал новага радка. У 1980-х, падтрымка бінарных файлаў прывяла да змен у алгарытме работы і рэалізацыі праграмы.

У BSD версіі 2.8 (выпушчанай у ліпені 1981 года) з’явіўся кантэкстны фармат (-c ).

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

Вынік каманды 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
***************
*** 5,20 ****
  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.
--- 11,20 ----
  be shown if it doesn’t
  change.  Otherwise, that
  would not be helping to
! compress anything.

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

• cmp
• comm
• diff3
• Kompare
• kdiff3
• Meld
• Microsoft File Compare
• rsync
• tkdiff
• wdiff — абгортка для diff для параўнання файлаў па словах
• WinMerge
• Дэльта-кадаванне
• Найбольшая агульная падпаслядоўнасць
• Адлегласць Левенштэйна

• Пакет GNU diffutils уключае ў сябе diff. Распаўсюджваецца пад GNU General Public License.
• diffutils для Win32 — частка GnuWin32
• Online-інтэрфейс да diff Архівавана 26 студзеня 2007. (англ.)
• java-diff — Бібліятэка diff, рэалізаваная на Java
• Алгарытм diff на C# — Зыходны код алгарытма diff і яго варыянтаў на C#