Сравнение текста и патчи: принципы Diff и инструменты

Diff: повсеместное вычисление различий

От управления версиями Git до проверки кода, от изменений конфигурации до синхронизации данных — Diff — это базовая операция в разработке программного обеспечения.

Сценарий	Тип Diff	Инструмент
Изменения кода	Построчный Diff	Git
Сравнение конфигураций	Diff по ключ-значение	Онлайн-инструмент сравнения
Данные JSON	Структурированный Diff	json-diff
Юридические документы	Семантический Diff	Специализированный инструмент
Проверка переводов	Посимвольный Diff	Онлайн-сравнение

I. Принципы алгоритма Myers Diff

Основная идея

Алгоритм Myers ищет кратчайший скрипт редактирования (SES), который преобразует исходный текст в целевой — минимальное количество операций вставки/удаления.

Исходный: ABCABBA
Целевой: CBABAC

Скрипт редактирования:
- A    (удалить A)
  B    (сохранить B)
- C    (удалить C)
  C    (сохранить C → вставить C раньше)
  A    (сохранить A)
  B    (сохранить B)
- B    (удалить B)
  A    (сохранить A)
+ C    (вставить C)

Схема алгоритма

      0   1   2   3   4   5   6   7
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
0 │ → │ ↘ │   │   │   │   │   │   │  A
  ├───┼───┼───┼───┼───┼───┼───┼───┤
1 │ ↓ │   │ ↘ │   │ → │ ↘ │   │   │  B
  ├───┼───┼───┼───┼───┼───┼───┼───┤
2 │   │ ↓ │   │ ↘ │ ↓ │   │ ↘ │   │  C
  ├───┼───┼───┼───┼───┼───┼───┼───┤
3 │   │   │ ↓ │   │   │ ↓ │   │ ↘ │  A
  ├───┼───┼───┼───┼───┼───┼───┼───┤
4 │   │   │   │ ↓ │ ↘ │   │ ↓ │   │  B
  ├───┼───┼───┼───┼───┼───┼───┼───┤
5 │   │   │   │   │ ↓ │   │   │ ↓ │  B
  ├───┼───┼───┼───┼───┼───┼───┼───┤
6 │   │   │   │   │   │ ↓ │ ↘ │   │  A
  └───┴───┴───┴───┴───┴───┴───┴───┘
    C   B   A   B   A   C   B   A

→ = вправо (удалить)  ↓ = вниз (вставить)  ↘ = по диагонали (сохранить)

Временная сложность

Случай	Сложность	Описание
Оптимальный	O(ND)	N=длина текста, D=количество различий
Худший	O((N+M)D)	Полностью разные тексты
Типичный	O(N+D²)	Небольшое количество различий

II. Использование инструмента сравнения текстов Tools Ku

Шаги работы

Откройте Инструмент сравнения текстов
Вставьте исходный текст слева
Вставьте изменённый текст справа
Просмотрите результаты различий:
- Красный: удалённые строки
- Зелёный: добавленные строки
- Жёлтый: изменённые строки
Поддерживает посимвольную подсветку различий, точно до каждого изменения символа

Режимы сравнения

Режим	Гранулярность	Случай использования
Построчный	Сравнение по строкам	Изменения кода
Пословный	Сравнение по словам	Редактирование документов
Посимвольный	Сравнение по символам	Точная корректура

III. Специальные техники JSON Diff

Использование инструмента JSON Diff

Откройте Инструмент JSON Diff
Вставьте два набора данных JSON
Просмотрите структурированные различия:
- Добавленные/удалённые/изменённые ключи
- Изменения значений (включая изменения типов)
- Вложенные пути

JSON Diff vs текстовый Diff

// Исходный
{ "name": "张三", "age": 25, "tags": ["a", "b"] }

// Изменённый
{ "name": "张三", "age": 26, "tags": ["a", "c"], "email": "z@test.com" }

Метод сравнения	Результат
Текстовый Diff	Показывает различия по строкам, трудно понять
JSON Diff	`age: 25→26`, `tags[1]: "b"→"c"`, `+email: "z@test.com"`

IV. Унифицированный формат Diff

Спецификация формата

--- a/config.json
+++ b/config.json
@@ -1,5 +1,6 @@
 {
   "name": "my-project",
-  "version": "1.0.0",
+  "version": "2.0.0",
   "description": "A tool",
-  "private": true
+  "private": true,
+  "license": "MIT"
 }

Символ	Значение
`---`	Исходный файл
`+++`	Изменённый файл
`@@ -a,b +c,d @@`	Позиция различия (исходный со строки a, b строк; изменённый со строки c, d строк)
`-`	Удалённая строка
`+`	Добавленная строка
(пробел)	Контекстная строка

V. Генерация и применение патчей

Генерация патча

import * as Diff from 'diff';

const oldText = 'Hello World\nGoodbye World';
const newText = 'Hello World\nGoodbye Cruel World';

// Генерация патча
const patch = Diff.createPatch('file.txt', oldText, newText, 'old', 'new');
console.log(patch);

Вывод:

--- old/file.txt
+++ new/file.txt
@@ -1,2 +1,2 @@
 Hello World
-Goodbye World
+Goodbye Cruel World

Применение патча

// Прямое применение
const result = Diff.applyPatch(oldText, patch);

// Обратное применение (откат)
const reversed = Diff.applyPatch(newText, Diff.reversePatch(patch));

Трёхстороннее слияние

const base = 'Исходный текст';
const branchA = 'Изменение A';
const branchB = 'Изменение B';

const merged = Diff.mergeDiff3(base, branchA, branchB);
// Автоматическое слияние, конфликты помечаются <<<<<<< / ======= / >>>>>>>

VI. Практические сценарии применения

Обнаружение изменений в конфигурационных файлах

const oldConfig = JSON.parse(fs.readFileSync('config.old.json', 'utf-8'));
const newConfig = JSON.parse(fs.readFileSync('config.new.json', 'utf-8'));

const diff = Diff.diffJson(oldConfig, newConfig);
diff.forEach(part => {
  if (part.added) console.log('Добавлено:', JSON.stringify(part.value, null, 2));
  if (part.removed) console.log('Удалено:', JSON.stringify(part.value, null, 2));
});

Проверка файлов переводов

// Сравнение согласованности ключей китайского и английского переводов
const zhKeys = Object.keys(flatten(zhTranslation));
const enKeys = Object.keys(flatten(enTranslation));

const missingInEn = zhKeys.filter(k => !enKeys.includes(k));
const missingInZh = enKeys.filter(k => !zhKeys.includes(k));

Регрессионное тестирование ответов API

const expected = await fs.readFile('fixtures/expected.json', 'utf-8');
const actual = await fetch('/api/data').then(r => r.json());

const diff = Diff.diffJson(JSON.parse(expected), actual);
if (diff.some(d => d.added || d.removed)) {
  throw new Error('Ответ API не соответствует ожидаемому');
}

VII. Оптимизация производительности

Стратегия оптимизации	Эффект	Применимо к
Ограничение строк контекста	Уменьшает размер вывода	Большие файлы
Предварительная обработка хешем	Пропускает одинаковые строки	Очень большие файлы
Поблочное сравнение	Параллельная обработка	Очень длинные тексты
Уровень строк перед уровнем символов	Уменьшает вычислительную нагрузку	Файлы кода

// Ограничение строк контекста
const patch = Diff.createPatch('file', old, new, '', '', { context: 3 });