diff算法演示

让我们从头开始，从头开始理解这个算法：

第一步很容易理解，它涉及布置一个网格，使我们能够比较要比较的两个序列的不同子部分。

对角线用于表示匹配的项。

现在可以描述任何将第一个序列转换为第二个序列的编辑序列，只需描述从左上角到右下角穿过该图的路径。这两个点之间的所有路径都对应于有效的编辑序列。有些路径比其他路径更可取。

Myers 论文中描述的算法的一个重要部分涉及由 k = x - y 定义的线。这些很重要，因为给定 k 行的任何编辑序列必须至少具有 |k|插入或删除。

D 代表路径的长度

理解迈尔斯论文的一个非常重要的概念是理解“蛇”的概念。该论文将蛇定义如下：“让一条 D 路径是一条从 (0,0) 开始的路径，它恰好具有 D 条非对角边。0 路径必须仅由对角边组成。通过简单的归纳，它因此，一条 D 路径必须由一条 (D − 1) 路径组成，然后是一条非对角边，然后是一个可能为空的对角边序列，称为蛇。”不幸的是，蛇的这个定义没有明确的措辞。仅鉴于此声明，我会理解“蛇”意味着以下可能的事物之一：

• 1) 一条蛇是一个可能为空的对角边序列，不包含水平边或垂直边。
• 2) 一条蛇是一条非对角边，后跟可能为空的对角边序列
• 3) 一条蛇是一条 D 路径，后跟非对角边，后跟可能为空的对角边序列

上面的可视化显示了寻找最短路径的基本算法。请注意，上面描述的算法只是使用线性空间量找到最短编辑脚本的长度。为了恢复完整路径，该算法的变体需要 O(D^2) 空间来恢复完整路径。如步骤 6 中所示，此多项式空间需求减少为线性空间需求。

如上一节所述，恢复完整编辑路径的简单实现需要 O(D^2) 空间。这不是很可扩展，但幸运的是有一种分而治之的方法，只需要线性空间（如上所示）。这种方法运行与上一节中描述的相同的距离测量算法，但它同时从编辑图的两端运行。当它们在中心相遇时，算法会在两个较小的子部分上重复运行。这会重复进行，直到子区域最终成为简单的插入或删除的微不足道的基本情况。