问Myers diff算法与Hunt-McIlroy算法

EN

• Myers算法是一种“分而治之的算法”：它通过递归查找两个序列的中心匹配和最小的编辑脚本来工作。一旦完成这一操作，匹配就会被记忆，然后再递归地比较它前面和后面的两个子序列，直到没有更多的比较。寻找中心匹配是通过尽可能匹配子序列的末端来完成的，在任何不可能的情况下，增加编辑脚本1，扫描每个对角线到那里的每个最远的位置，看看再匹配的距离有多远，如果匹配遇到另一端的匹配，算法就会找到中心匹配。该方法具有占用O(m+n)内存的优点，在O(nd)中执行，具有编辑脚本的复杂性。
• Hunt和McIlroy方法计算整个文件中的匹配，并将它们索引到所谓的k候选文件中。K为LCS长度。LCS是通过找到在适当的纵坐标范围内的匹配(遵循在他们的论文中解释的规则)而逐步增强的。在这样做的时候，每条路都会被记住。这种方法的问题在于它做的工作太多了:它存储所有路径，在最坏情况下存储O(mn)内存，而o(mn log m)存储时间复杂度。

Myers算法主要是因为它在工作时不记住路径，并且不需要“预见”到哪里，因此它可以在任何时候集中精力在最小复杂度的编辑脚本所能达到的最远位置上。这种“最小的复杂性”确保了所发现的是LCS，而不是记住它经过哪条路径，直到找到匹配时才使用更少的内存。不试图提前计算所有匹配，就可以避免它们的存储，并使它们在匹配时间而不是内存占优势。