Сравнение изменений

Параметрическое сравнение изменений

Этот модуль реализует сравнение изменений в списках произвольного содержимого. Оно параметризуется следующими элементами:

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

Сравнение изменений расширено для сохранения состояния, зависящего от вычисленных изменений при обходе двух списков.

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

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

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

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

d(k,l) = min ( del_cost + d(k-1,l), insert_cost + d(k,l-1), change_cost + d(k-1,l-1) )

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

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