模組 Diffing

參數化差異比較

此模組實作對任意內容列表的差異比較。它由以下參數化：

• 兩個列表的內容
• 當元素被保留時的相等性證明
• 當元素被更改時的差異比較證明

差異比較被擴展以維護在遍歷兩個列表時取決於已計算變更的狀態。

底層演算法是修改後的 Wagner-Fischer 演算法（請參閱 <https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm>）。

我們提供以下保證：給定兩個列表 l 和 r，如果不同的修補導致不同的狀態，我們說狀態發散。

• 我們總是返回在 l 和 r 的前綴上的最佳修補，在其上狀態不會發散。
• 否則，我們返回一個正確但非最佳的修補，其中沒有發散狀態的子修補對於給定的初始狀態是最佳的。

更精確地說，Wagner-Fischer 的最佳性取決於左輸入的 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-前綴的狀態的代表。

如果此屬性不滿足，我們仍然可以貪婪地選擇一個代表狀態。但是，計算出的修補不再保證是全局最佳的。儘管如此，它仍然是一個正確的修補，甚至在所有探索的修補中也是最佳的。