【第2641期】最长公共子序列(LCS)算法在重新排序项目中的应用
前言
由一个案例延伸出算法在前端的运用。今日前端早读课文章由腾讯@camdyzeng授权分享。
@camdyzeng：腾讯CSIG前端开发高级工程师。团队主要致力于前端相关技术的研究和在腾讯业务的应用，团队内部每周有内部分享会，有兴趣的读者可以加入我们或者参与一起讨论。邮箱：camdyzeng@qq.com。
正文从这开始~~
之前看到技术同学提问“刷算法题对实际工作有多大的作用呢？”，我觉得算法是有用的，所以就简短的回答了一下。我举一个实际中用的的例子，我之前做QQ相册的排序功能的时候遇到的，每张照片都有一个index属性，假设有4张照片，排序时第一张照片挪到最后的情况：
排序前：1,2,3,4
排序后：2,3,4,1
1、最简单最笨的方式是要修改四张照片的index值：1->4,2->1,3->2,4->3;
2、最优解应该是只修改第一张照片index值：1->5
备注：当时架构修改一次index是有成本，当然修改越少次越好
这个例子是肉眼可见的能找到最优解，但是当数据量大，排序后比较混乱的时候就不是那么容易找到最优解了。所以这个时候如果你曾经接触过算法，你就很容易联想到这个问题跟最长公共子序列(LCS)算法要解决的场景非常契合，通过动态规划的思想很容易找到这个问题的最优解，之前一直也没有展开讲LCS。最近我花了一些时间整理了这篇文章详细讲解LCS的算法精妙之处。
一、照片重新排序问题
我们把照片重新排序的问题抽象描述一下，排序前index序列X = [x1,x2,x3,……,xn]是一个递增数组，排序后的index序列Y= [y1,y2,y3,……,yn]是一个乱序的数组，现在要求修改Y数组中的零个或多个yi元素的值，使得Y数组重新成为递增数组。求解修改yi个数最少的方案，并把yi找出来。
上面描述应该比较容易理解，要找出需要修改的yi元素，并且越少越好。反过想，我只要找出Y数组中不需要修改的元素yj，让yj越多越好，不需要修改yj序列也是一个递增数组。问题重新描述一下，Y数组去掉零个或者多个元素后剩余的元素组成新数组Z=[z1,z2,z3,……,zk]，我们称Z是Y的子数组(子序列)，我们要求找到一个递增的子数组(因为是递增的，所以这个子数组Z也是X的子数组，也叫X和Y的公共子数组)，数组元素越多越好，也叫最长递增子数组(也叫X和Y的最长公共子数组)。找到最长递增子数组之后，我们只要把原先去掉的元素修改元素值然后插入到最长递增子数组对应位置使得新的数组也是递增的就可以了。那么怎么找到最长递增子数组？
1、暴力法
最容易想到的是暴力方法，枚举出Y数组的所有子数组，然后逐一检查看其是否是递增的，在所有递增的子数组中查找元素最多的那个数组就是最长递增子数组。Y的子数组有2的n次方个，判断递增又要比较n次，所以这个时间复杂度是n*(2的n次方)，是一个指数时间复杂度的算法，对于数组元素比较多的是不实际的。下面会探讨更优的解法。
二、最长公共子序列(LCS)问题
上面我都是用数组描述，因为排序特定问题下index是数字，并且没有重复的数字，所以用了数组和递增这些概念方便理解。其实问题可以扩展成任意序列，序列里的元素是数字，字符，字符串，结构化数据都可以，元素也可以重复出现。所以我们把问题再抽象一下，给定一个序列X=[X1,X2,X3,……,Xn]，序列的长度就是元素的个数n。X去掉零个或者多个元素后剩余的序列Z=[Z1,Z2,Z3,……,Zk]，我们称Z是X的子序列。给定两个序列X和Y，如果Z是X的子序列又是Y的子序列，我们称Z是X和Y的公共子序列。在X和Y的所有公共子序列Z集合中，序列长度最大的我们称为是X和Y的最长公共子序列(LCS)。LCS可能有零个或多个。
三、求解LCS
1、暴力法
上面提到的暴力方法，枚举出X=[X1,X2,X3,……,Xn]序列的所有子序列，逐一检查是否是Y=[Y1,Y2,Y3,……,Ym]序列的子序列，从中选择最长的那个子序列就是其中一个LCS。这个方法的时间复杂度是O(m * (2的n次方))。
2、递归公式推导
假设Z=[z1,z2,z3,……,zk]是X=[x1,x2,x3,……,xn]和Y=[y1,y2,y3,……,ym]的任意一个LCS。那么X,Y和Z具有以下三个特性：
如果
xn = ym，并且zk = xn = ym，那么Z(k-1)是X(n-1)和Y(m-1)的一个LCS。如果
xn != ym，并且zk != xn，那么Z是X(n-1)和Y的一个LCS。如果
xn != ym，并且zk != ym，那么Z是X和Y(m-1)的一个LCS。
这三个特性很容易用反证法证明，这里就不累赘证明了，读者们只要认真理解一下也很容易想明白。这三个特性说明了LCS具有递归性质，可以把大问题变成子问题，分而治之。如果xn = ym，只要找出X(n-1)和Y(m-1)的LCS,然后把xn加到后面就是X和Y的LCS。如果xn != ym，只要找出X(n-1)和Y的LCS以及X和Y(m-1)的LCS，这两个中最长的就是X和Y的LCS。
道理都讲明白了，但是如何写出递归公式呢？我们又回到问题上，LCS是最长公共子序列，问题关键在最长，就是长度的最大化。那我们就把长度定义出来，假设C[i, j]是序列X(i)和Y(j)的一个LCS的长度。当i = 0或者j = 0时，其中一个序列长度为0，那么LCS的长度也是0。由于上面三个特性，就可以很容易写出递归式:
C[i, j] = 0; 如果i = 0或者j = 0;C[i, j] = C[i-1, j-1] + 1; 如果i,j > 0并且xi = yj;C[i, j] = max(C[i, j-1], C[i-1, j]); 如果i,j > 0并且xi != yj;
这个递推公式是有边界和结束条件的，当i = 0或者j = 0时直接得出结果是0；当xi = yj时，递归求解X(i-1)和Y(j-1)的子问题；当xi != yj时，递归求解X(i)和Y(j-1) 以及X(i-1)和Y(j)两个子问题。每次都有减一，问题在缩小，最终会收敛。
3、计算LCS的长度
有了递归公式，就很容易写出一个递归算法。顺手就来一个
果然是随手一写，累死电脑。分支三不相等的时候需要递归调用两次，然后取最大值，这是一个指数时间复杂度的算法，最差情况是O(2的n+m次方)，对于元素多的序列，计算量是惊人，是接受不了的。有没有更优的算法，答案是有的，这个时候就要用到动态规划算法的思想。如果递归算法是从大到小，那么动态规划就是从小到大。从最小子问题开始算到大问题，把所有子问题的计算结果都缓存起来。计算LCS的长度C[i,j]，所有子问题的空间复杂度是n*m，所以我们可以用一个二维数组来存储中间过程。代码如下
二维数组的结果：
右下角的5就是LCS的长度。动态规划的时间复杂度是O(n*m)，二次方的时间相比于指数时间就优化很多了，电脑是可以接受的。需要增加二维数组缓存结果，所以空间复杂度是n*m。如果仅仅是计算LCS长度的话，缓存空间是可以优化的，因为每次计算只用到上一行的数据，所以只需要缓存两行就能计算LCS长度。但是如果需要构造一个LCS的话，就一定需要整个二维数组了。
4、构造一个LCS
有了上面的二维数组，我们就比较容易构造一个LCS。构造过程是从右下角开始反过来找。如果遇到x[i] = y[j],则是LCS的一个元素，然后跳到c[i-1][j-1]继续递归；如果x[i] != y[j]，则跳到c[i-1][j]与c[i][j-1]中较大值继续递归。代码如下
这个递归算法时间复杂度是O(n+m)，上面例子最后输出的结果是：
这是只是构造出一个LCS，其实LCS可能存在多个，看上面代码注释分支三，如果两个一样大任意选一个都可以，穷尽所有路径就能找出所有LCS。细心的读者可能会发现，这里面空间复杂度度可以做一些优化，构造LCS每次判断只有三种选择，所以二维数组只要存三种状态就可以了，可以使用二进制或者byte来存储，计算LCS长度的时候就把这个简化的二维数组计算好，这样LCS长度只要两行辅组空间，再加上这里简化的二维数组，就能省下不少存储空间。
5、解答照片重新排序问题
再回到文章开始照片重新排序问题，找到一个LCS之后。如何更好解决后续的一些问题。
1、怎么快速找出需要修改index的照片？
看上面构造一个LCS的代码注释分支二，找到LCS元素之后记录元素的位置下标。然后遍历一遍排序后的数组，没有被记录下标的都是需要修改index的照片。
2、怎么修改index合适？
由于不需要修改的照片已经记录下标了，所以可以知道LCS相邻元素需要插入的照片的个数，LCS相邻元素的index差值平均分给需要插入的照片的index就可以了。头尾边界情况需要特殊处理一下。
3、差值不够分怎么办？
index可以使用浮点数，并且支持负数。如果index一定要用整数，在初始化的时候预留一定的区间方便后续调整顺序时插入。如果浮点数由于精度限制确实不够空间插入，或者整数预留空间不够，理论上也是有可能的。这种特殊情况就需要降级处理，去掉LCS中的一个元素再试，或者全部修改index都时可以接受的，毕竟是小概率情况。
4、最长递增子数组还有O(nLogn)的方法
这篇文章先发公司内分享，收到内部同事反馈，最长递增子数组，对于这个特定问题，还有一种更优的解法，时间复杂度是O(nLogn)的，我后面想了一下貌似确实是。这里就不详细分析了，感兴趣的读者可以自己研究研究。
6、LCS算法还可以使用在什么场景？
LCS是经典的动态规划算法，它是能找到两个序列中相似的部分。应用也比较广，教科书上说的如DNA的相似度比对，文章相似对比对等。我自己是在重新排序项目用到，项目中常常遇到的列表重新调整顺序都可以用。另外前端同学都知道的React等使用了虚拟Dom的框架， React Diff算法判断同层级节点增删移动的时候也可以用使用LCS做一些优化，有兴趣的同学可以朝这个方向实践一下。
关于【算法】相关推荐。欢迎自荐投稿，前端早读课等你。