Модуль Диффинга

Параметрический диффинг

Этот модуль реализует диффинг над списками произвольного содержимого. Он параметризован

• Содержимым двух списков
• Свидетелем равенства, когда элемент сохраняется
• Свидетелем диффинга, когда элемент изменяется

Диффинг расширен для поддержания состояния в зависимости от вычисленных изменений во время прохода по двум спискам.

Основной алгоритм — это модифицированный алгоритм Вагнера-Фишера (см. <https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm>).

Мы предоставляем следующую гарантию: для двух списков l и r, если разные патчи приводят к разным состояниям, мы говорим, что состояние расходится.

• Мы всегда возвращаем оптимальный патч для префиксов l и r, на которых состояние не расходится.
• В противном случае мы возвращаем корректный, но не оптимальный патч, где подпатчи без расходящихся состояний являются оптимальными для заданного начального состояния.

Более точно, оптимальность Вагнера-Фишера зависит от свойства, что расстояние редактирования между k-префиксом левого входного списка и l-префиксом правого входного списка d(k,l) удовлетворяет

d(k,l) = min ( стоимость_удаления + d(k-1,l), стоимость_вставки + d(k,l-1), стоимость_изменения + d(k-1,l-1) )

При этом предположении, оптимальным является жадное выбор состояния минимального патча, преобразующего левый k-префикс в правый l-префикс, в качестве представителя состояний всех возможных патчей, преобразующих левый k-префикс в правый l-префикс.

Если это свойство не выполняется, мы все равно можем жадно выбрать представительское состояние. Однако вычисленный патч больше не гарантированно является глобально оптимальным. Тем не менее, это по-прежнему корректный патч, который является даже оптимальным среди всех изученных патчей.