最长的common subsequence problem是一个经典的计算机科学问题,解决它的算法是版本控制系统和wiki引擎的根源。两种基本算法是Hunt–McIlroy algorithm,它用于创建diff
的原始版本,以及Myers diff algorithm,它由GNU diff utility当前使用。两者似乎都或多或少地通过找到表示两个字符串或文本文件之间的编辑空间的图表的最短路径。编辑空间是将一个序列转换为另一个序列所需的插入或删除次数。那么Myer的差异算法和Hunt-McIlroy算法究竟有什么区别呢?Myers diff算法vs Hunt-McIlroy算法
0
A
回答
1
的迈尔斯算法是“分而治之算法”:它的工作原理是寻找递归两个序列的中央配以最小的编辑脚本。一旦完成,只有匹配被记住,并且递归地比较它之前和之后的两个子序列,直到没有其他要比较的东西。通过尽可能地匹配子序列的末端来找到中心匹配,并且在任何时候不可能的情况下,通过将编辑脚本增加1来扫描每个对角线到达那里的每个最远位置并且再次看到多远比赛可以去,如果一场比赛遇到另一端的比赛,该算法刚刚发现中央匹配。这种方法具有占用O(m + n)存储器的优点,并且在执行编辑脚本复杂度时执行。
亨特和麦克罗伊方法计算匹配整个文件,并将它们索引到所谓的k候选。 k是LCS长度。 LCS通过找到属于正确坐标的匹配来逐步增加(遵循他们的论文中的规则)。这样做的每条路都被记住。这种方法存在的问题是,它的工作量超过了必要的:它记录了所有的路径,在最坏的情况下存储所有的路径,并且在时间复杂度方面存储所有的路径和o(mn log m)。
迈尔斯算法主要是赢,因为它没有记忆,而工作路径,并不需要“预见”到哪儿去,这样就可以在任何时间只在它可能到达的最远位置集中用最小复杂度的编辑脚本。这个“最小的复杂性”确保找到的是LCS,而不是记住它通过哪条路径,直到找到匹配使用更少的内存为止。不要试图提前计算所有匹配,以避免他们的存储,并使他们在比赛时间而不是记忆猪。
相关问题
- 1. Diff算法
- 2. Diff算法C++
- 3. 算法VS代码
- 4. RequestFactory DIFF计算和“静态” find方法
- 5. 什么是Linux diff -y的算法?
- 6. Minimax vs Alpha Beta Pruning算法
- 7. 变量vs长算法
- 8. 选举算法 - 环算法
- 9. 算法:Esau-Williams算法
- 10. 图算法来算
- 11. 用算法计算
- 12. 测试和设置VS Peterson算法
- 13. 公钥长度vs加密算法
- 14. C# - 空VS “无法计算表达式”
- 15. Dijkstra算法VS A *对于权图
- 16. Python整数除法运算符vs math.floor
- 17. 射线追踪:Bresenham's vs Siddon算法
- 18. UIimagejpegrepresentation压缩质量vs其他算法
- 19. MYSQL评级算法
- 20. 以太网CRC32计算 - 软件vs算法结果
- 21. 算法
- 22. 算法
- 23. 字消歧算法(Lesk算法)
- 24. 贪婪算法的一般算法
- 25. 算法分析(big-O)算法
- 26. 修复算法计算法线
- 27. 击败Strassen算法的算法
- 28. 在php中无法算出算法
- 29. 具有模糊差分度量的Diff算法
- 30. Diff算法,即最短的编辑图路径