algorithms · advanced · 6d
Текстовый diff — алгоритм Майерса
Реализуй алгоритм diff Майерса с нуля: вычисли наибольшую общую подпоследовательность, построй edit script обратным ходом, докажи минимальность и применяй патчи так, чтобы любой round-trip был побайтово точным.
Результат
TypeScript-библиотека с экспортами `lcs<T>` и `diff<T>`, где вывод diff — минимальный edit script (операции keep / insert / delete), `apply` восстанавливает цель точно, а основу составляет диагональный поиск Майерса O(ND).
Этапы
0/6 · 0%- 01Наибольшая общая подпоследовательность методом динамического программирования
До Myers выстрой интуицию на классической DP-таблице LCS за O(MN). Для двух последовательностей A и B LCS — наибольшая последовательность элементов, встречающихся по порядку в обеих — не обязательно подряд. Рекуррентность проста: если A[i] == B[j], продолжаем LCS из [i-1][j-1]; иначе берём лучшее из [i-1][j] и [i][j-1]. Таблица кодирует все варианты выравнивания, а обратный ход по ней даёт сами элементы LCS, а не только длину. Правильный обратный ход нетривиален: диагональные ходы (совпадение), левые (пропуск B[j]) и верхние (пропуск A[i]) должны воспроизводить одну и ту же длину LCS из каждой клетки. Реализуй это как обобщённую `lcs<T>(a: T[], b: T[]): T[]` и проверь для строк, чисел и массивов смешанных типов. Таблица O(MN) позже послужит мотивацией для Myers как улучшения, находящего минимальный diff без материализации полной таблицы.
Критерии готовности- `lcs(a, b)` возвращает правильный LCS как минимум для трёх различных тест-кейсов (идентичные массивы, один пустой, чередующееся изменение) — проверено глубоким равенством.
- Ты можешь объяснить, почему обратный ход должен предпочитать диагональные ходы для получения согласованного LCS, когда несколько путей дают одинаковую длину.
Самопроверка
Нарисуй DP-таблицу и обратный ход для `(['a','b','c'], ['a','x','c'])` на доске; senior-ревьюер проверяет, что значения ячеек верны, обратный ход не дублирует выборы, а результат — `['a','c']`, а не `['a']` или `['c']`.
- 02Обратный ход по DP-таблице в минимальный edit script
LCS говорит, что оставить; всё остальное — удаление (в A, но не в LCS) или вставка (в B, но не в LCS). Обходи DP-таблицу одновременно по обеим последовательностям: диагональный шаг порождает `keep`, шаг влево — `insert` из B, шаг вверх — `delete` из A. Получившийся массив объектов `{op, value}` и есть edit script. Два инварианта должны выполняться: (1) чтение операций `keep` + `insert` по порядку даёт B точно — это элементы, оставленные из A, и новые добавляемые; (2) чтение `keep` + `delete` по порядку даёт A точно — это оставляемые и удаляемые элементы. Эти инварианты делают script применимым: ты можешь восстановить любую из сторон из другой, не храня обе. Правильно упорядочь операции: они должны следовать выравниванию A и B, а не переставляться произвольно. Типичная ошибка — выдавать все удаления перед всеми вставками для изменённого региона; корректный script их чередует, как диктует выравнивание.
Критерии готовности- Для входных данных `(['a','b','c'], ['a','x','c'])` `diff` возвращает `[{op:'keep',value:'a'},{op:'delete',value:'b'},{op:'insert',value:'x'},{op:'keep',value:'c'}]` или эквивалентный минимальный script (такое же редакционное расстояние).
- Round-trip: применение keep+insert из script даёт B, keep+delete даёт A — доказано тестом как минимум для трёх различных случаев.
Самопроверка
Покажи, что выдаёт `diff(['a','b','c','d'], ['a','c','d'])`; senior-ревьюер проверяет, что script содержит ровно одно удаление (для 'b'), два keep ('c','d') и что round-trip инвариант выполняется — восстановление B из keep+insert даёт `['a','c','d']`, а не `['a','b','c','d']`.
- 03Замени DP-ядро на диагональный поиск Майерса O(ND)
DP-таблица O(MN) материализует каждое выравнивание; прозрение Майерса в том, что нужно найти только кратчайший edit script (минимальное число вставок и удалений, обозначаемое D), а граф редактирования обладает структурой, которую можно использовать. Диагональ k = x − y в графе редактирования продвигает оба указателя при совпадении элементов (snake), и snakes ты проходишь жадно. Итерируешь D = 0, 1, 2, … до достижения правого нижнего угла; на каждом D исследуешь только достижимые диагонали (k ∈ {−D, −D+2, …, D}) и хранишь только самую дальнюю x-координату на каждой диагонали в массиве V. Внешний цикл выполняется за O(D) проходов, каждый проход затрагивает O(D) диагоналей, а каждое продвижение по диагонали — O(1) амортизированно (snakes проходят O(N) суммарно по всем диагоналям), что даёт O(ND) в целом — O(N + D²), и зачастую намного лучше O(MN) при малом diff. Сохраняй массивы V на каждом D для обратного хода по пути и восстановления edit script. Это алгоритм, который работает в `git diff`, GNU diff и каждом production-инструменте построчного diff.
Критерии готовности- Функция `diff` использует внутренний диагональный поиск Майерса (цикл O(ND) с массивом V), а не DP-таблицу O(MN) — проверяемо инспекцией кода.
- Все предыдущие тесты всё ещё проходят после замены — edit script наблюдаемо эквивалентен (те же операции и round-trip), хотя внутренний алгоритм изменился.
Самопроверка
Пройди эволюцию массива V для `diff(['a','b','c'], ['a','x','c'])` шаг за шагом при D=0, D=1, D=2; senior-ревьюер проверяет, что ты можешь назвать snake-продвижения на каждой диагонали и показать сохранённые значения V до обратного хода.
- 04Докажи минимальность: редакционное расстояние равно |удалений| + |вставок|
Алгоритм diff полезен только если его вывод минимален — кратчайший возможный edit script. Myers гарантирует минимальность по построению (по определению находит наименьший D), но нужно проверить это эмпирически: число non-keep-операций в твоём script должно равняться истинному редакционному расстоянию между A и B. Редакционное расстояние (Левенштейн только с вставками/удалениями, без замен) равно len(A) + len(B) − 2 × len(LCS), потому что каждый элемент, не входящий в LCS, должен быть либо удалён из A, либо вставлен в B. Сравни количество операций твоего diff с этой формулой как минимум на пяти различных парах. Корректная реализация всегда совпадёт. Некорректная будет переучитывать (избыточные операции) или недоучитывать (нарушение round-trip). Этот этап также заставляет чисто обработать вырожденные случаи: идентичные массивы (D=0, все keep), один пустой массив (D=длина другого, все insert или все delete), одноэлементные массивы и очень длинные массивы где D ≪ N.
Критерии готовности- Для каждой тестовой пары `diff(a,b).filter(op=>op.op!=='keep').length === a.length + b.length - 2 * lcs(a,b).length` — проверено автоматическим утверждением, а не только визуально.
- Граничные случаи (идентичные, один пустой, одноэлементный) дают скрипты без накладных расходов: идентичные массивы дают ноль non-keep-операций, пустой A даёт только insert, пустой B — только delete.
Самопроверка
Для `diff(['a','b','c','d','e'], ['b','c','e','f'])` подсчитай non-keep-операции в твоём script и убедись, что результат равен `5 + 4 - 2*lcs.length`; senior-ревьюер проверяет, что формула верна, и что ты можешь назвать LCS без запуска кода.
- 05Применение патча: точность round-trip и обработка ошибок
Edit script полезен ровно настолько, насколько он применим. Реализуй `apply<T>(base: T[], script: EditOp<T>[]): T[]`, восстанавливающую цель потреблением операций keep и insert по порядку (операции delete потребляются, но не эмитируются). Функция apply должна быть строгой: если элемент base на позиции keep или delete не совпадает с ожидаемым значением в операции — бросай исключение, потому что неправильно применённый патч хуже отсутствия патча: он молча портит данные. Проверь прямой round-trip: `apply(a, diff(a, b))` глубоко равно `b`. Затем обратный: `apply(b, invertScript(diff(a, b)))` глубоко равно `a`, где `invertScript` меняет insert и delete местами. Эти два round-trip вместе доказывают, что script не просто синтаксически корректен, но и семантически правилен. Тестируй со строками (посимвольный diff), числами и объектами, сравниваемыми пользовательской функцией равенства, передаваемой параметром — `lcs<T>` и `diff<T>` должны принимать опциональную `eq: (x: T, y: T) => boolean` для непримитивного равенства.
Критерии готовности- `apply(a, diff(a, b))` === b для всех тестовых пар (прямой round-trip), и `apply(b, invertScript(diff(a,b)))` === a для тех же пар (обратный round-trip).
- `apply` бросает понятное исключение, когда элемент base на позиции keep/delete не совпадает со значением операции — проверено тестом, подающим намеренно испорченный base.
Самопроверка
Покажи реализацию `apply` для пути с броском при несовпадении; senior-ревьюер проверяет, что сообщение об ошибке указывает позицию, ожидаемое и фактическое значение, и что `apply` никогда молча не проглатывает конфликт.
- 06Группировка ханков и контекстные строки — вывод в формате unified diff
Сырой edit script — это плоский список операций. Люди (и инструменты патчей) работают с ханками: смежными группами изменённых операций с настраиваемым числом контекстных строк (неизменённых keep) с каждой стороны. Стандартный unified diff использует 3 контекстных строки; patch и git принимают размер контекста как флаг. Сгруппируй edit script в ханки: сканируй последовательности insert/delete, разделённые более чем 2×context операциями keep; каждая такая последовательность вместе со своими контекстными строками становится одним ханком. Заголовок ханка содержит номера строк в оригинале и цели (`@@ -M,N +P,Q @@` в нотации unified diff), вычисляемые подсчётом уже эмитированных операций. Реализуй `toUnifiedDiff(a: string[], b: string[], context = 3): string`, выдающую корректный unified diff, и `fromUnifiedDiff(patch: string): Hunk[]`, парсящую его обратно. Round-trip `fromUnifiedDiff(toUnifiedDiff(a, b)).apply(a)` должен воспроизводить b точно. Это формат, который потребляют `git apply`, `patch(1)` и инструменты code review — ошибка в номерах строк на единицу — это канонический off-by-one, на котором спотыкается каждая реализация diff.
Критерии готовности- `toUnifiedDiff` выдаёт заголовки ханков (`@@ -M,N +P,Q @@`) с правильными номерами строк как минимум для двух тестовых пар с несмежными изменениями — верифицировано относительно вывода `diff -u` на тех же входных данных.
- Round-trip `a → toUnifiedDiff → fromUnifiedDiff → apply → b` проходит для всех тестовых пар, а ханки со смежными изменениями объединяются, а не выдаются как отдельные в пределах контекстного окна.
Самопроверка
Для двух массивов, отличающихся на позициях 2 и 8 (из 15), покажи, что выдаёт `toUnifiedDiff` с context=3: сколько ханков, каковы их заголовки `@@ -M,N +P,Q @@`, и входят ли средние неизменённые строки (позиции 5–7) в контекст или разделяют ханки; senior-ревьюер проверяет граничную арифметику, а не только итоговую строку.
Стартер
- README.md
- src/diff.ts
- test/diff.test.ts
Распакуй, реализуй заглушки, затем гоняй тесты, пока не позеленеют: bun test
Рубрика
| Джуниор | Миддл | Сеньор | |
|---|---|---|---|
| Корректность LCS и edit script | LCS вычислен и имеет правильную длину для типичных тест-кейсов; edit script получен сравнением A и B с LCS, но может содержать лишние операции или неправильный порядок при наличии нескольких выравниваний LCS. | Обратный ход через DP-таблицу (или массивы V Майерса) даёт уникальный упорядоченный edit script, где round-trip инварианты выполняются: keep+insert даёт B, keep+delete даёт A — проверено для идентичных, пустых и чередованно-изменённых случаев. | Реализация обрабатывает все вырожденные случаи (оба пустые, один пустой, идентичные, одноэлементные, очень длинные при D≪N), инвариант минимальности `non-keep ops == len(A)+len(B)-2*len(LCS)` выполняется для каждой тестовой пары, а пользовательская функция равенства принимается параметром, чтобы алгоритм работал для непримитивных типов элементов. |
| Минимальность diff | Выходной script в целом короче наивного, но не доказуемо минимален — некоторые пары дают больше non-keep-операций, чем предсказывает формула редакционного расстояния. | Используется диагональный поиск Майерса O(ND), счётчик D совпадает с фактическим редакционным расстоянием; утверждение минимальности `non-keep ops == len(A)+len(B)-2*len(LCS)` проходит для всех тестовых пар. | Ты можешь объяснить, почему Myers минимален по построению (он находит наименьший D, итерируясь от 0), противопоставить его DP-таблице (которая тоже даёт минимальный script, но за O(MN)), и эмпирически доказать, что более короткого edit script для выбранных тестовых пар не существует. |
| Точность apply / round-trip | Применение script в прямом направлении восстанавливает B для простых случаев, но ломается на граничных (пустые массивы, идентичные, или массивы где D > N/2) — режим ошибки — молчаливо неправильный вывод, а не выброшенное исключение. | Оба round-trip — прямой (`apply(a, diff(a,b)) === b`) и обратный (`apply(b, invertScript(diff(a,b))) === a`) — проходят для всех тестовых пар, а `apply` бросает понятное исключение при несовпадении base, а не молча портит вывод. | Вывод unified diff (`toUnifiedDiff`) даёт корректные заголовки `@@ -M,N +P,Q @@` с точными номерами строк для всех тестовых пар (проверено относительно `diff -u`), а round-trip парсинг→применение работает для патчей с несколькими несмежными ханками и настраиваемыми размерами контекста. |
| Ясность алгоритма и обоснование сложности | Реализация работает, но утверждение о сложности O(ND) не обосновано — ты не можешь объяснить, почему D итераций диагонального поиска достаточно, или что представляет массив V. | Ты можешь пройти массив V шаг за шагом на небольшом примере, объяснить, почему на каждом D достижимы только чётные или нечётные диагонали, и объяснить, почему snake-продвижения амортизированно O(1). | Ты можешь вывести границу O(N + D²) из первых принципов, показать точку пересечения, где O(ND) обгоняет O(MN) (примерно при D < √N), и объяснить линейно-пространственное расширение Хиршберга без реализации — знание формы этой оптимизации и есть планка depth bar. |
Эталонный разбор (спойлер)
Двойственность LCS–редакционное расстояние: длина наибольшей общей подпоследовательности A и B равна `(len(A) + len(B) - editDistance(A,B)) / 2`, где редакционное расстояние считает только вставки и удаления (без замен). Myers использует это, формулируя diff как «найти путь через граф редактирования с наименьшим числом недиагональных шагов», где диагональные шаги бесплатны (это совпадения), а горизонтальные/вертикальные стоят по 1.
Почему Myers хранит только массив V, а не полный путь: x-координаты диагоналей при редакционном расстоянии D полностью определяют, какие ячейки достижимы. Ты сохраняешь весь массив V на каждом D и делаешь обратный ход: начиная с правого нижнего угла, на каждом D находишь, на какой диагонали ты был, и продвигался ли по snake (диагональный ход) или по insert/delete (недиагональный ход). Этот обратный ход использует O(D²) суммарной памяти вместо O(MN).
Off-by-one группировки ханков: заголовок `@@ -M,N +P,Q @@` означает «начиная со строки M в оригинале, ханк охватывает N строк; начиная со строки P в цели он охватывает Q строк». И M, и P индексируются с 1. N и Q считают строки keep + delete (в оригинале) и keep + insert (в цели) внутри ханка. Ошибка на единицу — канонический баг в реализациях diff: генерация `@@ -1,4 +1,4 @@` когда изменение реально на строке 2 означает, что `patch(1)` либо отклонит патч, либо применит его к неправильной строке.
Контракт round-trip и почему `apply` должен быть строгим: если `apply` молча принимает несовпадающий элемент base (операцию keep или delete, чьё значение не совпадает с фактическим элементом base), то `apply(corrupted_base, script)` может дать правдоподобный, но неправильный результат. Строгое сравнение — бросать при несовпадении — превращает необнаруженную порчу данных в явный сбой, что является правильным компромиссом для инструмента патчей. Альтернатива (нечёткое сравнение) — это то, что делает `patch -l`, и это явно ослабленный режим для текста, читаемого человеком, а не для программного патчирования.
Patience diff и почему Myers иногда даёт нечитаемые ханки: Myers находит script с минимальным D, но не ограничивает, какой именно минимальный script он находит. Когда код рефакторится перемещением функций, Myers может связать одинаковые строки из несвязанных контекстов, давая ханк, удаляющий целую функцию и вставляющий немного иную. Patience diff сначала закрепляет выравнивание на уникальных общих строках, поэтому перемещённые функции остаются выровненными, а ханк захватывает только фактическое изменение. Именно поэтому `git diff --patience` часто даёт более удобный для ревьюера вывод при рефакторингах.
Сделай по-сеньорски
- Реализуй уточнение Майерса с линейной памятью (разделяй и властвуй Хиршберга), снижающее пиковую память с O(ND) до O(N): раздели граф редактирования в средней точке, рекурсируй на каждой половине и восстанови полный edit script, никогда не материализуя всю историю V.
- Добавь режим семантического diff с учётом токенов: вместо массивов символов диффуй поток токенов TypeScript AST, чтобы переименование переменной давало единый многоточечный edit script, а не несвязанные построчные diff — замерь, насколько меньше редакционное расстояние на реальном рефакторинге.
- Реализуй patience diff: вместо Myers на сырых токенах сначала найди уникальные общие строки как фиксированные якоря (сортировка patience), делай diff между якорями и покажи эмпирически на реальных исходных файлах, что patience даёт более читаемые ханки, чем наивный Myers при перестановке функций.
- Расширь `apply` до трёхстороннего слияния: при наличии общего предка O и двух расходящихся версий A и B получи объединённый результат, автоматически разрешая неконфликтующие ханки и помечая конфликтные регионы для ручного разрешения — реализуй формат маркеров конфликтов, используемый `git merge`.
- Сравни Myers против DP против WASM-порта libxdiff на случайных файлах по 10k строк и структурированных рефакторингах; сообщи точку пересечения, где O(ND) перестаёт выигрывать у O(MN), и объясни это через соотношение D/N.