Myers diff算法与Hunt-McIlroy算法

  • Z时代
  • 2024-01-10
  • 分类：问答

最长的常见子序列问题是经典的计算机科学问题，解决该问题的算法是版本控制系统和Wiki引擎的根本。有两种基本算法：用于创建原始版本的Hunt-McIlroy算法diff和当前由GNUdiff实用程序使用的Myersdiff算法。通过

或文本文件

两者似乎或多或少地起作用。编辑空间是将一个序列转换为另一个序列所需的插入或删除次数。那么Myer的diff算法和Hunt-McIlroy算法到底有什么区别？

回答：

  • 该 执行 *，d具有编辑脚本的复杂性。

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

Myers算法之所以能胜出，是因为它在工作时不会记住路径，也不需要“预见”要去的地方，因此它可以随时仅专注于使用最小复杂度的编辑脚本可以到达的最远位置。

。这种“最小的复杂性”可确保找到的是LCS，并且不会记住找到匹配项所经过的路径，直到找到匹配项时才使用更少的内存。不尝试提前计算所有匹配项将避免它们的存储，并使它们在匹配时受益，而不是浪费内存。

以上是 Myers diff算法与Hunt-McIlroy算法 的全部内容， 来源链接： utcz.com/qa/418297.html

回到顶部