0x4*_*672 8 algorithm diff lcs
最常见的子序列问题是典型的计算机科学问题,解决它的算法是版本控制系统和维基引擎的根源.两种基本算法是用于创建原始版本的Hunt-McIlroy算法diff,以及目前由GNU diff实用程序使用的Myers diff算法.通过在表示两个字符串或文本文件之间的编辑空间的图形中找到最短路径,两者似乎都或多或少地起作用.编辑空间是将一个序列转换为另一个序列所需的插入或删除次数.那么Myer的diff算法和Hunt-McIlroy算法之间到底有什么区别呢？
arm*_*mel 15
该迈尔斯算法是"分而治之算法":它的工作原理是寻找递归两个序列的中央配以最小的编辑脚本.完成此操作后,只记忆匹配,并再次递归地比较它之前和之后的两个子序列,直到没有更多要比较的方式.找到中心匹配是通过尽可能匹配子序列的末端来完成的,并且在任何时候都不可能,将编辑脚本增加1,扫描每个对角线到达的最远位置,再看多远匹配可以去,如果匹配遇到另一端的匹配,算法才找到中心匹配.这种方法的优点是占用O(m + n)存储器,并在O(nd)中执行,使编辑脚本复杂化.
在亨特和麦克罗伊的方法计算在整个文件相匹配,并将其索引到所谓的K-候选人.k是LCS长度.LCS通过找到属于适当纵坐标的匹配来逐步增加(遵循他们的论文中解释的规则).在这样做时,每条路径都会被记忆.该方法的问题在于它完成了比必要工作更多的工作:它记忆所有路径,最坏情况下的O(mn)存储器和时间复杂度的o(mn log m).
迈尔斯算法大多胜利,因为它在工作时不会记住路径,并且不需要"预见"去哪里,这样做它可以随时集中在它可以通过最小复杂度的编辑脚本到达的最远位置.这种"最小的复杂性"确保找到的是LCS,而不是记住它通过哪条路径,直到找到匹配使用更少的内存.不尝试提前计算所有匹配可以避免它们的存储,并使它们在匹配时获益,而不是记忆.