Myers diff 算法与 Hunt–McIlroy 算法
Myers diff algorithm vs Hunt–McIlroy algorithm
目前最长common subsequence problem is a classic computer science problem, algorithms to solve it are the root of version control systems and wiki engines. Two basic algorithms are the Hunt–McIlroy algorithm which was used to create the original version of diff, and the Myers diff algorithm which is used by the GNU diff utility。两者似乎都或多或少地通过 通过表示两个字符串 或文本文件之间的编辑 space 的图形找到最短路径来工作。 edit space 是将一个序列转换为另一个序列所需的插入或删除次数。那么Myer的diff算法和Hunt-McIlroy算法到底有什么区别呢？
Myers 算法 是一种“分而治之算法”：它通过递归地找到两个序列与最小编辑脚本的中心匹配来工作。完成此操作后，只会记住匹配项，并且会递归地再次比较其前后的两个子序列，直到没有更多内容可比较为止。找到中心匹配是通过尽可能匹配子序列的末端来完成的，并且在不可能的时候，将编辑脚本增加 1，扫描每个对角线到达那里的每个最远位置，然后再次查看多远匹配可以进行，如果匹配遇到另一端的匹配，则算法只是找到中心匹配。这种方式的优点是占用O(m+n)内存，执行时间为O(nd)，d为编辑脚本复杂度。
Hunt 和 McIlroy 方法在整个文件中计算匹配项，并将它们索引到所谓的 k-候选者中。 k 是 LCS 长度。 LCS 通过查找落在适当纵坐标内的匹配项（遵循他们的论文中解释的规则）逐渐增强。这样做时，每条路径都会被记住。该方法的问题是它做了比必要更多的工作：它记住了所有路径，在最坏的情况下 O(mn) 内存，并且 o(mn log m)为时间复杂度。
迈尔斯算法大部分获胜是因为它在工作时不记忆路径，不需要“预见”去哪里，这样它可以随时专注于它可以到达的最远位置编辑最复杂的脚本。这种“最小的复杂性”确保找到的是 LCS，而不是记住它经过的路径，直到找到匹配使用更少的内存。不尝试提前计算所有比赛可以避免存储它们，并使它们在比赛时受益而不是占用内存。
目前最长common subsequence problem is a classic computer science problem, algorithms to solve it are the root of version control systems and wiki engines. Two basic algorithms are the Hunt–McIlroy algorithm which was used to create the original version of diff, and the Myers diff algorithm which is used by the GNU diff utility。两者似乎都或多或少地通过 通过表示两个字符串 或文本文件之间的编辑 space 的图形找到最短路径来工作。 edit space 是将一个序列转换为另一个序列所需的插入或删除次数。那么Myer的diff算法和Hunt-McIlroy算法到底有什么区别呢？
Myers 算法 是一种“分而治之算法”：它通过递归地找到两个序列与最小编辑脚本的中心匹配来工作。完成此操作后，只会记住匹配项，并且会递归地再次比较其前后的两个子序列，直到没有更多内容可比较为止。找到中心匹配是通过尽可能匹配子序列的末端来完成的，并且在不可能的时候，将编辑脚本增加 1，扫描每个对角线到达那里的每个最远位置，然后再次查看多远匹配可以进行，如果匹配遇到另一端的匹配，则算法只是找到中心匹配。这种方式的优点是占用O(m+n)内存，执行时间为O(nd)，d为编辑脚本复杂度。
Hunt 和 McIlroy 方法在整个文件中计算匹配项，并将它们索引到所谓的 k-候选者中。 k 是 LCS 长度。 LCS 通过查找落在适当纵坐标内的匹配项（遵循他们的论文中解释的规则）逐渐增强。这样做时，每条路径都会被记住。该方法的问题是它做了比必要更多的工作：它记住了所有路径，在最坏的情况下 O(mn) 内存，并且 o(mn log m)为时间复杂度。
迈尔斯算法大部分获胜是因为它在工作时不记忆路径，不需要“预见”去哪里，这样它可以随时专注于它可以到达的最远位置编辑最复杂的脚本。这种“最小的复杂性”确保找到的是 LCS，而不是记住它经过的路径，直到找到匹配使用更少的内存。不尝试提前计算所有比赛可以避免存储它们，并使它们在比赛时受益而不是占用内存。