最长公共子序列问题是一个经典的计算机科学问题，解决它的算法是版本控制系统和维基引擎的根源。两个基本算法是Hunt-McIlroy算法，它被用来创建diff的原始版本，以及Myers diff算法，它目前被GNU diff实用程序使用。两者似乎都通过在代表两个字符串或文本文件之间编辑空间的图形中找到最短路径来工作。编辑空间是将一个序列转换为另一个序列所需的插入或删除数量。那么Myer's diff算法和Hunt-McIlroy算法之间到底有什么区别呢？
1个回答
34
Myers 算法 是一种 "分而治之算法"：它通过递归地找到两个序列中具有最小编辑脚本的中央匹配来工作。一旦完成了这个步骤，只有匹配被记忆，然后再次递归地比较前面和后面的两个子序列，直到没有更多内容可比较为止。通过尽可能匹配子序列的结尾来找到中央匹配，如果不可能，则每次将编辑脚本增加1，并扫描达到每个对角线上的最远位置，看看再次匹配可以走多远，如果遇到另一个端点的匹配，算法就找到了中央匹配。这种方法的优点是占用O(m+n)内存，并在O(nd)的时间内运行，其中d是编辑脚本复杂度。
Hunt 和 McIlroy 方法计算整个文件中的匹配项，并将它们索引为所谓的k候选项，k是LCS长度。LCS逐步增大，通过找到落在适当坐标内的匹配项（按照他们的论文中解释的规则）进行实现。在此过程中，每个路径都被记忆。该方法的问题在于它执行的工作过多：它记忆了所有路径，在最坏情况下需要O(mn)内存，并且时间复杂度为o(mn log m)。
Myers 算法大多胜出是因为它在工作时不会记忆路径，也不需要“预见”何处前进，因此它可以随时只集中在能够用最小复杂度的编辑脚本到达的最远位置上。这个“最小复杂度”确保找到的是LCS，而不是通过哪条路径记忆，使用更少的内存。不尝试提前计算所有匹配项避免了它们的存储，并使它们在匹配时成为一个好处，而不是占用内存。
- armel
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接