Коли git показує зміни в файлі, або редактор порівнює дві версії тексту, під капотом працює diff-алгоритм — спосіб знайти мінімальний набір змін (додавань і видалень рядків), який перетворює один текст на інший.
Найдовша спільна підпослідовність
Класичний підхід до diff ґрунтується на пошуку найдовшої спільної підпослідовності (LCS) рядків між двома версіями тексту. Рядки, що входять у цю підпослідовність, вважаються незмінними; усе інше позначається як видалене зі старої версії або додане в нову. Такий підхід дає мінімальний, а не будь-який можливий набір змін.
Як читати результат
Типовий вивід diff позначає видалені рядки одним маркером (часто - і червоним кольором), а додані — іншим (+ і зеленим). Рядок, що «змінився», технічно показується як видалення старої версії плюс додавання нової — diff не знає про редагування рядка як окрему операцію.
Чому порівняння рядок за рядком не завжди інтуїтивне
Якщо посеред тексту вставити один новий рядок, порівняння рядок за рядком може показати, що «змінились» усі наступні рядки — бо алгоритм не завжди вгадує, що це саме вставка, а не масова заміна. Хороші diff-інструменти намагаються мінімізувати такі хибні спрацьовування, але це не завжди ідеально.
Навіщо це потрібно
- Перевірити, що саме змінилося між двома версіями конфігурації чи документа.
- Переглянути code review, розуміючи логіку алгоритму пошуку відмінностей.
- Порівняти вивід скрипта до і після рефакторингу, щоб переконатись у відсутності регресій.
Diff на рівні рядків проти рівня символів
Порівняння рядок за рядком підходить для коду й конфігів, але для прози чи довгого речення, у якому змінилось одне слово, воно позначить увесь рядок як видалений і доданий заново. Diff на рівні слів чи символів усередині рядка точніше показує саме те слово, що змінилося, — ціна за це вища обчислювальна складність на великих текстах.