Diff

В обчислювальній техніці diff - утиліта порівняння файлів, що виводить різницю між двома файлами. Ця програма виводить порядково зміни, зроблені в файлі (для текстових файлів). Сучасні реалізації підтримують також двійкові файли. Висновок утиліти називається «diff», або, що більш поширене, патч, так як він може бути застосований до програми patch. Висновок схожих утиліт порівняння файлів також часто називається «diff». Історія

Утиліта diff була розроблена на початку 1970-х років для операційної системи Unix, яка була плодом роботи AT & T Bell Labs, у Мюррей Хілл (Нью-Джерсі). Фінальна версія, розповсюджувана з п'ятим версією 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 залишаються зовні незмінними з 1975 року. Модифікації включають в себе поліпшення основного алгоритму, додавання нових ключів команди, нові формати виводу. Базовий алгоритм викладено в книгах An O (ND) Difference Algorithm and its Variations Юджина В. Майерса, [2] і в A File Comparison Program Вебба Міллера і Майерса. [3] Алгоритм був незалежно відкритий і описаний в Algorithms for Approximate String Matching Е. Укконеном [4] Перші версії програми diff були розроблені для порівняння рядків текстових файлів, що використовує символ нового рядка як роздільник рядків. У 1980-х, підтримка двійкових файлів привела до змін в схемі роботи і реалізації програми.