Myers diff算法与Hunt-McIlroy算法

Myers diff算法与Hunt-McIlroy算法

• 该 迈尔斯算法* 是“分而治之算法”：它的工作原理是寻找递归两个序列的中央配以最小的编辑脚本。完成此 *** 作后，只会记住匹配项，然后再次递归比较之前和之后的两个子序列，直到没有其他可比较的为止。通过尽可能地匹配子序列的末端来找到中心匹配项，并且在不可能的情况下，将编辑脚本增加1，扫描每个对角线到达的最远位置，然后查看多远匹配可以进行，如果匹配遇到另一端的匹配，则算法只是找到了中心匹配。这种方法的优点是占用O（m + n）内存，并在 O（nd）中 执行 *，d具有编辑脚本的复杂性。

• 在 亨特和麦克罗伊 接近整个文件索引他们的计算匹配，进入所谓的K-候选人。k是LCS长度。通过找到属于适当纵坐标内的匹配项（遵循其论文中解释的规则），逐步增强LCS。在执行此 *** 作时，将记住每条路径。这种方法的问题在于它做的工作比必要的多：它会记住所有路径，最坏的情况是 O（mn） 内存，时间复杂度是 o（mn log m） 。

Myers算法之所以能胜出，是因为它在工作时不会记住路径，也不需要“预见”要去的地方，因此它可以随时仅专注于使用最小复杂度的编辑脚本可以到达的最远位置。
。这种“最小的复杂性”可确保找到的是LCS，并且不会记住找到匹配项所经过的路径，直到找到匹配项时才使用更少的内存。不尝试提前计算所有匹配项将避免它们的存储，并使它们在匹配时受益，而不是浪费内存。