[转载]最长公共子序列―O(ND)比较算法和它的变化（翻译）_Bluewind_新浪博客
在之前的最长公共子序列的文章中，我列出了动态规划算法。这是一个伟大的算法，它几乎能适用于很多求解最优解问题。然而，动态规划算法也有它弊端，我们需要足够的空间用来存储决策信息。比如，在求最长公共子序列的问题，虽然我们可以利用滚动数组来求得子序列的长度，但我们却无法逆推得到子序列(参见之前的文章)。所以，为了求得这个子序列（通过每个点保存上一次抉择的由来，最终通过回溯找到路径），我们依然需要开辟N*M的二维数组和使用O(N*M)的时间复杂度。
于是，问题就产生了……它无法满足大文件之间的匹配，会超出内存……
O((M+N)D)的贪心算法
这次介绍的O(ND)比较算法，我们可以参考:
http://code.google.com/p/google-diff-match-patch/
它是从另一角度找出最长公共子序列-贪心，另一个求最优解的伟大算法。首先，关于O(ND)算法，我引用几个概念：
1. Edit Graph：如下图。主要保存两字符串的编辑信息，路径信息，公共子序列信息
2. Edit Script：通过适当的删除和插入字符，使得字符串完全匹配，下图的编辑边为1D,2D,3iB,6D,7IC,D=Delete, I=Insert
3. Snake: 由连续匹配点形成的对角线，称为Snake
4. The Shortest Trace：我们需要找到最短的从 (0, 0) 到 (7, 6) 的路径，即Snake的个数和长度最长，同理Edit Scripts的数量最少。这样的一条路径一定满足花费最小的编辑，就能让两字符串匹配。而这条路径中的Snake便是最长公共子序列了。
Read full article from [转载]最长公共子序列―O(ND)比较算法和它的变化（翻译）_Bluewind_新浪博客
No comments:
Post a Comment