从LCS到IGListKit框架中的Diff算法（上）

什么是LCS

子序列

假设有两个序列 X, Z：


若 Z 序列中的每个元素都能在 X 中找到，并且是严格递增的，那么就称 Z 是 X 的子序列。

公共子序列

Z 既是 X 的子序列， 也是 Y 的子序列，则称 X，Y 的公共子序列是 Z，公共子序列长度为元素的个数。

最长公共子序列

最长公共子序列（Longest Common SubSequence），简称 LCS，指的是两个序列中元素个数最多的公共子序列。

的广泛应用

LCS 是一个经典的计算机科学问题，也是数据比较程序，LCS主要应用在：

• Git等版本控制中文件的对比
• 一些做图片、文件、文本等对比的软件
• IGListKit框架中的Diff算法来做UICollectionView的刷新

如何求两个序列的

给定两个序列：


求 X，Y 的最长公共子序列。

蛮力算法

依次检查 X 中的每个子序列在 Y 中是否出现。
时间复杂度：

分析：这个时间复杂度是一个指数级，很明显这个算法是不合适的。

动态规划算法

一、子问题界定
假设 X 序列终止位置为 ，Y 序列终止位置为 ：


如图所示：

2022060901.png
二、子问题之间的依赖关系
设，
为 X 和 Y 的 LCS，那么：
（一）如果 => ，则是和的 LCS，如下图所示：
2022060902.png
（二）如果， => 是 和 的 ，如下图所示：
2022060903.png
（三）如果， => 是 和 的 ，如下图所示：
2022060904.png
三、递推方程
与 的子序列：


是 和 的 的长度，由此我们可以得到递推方程为：

求解的具体实例

例1：两个序列


求 和 的

2022060905.png
可以得到 和 的 为：， 长度为3。
具体求解算法如下：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j]);
                dp[i][j] = Math.max(dp[i][j - 1], dp[i][j]);
            }
        }
        return dp[m][n];
    }
}

时间复杂度：
大家要有兴趣，也可以上LeetCode上找到这个求解 的算法题练习大家的算法。

从 到Diff

如果我们仔细观察会从上图中得到一个特别有意思的地方，现在我们假设 为旧数据， 为新数据，再结合上图用蓝色箭头标记出来的路线图从右下角开始观察会发现:

• 从<label style="color:green">左上角</label>走的单元里的元素是 和 都存在的元素，那么旧数据里的这个元素会通过Move或Reload变成新数据的元素。
• 从<label style="color:green">左边</label>走的单元里的元素表示 里面没有，里面有的元素，那么就会通过Insert操作将元素插入新数据里面。
• 从<label style="color:green">上边</label>走的单元里的元素表示里面有，里面没有的元素，那么就会通过Delete操作将元素从旧数据里面删除。
  最后，我们就可以得到旧数据 变成新数据 的所有元素的操作如下：
• Reload：A、T
• Insert：O、X
• Delete：D、G
• Move：F

存在的问题

我们接下来再来简单的看一个例子：


求 和 的

2022060906.png
可以得到 和 的 为： 或 ，长度为2。
通过上面的分析，我们发现元素的操作如下：

• Reload：A
• Insert：T、O、X
• Delete：D、G、T
• Move：F
  我们会发现元素T既进行了Delete操作也进行了Insert操作，但是却没有Move操作，我们会发现：当两个序列存在多个 的时候，只会取其中的一组，其他的只能进行Delete或Insert操作。

存在的问题：

• 虽然通过动态规划的算法将时间复杂度降低到了 ，但是当特别大的时候，这个时间复杂度依然比较可怕。
• 希望对新、旧数据都存在的元素的Move进行一些优化，而不是简单的Delete、Insert操作。

最后

问题我们已经抛出来了，我们如何解决上面的两个问题，在降低时间复杂度的同时对Move操作进行一些优化，下一篇我们将谈到iOS中IGListKit框架中的Diff是如何巧妙解决这两个问题的。

更多技术文章欢迎移步Sunny的个人技术博客。