最小编辑距离动态规划方法正确性证明
Proof of correct of the dynamic programming approach to min edit distance
为了计算最小编辑距离（将一个词转换为另一个词所需的最小插入、删除和替换量），动态规划解决方案基于递归关系，其中检查两个字符串的最后一个字符。详情在https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm.
关于编辑距离，网上到处都是关于这个算法的描述，但都只是断言其正确性，没有证明。根据编辑距离的定义，您可以在中间插入、删除或替换字符，而不仅仅是在末尾。那怎么证明这个递归关系真的成立呢？
使用归纳法证明递归算法的正确性
首先，正如我在评论中所说，您可以将动态规划视为一种加速递归的方法，证明递归算法正确的最简单方法几乎总是通过 induction：证明它是在一些小的基本情况下正确，然后表明，假设它对大小为 n 的问题是正确的，它对大小为 n+1 的问题也是正确的。通过这种方式，证明紧密地反映了递归结构。
此问题的通常递归将问题 "Find the minimum cost to edit string A into string B" 分解为 (|A|+1)(|B|+1) 个子问题 "Find the minimum cost to edit the first i characters of string A into the first j characters of string B"，对于所有 0 <= i <= |一个|和 0 <= j <= |B|。
选择基本案例
通常通过归纳法，我们可以选择少量简单的基本案例（也许只有一个），表明我们可以轻松地为它们计算出正确答案，并且很明显如何暗示所有其他案例的正确性通过基本案例的正确性，因为无论我们从什么案例开始，都只会有一个 "chain" 的假设需要满足，而且这条链显然必须在我们的基本案例之一结束。然而，对于这个特定问题，为了证明该算法最优地解决了 (i, j) 子问题，我们需要首先假设它解决了 (i-1, j)、(i, j-1) 和 (i-1) , j-1) 子问题最优（因为如果这些子问题的任何答案不正确，它很容易为 (i, j) 子问题计算出一个完全错误的答案）。这将需要比平常更复杂的归纳：而不是需要满足的单个 "chain" 假设，我们现在有分支 "tree" 假设，（最多）3 children 在每个点。我们需要以这样的方式选择基本案例，即对于 any (i, j)，这整个假设树最终 "stops"，即其中的每条路径最终都会遇到一个满足其假设的基本情况。
回顾一下：为了证明我们对 (i, j) 的最优解，我们必须假设我们有 (i-1, j)、(i, j-1) 和 (i-1, j-1);为了满足 (i-1, j) 的假设（即证明我们对 (i-1, j) 的解决方案是最优的），我们需要假设我们有 (i-2, j) 的最优解决方案), (i-1, j-1) and (i-2, j-1), 等等等等。如何选择可行的基本案例？在向下遍历这棵树时，即从证明我们对子问题 (i, j) 的解决方案正确到证明我们对其 "child" 子问题 (i', j') 中任何一个的解决方案正确，我们注意到:
- i' < i 或 j' < j 中至少有一个成立。
- 我们从来没有 "skip over" 子问题——也就是说，我们从来没有 i-i' >= 2，或 j-j' >= 2.
基本上，如果我们沿着这棵树向下移动一步，我们的两个 "subproblem co-ordinates"（i 或 j）中至少有一个会减少，但不会超过 1。这意味着如果我们保持通过树下降，然后不管我们在下降的过程中选择了哪个特定的 "children" 子问题，我们最终必须为（至少）其中一个 co-ordinates 找到一个 0 的子问题——即 ( i'', 0) 一些 0 <= i'' <= |A| 的子问题或某个 0 <= j'' <= |B| 的 (0, j'') 子问题。这意味着如果我们将 那些 子问题作为我们的基本情况，我们可以确保归纳树中的每条路径都遇到满足其假设的基本情况，因此可以停止。
幸运的是，这些基本案例确实很容易计算出最佳答案。考虑一个问题 (i, 0)：这个问题要求将字符串 A 的前 i 个字符更改为字符串 B 的前 0 个字符所需的最小成本。显然最好（唯一！）的方法是删除所有A 前缀中的 i 个字符，成本为 i。同样，问题 (0, j) 要求将 A 的前 0 个字符更改为 B 的前 j 个字符所需的最小成本：同样清楚，最好的方法是简单地将所有 j 个字符插入此前缀中B 的成本，j 的成本。
归纳步骤
剩下的就是归纳步骤：表明我们正确计算了 (i, j) 子问题的答案，假设我们已经计算了 (i-1, j) 的答案，(i , j-1) 和 (i-1, j-1) 子问题正确。诀窍是看到以各种可能的方式将 A 的前 i 个字符编辑为 B 的前 j 个字符，实际上我们可以用最后一个做 3 种可能的事情每个前缀中的字符（即 A 中的 i-th 字符和 B 中的 j-th 字符）：
- 将 A[i] 与 B[j] 配对。它们要么匹配（成本 0），要么不匹配（成本 1），但无论哪种方式，此配对的总成本必须是该成本（0 或 1）加上编辑 rest[ 的最小可能成本=51=] 的前缀 A (A[1 .. i-1]) 到 rest 的前缀 B (B[1 .. j-1]) - - 根据假设，我们已经正确计算了！
- 删除A[i]。这花费 1，所以 th这样做的总成本必须是 1 加上将 A (A[1 .. i-1]) 前缀的 rest 编辑为 的最小可能成本entire B 的前缀 (B[1 .. j]) -- 根据假设，我们已经正确计算了！
- 插入 B[j]。这花费了 1，所以这样做的总花费必须是 1 加上将 A (A[1 .. i]) 的 整个 前缀编辑到 rest of the prefix of B (B[1 .. j-1]) -- 根据假设，我们已经计算正确了！
因为这 3 件事是我们可以做的唯一可能的事情，并且对于这 3 件事中的每一件事，我们都计算了做那件事的总体最低成本，总体上最好的要做的事情必须是他们三个中最好的。这证明我们正确计算了将 A 的前 i 个字符编辑为 B 的前 j 个字符所需的最低成本，对于 any i 和 j —— 因此特别是，它适用于我 = |A| j = |B|，即把完整的字符串A编辑成完整的字符串B。
我找不到任何令人满意的证据，所以我做了一个。我读过的所有证据实际上并不能证明这些案例都是详尽无遗的。
(A) 总存在至少一个最优的编辑系列，称其为Eo
这很简单。
(B) 在 Eo 中有些字符永远不会被插入或更改。让最后一个这样的字符被称为 pivot.
如果没有，我们可以使用字符串的开头作为主元。在Eo中，这个公共子序列从头到尾都没有改变。我们不假设它是最长的公共子序列或任何东西。
例）#KITTEN,#SITTING → 主元：'#ITTN'[-1] = 'N'
这个枢轴有一些属性可以使问题变得更容易。
- 枢轴的左右两边相互独立。一侧发生的任何编辑都不会影响另一侧。
- 根据定义(B)，目标字符串中心点右侧的所有字符都应该通过替换或添加来正确。
由于(1)我们只需要考虑原串和目标串的主元右边。让我们假设左侧是最优的（贪婪的）并且编辑次数将添加到总数中。
例如）
#weofanbmcdepmqu -> #eopasbctdewni
只考虑pmqu → wni
使用（2）这个子问题可以解决如下。
len(原始)>len(目标): asdfgh→qwer
删除 len(original)-len(target) 次以适合长度，并替换 len(target) 次以适合字符。它可以按任何顺序完成，因为它们在距离上都是等效的。在最后一次编辑时删除最后一个字符是此类解决方案之一，它等于 dp(original[:-1]→target) + 1.
len(原始) asdf→qwerty
添加 len(target)-len(original) 次以适应长度，并替换 len(original) 次以适应字符。在最后一次编辑时添加最后一个字符等于 dp(original→target[:-1])+1.
len(原始)==len(目标)!=0: asdf→qwer
替换为长度。相当于替换上次编辑的最后一个字符。 dp(原始[:-1]→目标[:-1])+1
len(原始)==len(目标)==0: ' '→' '
最后一个字符是枢轴。当最后一个字符是相同的字符时会发生这种情况。您不编辑枢轴，因此它与 dp(original[:-1]->target[:-1])
相同
这是我的证明：
为了从字符串 A 到 B，我们从左到右执行一组最佳操作。有4种操作：EQ（保留字符），SWAP（改变字符），INS（插入一个字符），DEL（删除一个字符）。这是编辑距离的定义，EQ的成本== 0.
定义A的长度为a，B的长度为b。
定义d[a,b]为A的前a个字符与B的前b个字符之间的编辑距离，即为了得到A需要进行的操作数（除EQ外）到 B.
如果我们看一组最佳操作（必须有一个），最后一个操作有 4 个选项。我们不知道最后一个操作，所以我们检查所有 4 个选项并选择最好的一个（最好意味着最小编辑距离）。
如果最后一个操作是EQ，则意味着A[a]==B[b]，编辑距离等于d[a-1,b-1]，因为EQ不被认为是“编辑距离”成本。
如果最后一个操作是 SWAP 那意味着 A[a]!=B[b] 并且编辑距离等于 d[a-1, b-1] + 1.
如果操作是 INS 意味着编辑距离是 d[a, b-1] + INS(to B)
如果操作是 DEL 这意味着编辑距离是 d[a-1, b] + DEL(from A)
我们简单地尝试从最后到第 4 个操作的所有组合，直到找到最佳路径。实际上每一步都是3次操作，因为我们可以根据当前字符是否相等来决定是检查EQ还是SWAP。 （如果它们相等，则无需检查 SWAP 操作，反之亦然）。
由于我们尝试了所有可能的操作，因此递归公式必须为真。
假设我们正在使用最小编辑序列将长度 m 的字符串 A 编辑为长度 n 的字符串 B。
需要注意的一个关键事实是，在 minimal 编辑序列中，A 和 B 中的每个字符最多操作一次. （这很容易证明；如果一个字符被操作两次，我们可以将这些操作组合成一个等价操作。）
于是我们可以将A和B中的字符划分为：
A 中已删除的字符（不在 B 中）B 中插入的字符（不在 A 中）- 来自
A 的字符对和来自 B 的字符对，它们是：
- 已替换（因此不同）
- 独自一人（因此相同）
考虑 A[m] 和 B[n]，A 和 B 的最后一个字符。以下是最小编辑序列的可能情况；我们声称其中至少有一个是正确的：
A[m]被删除B[n]插入A[m] 与 B[n]
如果1)为假，则A[m]必须与B中的一个字符A[m]'配对，
如果 2) 也为假，则 B[n] 必须与 A.
中的字符 B[n]' 配对
请注意，所有编辑操作都会保留字符的顺序。
所以我们不能在 B[n] 之前有 A[m]' 和在 A[m] 之前有 B[n]' ——否则这些对已经改变了顺序。
因此，A[m]' 是 B[n]，B[n]' 是 A[m]——也就是说，A[m] 与 B[n] 配对，并且证明了权利要求。
剩下的就是对三种可能情况的每一种进行简单的递归。
令 A[..m-1] 表示除最后一个字符 A[m] 之外的所有 A，B[..n-1] 表示除最后一个字符 B[n] 之外的所有 B。
在情况 1) 中，要将 A 编辑为 B，我们必须删除 A[m] 并将 A[..m-1] 编辑为 B，
总共可以在最少 1 + distance(A[..m-1], B) 次操作中完成。
在情况 2) 中，要将 A 编辑为 B，我们必须将 A 编辑为 B[..n-1] 并插入 B[n]，
总共可以在最少 1 + distance(A, B[..n-1]) 次操作中完成。
而在情况 3) 中，我们必须将 A[m] 替换为 B[n]（如果它已更改），或者如果没有更改则保留它，然后将 A[..m-1] 编辑为 B[..n-1]，总共可以在最少 1 + distance(A[..m-1], B[..n-1]) 次操作中完成
或 distance(A[..m-1], B[..n-1]) 操作分别。
由于这些是唯一可能的情况，因此选择最小操作数最小的情况会产生操作数尽可能少的编辑序列。
我发现这些资源很有用：
https://blog.cykerway.com/posts/2021/04/10/minimum-edit-distance.html
https://cstheory.stackexchange.com/questions/10391/proof-of-levenshtein-distance/48178#48178
为了计算最小编辑距离（将一个词转换为另一个词所需的最小插入、删除和替换量），动态规划解决方案基于递归关系，其中检查两个字符串的最后一个字符。详情在https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm.
关于编辑距离，网上到处都是关于这个算法的描述，但都只是断言其正确性，没有证明。根据编辑距离的定义，您可以在中间插入、删除或替换字符，而不仅仅是在末尾。那怎么证明这个递归关系真的成立呢？
使用归纳法证明递归算法的正确性
首先，正如我在评论中所说，您可以将动态规划视为一种加速递归的方法，证明递归算法正确的最简单方法几乎总是通过 induction：证明它是在一些小的基本情况下正确，然后表明，假设它对大小为 n 的问题是正确的，它对大小为 n+1 的问题也是正确的。通过这种方式，证明紧密地反映了递归结构。
此问题的通常递归将问题 "Find the minimum cost to edit string A into string B" 分解为 (|A|+1)(|B|+1) 个子问题 "Find the minimum cost to edit the first i characters of string A into the first j characters of string B"，对于所有 0 <= i <= |一个|和 0 <= j <= |B|。
选择基本案例
通常通过归纳法，我们可以选择少量简单的基本案例（也许只有一个），表明我们可以轻松地为它们计算出正确答案，并且很明显如何暗示所有其他案例的正确性通过基本案例的正确性，因为无论我们从什么案例开始，都只会有一个 "chain" 的假设需要满足，而且这条链显然必须在我们的基本案例之一结束。然而，对于这个特定问题，为了证明该算法最优地解决了 (i, j) 子问题，我们需要首先假设它解决了 (i-1, j)、(i, j-1) 和 (i-1) , j-1) 子问题最优（因为如果这些子问题的任何答案不正确，它很容易为 (i, j) 子问题计算出一个完全错误的答案）。这将需要比平常更复杂的归纳：而不是需要满足的单个 "chain" 假设，我们现在有分支 "tree" 假设，（最多）3 children 在每个点。我们需要以这样的方式选择基本案例，即对于 any (i, j)，这整个假设树最终 "stops"，即其中的每条路径最终都会遇到一个满足其假设的基本情况。
回顾一下：为了证明我们对 (i, j) 的最优解，我们必须假设我们有 (i-1, j)、(i, j-1) 和 (i-1, j-1);为了满足 (i-1, j) 的假设（即证明我们对 (i-1, j) 的解决方案是最优的），我们需要假设我们有 (i-2, j) 的最优解决方案), (i-1, j-1) and (i-2, j-1), 等等等等。如何选择可行的基本案例？在向下遍历这棵树时，即从证明我们对子问题 (i, j) 的解决方案正确到证明我们对其 "child" 子问题 (i', j') 中任何一个的解决方案正确，我们注意到:
- i' < i 或 j' < j 中至少有一个成立。
- 我们从来没有 "skip over" 子问题——也就是说，我们从来没有 i-i' >= 2，或 j-j' >= 2.
基本上，如果我们沿着这棵树向下移动一步，我们的两个 "subproblem co-ordinates"（i 或 j）中至少有一个会减少，但不会超过 1。这意味着如果我们保持通过树下降，然后不管我们在下降的过程中选择了哪个特定的 "children" 子问题，我们最终必须为（至少）其中一个 co-ordinates 找到一个 0 的子问题——即 ( i'', 0) 一些 0 <= i'' <= |A| 的子问题或某个 0 <= j'' <= |B| 的 (0, j'') 子问题。这意味着如果我们将 那些 子问题作为我们的基本情况，我们可以确保归纳树中的每条路径都遇到满足其假设的基本情况，因此可以停止。
幸运的是，这些基本案例确实很容易计算出最佳答案。考虑一个问题 (i, 0)：这个问题要求将字符串 A 的前 i 个字符更改为字符串 B 的前 0 个字符所需的最小成本。显然最好（唯一！）的方法是删除所有A 前缀中的 i 个字符，成本为 i。同样，问题 (0, j) 要求将 A 的前 0 个字符更改为 B 的前 j 个字符所需的最小成本：同样清楚，最好的方法是简单地将所有 j 个字符插入此前缀中B 的成本，j 的成本。
归纳步骤
剩下的就是归纳步骤：表明我们正确计算了 (i, j) 子问题的答案，假设我们已经计算了 (i-1, j) 的答案，(i , j-1) 和 (i-1, j-1) 子问题正确。诀窍是看到以各种可能的方式将 A 的前 i 个字符编辑为 B 的前 j 个字符，实际上我们可以用最后一个做 3 种可能的事情每个前缀中的字符（即 A 中的 i-th 字符和 B 中的 j-th 字符）：
- 将 A[i] 与 B[j] 配对。它们要么匹配（成本 0），要么不匹配（成本 1），但无论哪种方式，此配对的总成本必须是该成本（0 或 1）加上编辑 rest[ 的最小可能成本=51=] 的前缀 A (A[1 .. i-1]) 到 rest 的前缀 B (B[1 .. j-1]) - - 根据假设，我们已经正确计算了！
- 删除A[i]。这花费 1，所以 th这样做的总成本必须是 1 加上将 A (A[1 .. i-1]) 前缀的 rest 编辑为 的最小可能成本entire B 的前缀 (B[1 .. j]) -- 根据假设，我们已经正确计算了！
- 插入 B[j]。这花费了 1，所以这样做的总花费必须是 1 加上将 A (A[1 .. i]) 的 整个 前缀编辑到 rest of the prefix of B (B[1 .. j-1]) -- 根据假设，我们已经计算正确了！
因为这 3 件事是我们可以做的唯一可能的事情，并且对于这 3 件事中的每一件事，我们都计算了做那件事的总体最低成本，总体上最好的要做的事情必须是他们三个中最好的。这证明我们正确计算了将 A 的前 i 个字符编辑为 B 的前 j 个字符所需的最低成本，对于 any i 和 j —— 因此特别是，它适用于我 = |A| j = |B|，即把完整的字符串A编辑成完整的字符串B。
我找不到任何令人满意的证据，所以我做了一个。我读过的所有证据实际上并不能证明这些案例都是详尽无遗的。
(A) 总存在至少一个最优的编辑系列，称其为Eo
这很简单。
(B) 在 Eo 中有些字符永远不会被插入或更改。让最后一个这样的字符被称为 pivot.
如果没有，我们可以使用字符串的开头作为主元。在Eo中，这个公共子序列从头到尾都没有改变。我们不假设它是最长的公共子序列或任何东西。
例）#KITTEN,#SITTING → 主元：'#ITTN'[-1] = 'N'
这个枢轴有一些属性可以使问题变得更容易。
- 枢轴的左右两边相互独立。一侧发生的任何编辑都不会影响另一侧。
- 根据定义(B)，目标字符串中心点右侧的所有字符都应该通过替换或添加来正确。
由于(1)我们只需要考虑原串和目标串的主元右边。让我们假设左侧是最优的（贪婪的）并且编辑次数将添加到总数中。
例如）
#weofanbmcdepmqu -> #eopasbctdewni
只考虑pmqu → wni
使用（2）这个子问题可以解决如下。
len(原始)>len(目标): asdfgh→qwer
删除 len(original)-len(target) 次以适合长度，并替换 len(target) 次以适合字符。它可以按任何顺序完成，因为它们在距离上都是等效的。在最后一次编辑时删除最后一个字符是此类解决方案之一，它等于 dp(original[:-1]→target) + 1.
len(原始)
添加 len(target)-len(original) 次以适应长度，并替换 len(original) 次以适应字符。在最后一次编辑时添加最后一个字符等于 dp(original→target[:-1])+1.
len(原始)==len(目标)!=0: asdf→qwer
替换为长度。相当于替换上次编辑的最后一个字符。 dp(原始[:-1]→目标[:-1])+1
len(原始)==len(目标)==0: ' '→' '
最后一个字符是枢轴。当最后一个字符是相同的字符时会发生这种情况。您不编辑枢轴，因此它与 dp(original[:-1]->target[:-1])
这是我的证明：
为了从字符串 A 到 B，我们从左到右执行一组最佳操作。有4种操作：EQ（保留字符），SWAP（改变字符），INS（插入一个字符），DEL（删除一个字符）。这是编辑距离的定义，EQ的成本== 0.
定义A的长度为a，B的长度为b。
定义d[a,b]为A的前a个字符与B的前b个字符之间的编辑距离，即为了得到A需要进行的操作数（除EQ外）到 B.
如果我们看一组最佳操作（必须有一个），最后一个操作有 4 个选项。我们不知道最后一个操作，所以我们检查所有 4 个选项并选择最好的一个（最好意味着最小编辑距离）。
如果最后一个操作是EQ，则意味着A[a]==B[b]，编辑距离等于d[a-1,b-1]，因为EQ不被认为是“编辑距离”成本。
如果最后一个操作是 SWAP 那意味着 A[a]!=B[b] 并且编辑距离等于 d[a-1, b-1] + 1.
如果操作是 INS 意味着编辑距离是 d[a, b-1] + INS(to B) 如果操作是 DEL 这意味着编辑距离是 d[a-1, b] + DEL(from A)
我们简单地尝试从最后到第 4 个操作的所有组合，直到找到最佳路径。实际上每一步都是3次操作，因为我们可以根据当前字符是否相等来决定是检查EQ还是SWAP。 （如果它们相等，则无需检查 SWAP 操作，反之亦然）。
由于我们尝试了所有可能的操作，因此递归公式必须为真。
假设我们正在使用最小编辑序列将长度 m 的字符串 A 编辑为长度 n 的字符串 B。
需要注意的一个关键事实是，在 minimal 编辑序列中，A 和 B 中的每个字符最多操作一次. （这很容易证明；如果一个字符被操作两次，我们可以将这些操作组合成一个等价操作。）
于是我们可以将A和B中的字符划分为：
A中已删除的字符（不在B中）B中插入的字符（不在A中）- 来自
A的字符对和来自B的字符对，它们是：- 已替换（因此不同）
- 独自一人（因此相同）
考虑 A[m] 和 B[n]，A 和 B 的最后一个字符。以下是最小编辑序列的可能情况；我们声称其中至少有一个是正确的：
A[m]被删除B[n]插入A[m]与B[n] 配对
如果1)为假，则A[m]必须与B中的一个字符A[m]'配对，
如果 2) 也为假，则 B[n] 必须与 A.
中的字符 B[n]' 配对
请注意，所有编辑操作都会保留字符的顺序。
所以我们不能在 B[n] 之前有 A[m]' 和在 A[m] 之前有 B[n]' ——否则这些对已经改变了顺序。
因此，A[m]' 是 B[n]，B[n]' 是 A[m]——也就是说，A[m] 与 B[n] 配对，并且证明了权利要求。
剩下的就是对三种可能情况的每一种进行简单的递归。
令 A[..m-1] 表示除最后一个字符 A[m] 之外的所有 A，B[..n-1] 表示除最后一个字符 B[n] 之外的所有 B。
在情况 1) 中，要将 A 编辑为 B，我们必须删除 A[m] 并将 A[..m-1] 编辑为 B，
总共可以在最少 1 + distance(A[..m-1], B) 次操作中完成。
在情况 2) 中，要将 A 编辑为 B，我们必须将 A 编辑为 B[..n-1] 并插入 B[n]，
总共可以在最少 1 + distance(A, B[..n-1]) 次操作中完成。
而在情况 3) 中，我们必须将 A[m] 替换为 B[n]（如果它已更改），或者如果没有更改则保留它，然后将 A[..m-1] 编辑为 B[..n-1]，总共可以在最少 1 + distance(A[..m-1], B[..n-1]) 次操作中完成
或 distance(A[..m-1], B[..n-1]) 操作分别。
由于这些是唯一可能的情况，因此选择最小操作数最小的情况会产生操作数尽可能少的编辑序列。
我发现这些资源很有用：
https://blog.cykerway.com/posts/2021/04/10/minimum-edit-distance.html
https://cstheory.stackexchange.com/questions/10391/proof-of-levenshtein-distance/48178#48178