LCS 算法:Javascript 最长公共子序列

javascript admin 61200 0 评论

最长公共子序列(Longest Common Subsequence LCS)是从给定的两个序列X和Y中取出尽可能多的一部分字符,按照它们在原序列排列的先后次序排列得到。LCS问题的算法用途广泛,如在软件不同版本的管理中,用LCS算法找到新旧版本的异同处;在软件测试中,用LCS算法对录制和回放的序列进行比较,在基因工程领域,用LCS算法检查患者DNA连与键康DNA链的异同;在防抄袭系统中,用LCS算法检查论文的抄袭率。LCS算法也可以用于程序代码相似度度量,人体运行的序列检索,视频段匹配等方面,所以对LCS算法进行研究具有很高的应用价值。

基本概念

  1. 子序列(subsequence): 一个特定序列的子序列就是将给定序列中零个或多个元素去掉后得到的结果(不改变元素间相对次序)。例如序列的子序列有:等。
  2. 公共子序列(common subsequence): 给定序列X和Y,序列Z是X的子序列,也是Y的子序列,则Z是X和Y的公共子序列。例如X=[A,B,C,B,D,A,B],Y=[B,D,C,A,B,A[,那么序列Z=[B,C,A]为X和Y的公共子序列,其长度为3。但Z不是X和Y的最长公共子序列,而序列[B,C,B,A]和[B,D,A,B]也均为X和Y的最长公共子序列,长度为4,而X和Y不存在长度大于等于5的公共子序列。对于序列[A,B,C]和序列[E,F,G]的公共子序列只有空序列[]。
  3. 最长公共子序列:给定序列X和Y,从它们的所有公共子序列中选出长度最长的那一个或几个。
  4. 子串: 将一个序列从最前或最后或同时删掉零个或几个字符构成的新系列。区别与子序列,子序列是可以从中间抠掉字符的。cnblogs这个字符串中子序列有多少个呢?很显然有27个,比如其中的cb,cgs等等都是其子序列

给一个图再解释一下:

image_1c3ofq79gg4f1u7sf3o40gls29

我们可以看出子序列不见得一定是连续的,连续的是子串。

问题分析

我们还是从一个矩阵开始分析,自己推导出状态迁移方程。

首先,我们把问题转换成前端够为熟悉的概念,不要序列序列地叫了,可以认为是数组或字符串。一切从简,我们就估且认定是两个字符串做比较吧。

我们重点留意”子序列“的概念,它可以删掉多个或零个,也可以全部干掉。这时我们的第一个子序列为空字符串(如果我们的序列不是字符串,我们还可以 )!这个真是千万要注意到!许多人就是看不懂《算法导论》的那个图表,还有许多博客的作者不懂装懂。我们总是从左到右比较,当然了第一个字符串,由于作为矩阵的高,就垂直放置了。

我们现在用下面的方程来继续填表了。

image_1c3vdljfs1g5p1s5lpppcln1s88m

程序实现

LCS可以进一步简化,只要通过挪位置,省去新数组的生成

打印一个LCS

我们再给出打印函数,先看如何打印一个。我们从右下角开始寻找,一直找到最上一行终止。因此目标字符串的构建是倒序。为了避免使用stringBuffer这样麻烦的中间量,我们可以通过递归实现,每次执行程序时,只返回一个字符串,没有则返回一个空字符串, 以printLCS(x,y,...) + str[i]相加,就可以得到我们要求的字符串。

我们再写出一个方法,来验证我们得到的字符串是否真正的LCS字符串。作为一个已经工作的人,不能写的代码像在校生那样,不做单元测试就放到线上让别人踩坑。

使用:

image_1c3v0n1qnhq1sqa36min2goi16

打印全部LCS

思路与上面差不多,我们注意一下,在LCS方法有一个Math.max取值,这其实是整合了三种情况,因此可以分叉出三个字符串。我们的方法将返回一个es6集合对象,方便自动去掉。然后每次都用新的集合合并旧的集合的字任串。

使用:

image_1c3v1al221m5l1cdlmui48vd831j

空间优化

使用滚动数组:

危险的递归解法

str1的一个子序列相应于下标序列{1, 2, …, m}的一个子序列,因此,str1共有${2^m}$个不同子序列(str2亦如此,如为${2^n}$),因此复杂度达到惊人的指数时间(${2^m * 2^n}$)。

参考链接

  1. http://blog.csdn.net/hrn1216/…
  2. https://segmentfault.com/a/11…
  3. https://www.cnblogs.com/ider/…
  4. http://www.cppblog.com/mysile…

转载请注明: 飞嗨_分享互联网 » LCS 算法:Javascript 最长公共子序列

赞 (0) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽

高效,专业,符合SEO

联系我们