LCS 算法:Javascript 最长公共子序列
最长公共子序列(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等等都是其子序列
给一个图再解释一下:
我们可以看出子序列不见得一定是连续的,连续的是子串。
问题分析
我们还是从一个矩阵开始分析,自己推导出状态迁移方程。
首先,我们把问题转换成前端够为熟悉的概念,不要序列序列地叫了,可以认为是数组或字符串。一切从简,我们就估且认定是两个字符串做比较吧。
我们重点留意”子序列“的概念,它可以删掉多个或零个,也可以全部干掉。这时我们的第一个子序列为空字符串(如果我们的序列不是字符串,我们还可以 )!这个真是千万要注意到!许多人就是看不懂《算法导论》的那个图表,还有许多博客的作者不懂装懂。我们总是从左到右比较,当然了第一个字符串,由于作为矩阵的高,就垂直放置了。
假令X = "ABCDAB", Y="BDCABA",各自取出最短的序列,也就是空字符串与空字符串比较。LCS的方程解为一个数字,那么这个表格也只能填数字。两个空字符串的公同区域的长度为0.
然后我们X不动,继续让空字符串出阵,Y让“B”出阵,很显然,它们的公共区域的长度为0. Y换成其他字符, D啊,C啊, 或者, 它们的连续组合DC、 DDC, 情况没有变, 依然为0. 因此第一行都为0. 然后我们Y不动,Y只出空字任串,那么与上面的分析一样,都为0,第一列都是0.
LCS问题与背包问题有点不一样,背包问题还可以设置-1行,而最长公共子序列因为有空子序列的出现,一开始就把左边与上边固定死了。
然后我们再将问题放大些,这次双方都出一个字符,显然只有两都相同时,才有存在不为空字符串的公共子序列,长度也理解数然为1。
A为"X", Y为"BDCA"的子序列的任意一个
继续往右填空,该怎么填?显然,LCS不能大于X的长度,Y的从A字符串开始的子序列与B的A序列相比,怎么也能等于1。
如果X只从派出前面个字符A,B吧,亦即是“”,“A”, "B", "AB"这四种组合,前两个已经解说过了。那我们先看B,${X1} == ${Y0}, 我们得到一个新的公共子串了,应该加1。为什么呢?因为我们这个矩阵是一个状态表,从左到右,从上到下描述状态的迁移过程,并且这些状态是基于已有状态累加出来的。现在我们需要确认的是,现在我们要填的这个格子的值与它周围已经填好的格子的值是存在何种关系。目前,信息太少,就是一个孤点,直接填1。
然后我们让Y多出一个D做帮手,{"",A,B,AB} vs {"",B,D,BD},显然,继续填1. 一直填到Y的第二个B之前,都是1。 因为到BDCAB时,它们有另一个公共子序列,AB。
到这一步,我们可以总结一些规则了,之后就是通过计算验证我们的想法,加入新的规则或限定条件来完善。
Y将所有字符派上去,X依然是2个字符,经仔细观察,还是填2.
看五行,X再多派一个C,ABC的子序列集合比AB的子序列集合大一些,那么它与Y的B子序列集合大一些,就算不大,就不能比原来的小。显然新增的C不能成为战力,不是两者的公共字符,因此值应该等于AB的子序列集合。
并且我们可以确定,如果两个字符串要比较的字符不一样,那么要填的格子是与其左边或上边有关,那边大就取那个。
如果比较的字符一样呢,稍安毋躁,刚好X的C要与Y的C进行比较,即ABC的子序列集合{"",A,B,C,AB,BC,ABC}与BDC的子序列集合{"",B,D,C,BD,DC,BDC}比较,得到公共子串有“”,B,D 。这时还是与之前的结论一样,当字符相等时,它对应的格子值等于左边与右边与左上角的值,并且左边,上边,左上边总是相等的。这些奥秘需要更严格的数学知识来论证。
我们现在用下面的方程来继续填表了。
程序实现
LCS可以进一步简化,只要通过挪位置,省去新数组的生成。
打印一个LCS
我们再给出打印函数,先看如何打印一个。我们从右下角开始寻找,一直找到最上一行终止。因此目标字符串的构建是倒序。为了避免使用stringBuffer这样麻烦的中间量,我们可以通过递归实现,每次执行程序时,只返回一个字符串,没有则返回一个空字符串, 以 printLCS(x,y,...)+str[i]相加,就可以得到我们要求的字符串。
我们再写出一个方法,来验证我们得到的字符串是否真正的LCS字符串。作为一个已经工作的人,不能写的代码像在校生那样,不做单元测试就放到线上让别人踩坑。
使用:
打印全部LCS
思路与上面差不多,我们注意一下,在LCS方法有一个Math.max取值,这其实是整合了三种情况,因此可以分叉出三个字符串。我们的方法将返回一个es6集合对象,方便自动去掉。然后每次都用新的集合合并旧的集合的字任串。
使用:
空间优化
使用滚动数组:
危险的递归解法
str1的一个子序列相应于下标序列{1, 2, …, m}的一个子序列,因此,str1共有${2^m}$个不同子序列(str2亦如此,如为${2^n}$),因此复杂度达到惊人的指数时间(${2^m * 2^n}$)。
原文发布时间为:2018-07-23
本文作者:Kaelan Cooter
本文来自云栖社区合作伙伴“前端大学”,了解相关信息可以关注“前端大学”
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
前端一站式异常捕获方案(全)
一、前端异常监控的重要性 软件异常监控常常直接关联到软件本身的质量,完备的异常监控体系常常能够快速定位到软件运行中发生的问题,并能帮助我们快速定位问题的源头,提升软件质量。 在服务器开发中,我们常常使用日志来记录请求的错误和服务器异常问题,但是在前端开发中,前端工程师按照需求完成页面开发,通过产品体验确认和测试,页面就可以上线了。但不幸的是,产品很快就收到了用户的投诉。用户反映页面点击按钮没反应而且能复现,我们试了一下却一切正常,于是追问用户所用的环境,最后结论是用户使用了一个非常小众的浏览器打开页面,因为该浏览器不支持某个特性,因此页面报错,整个页面停止响应。在这种情况下,用户反馈的投诉花掉了我们很多时间去定位问题,然而这并不是最可怕的,更让我们担忧的是更多的用户遇到这种场景后便会直接抛弃这个有问题的“垃圾产品”。这个问题唯一的解决办法就是在尽量少的用户遇到这样的场景时就把问题即时修复掉,保证尽量多的用户可以正常使用。 首先我们需要在少数用户使用产品出错时知道有用户出错,而且尽量定位到是什么错误。由于用户的运行环境是在浏览器端的,因此可以在前端页面脚本执行出错时将错误信息...
- 下一篇
Python NLP库top6的介绍和比较
文章来源:ActiveWizards https://medium.com/activewizards-machine-learning-company/comparison-of-top-6-python-nlp-libraries-c4ce160237eb 译者 | Revolver 编辑 | 磐石 出品 | 磐创AI技术团队 自然语言处理(NLP)在今天已经变得越来越流行,尤其是在深度学习迅猛发展的大背景下变得更加引人注目。NLP属于人工智能的一个领域,旨在理解文本和从中提取重要信息,并在文本数据上做进一步的训练。NLP的主要任务包括了语音识别和生成,文本分析,情感分析,机器翻译等。 现下已经有许多工具库被设计来解决NLP问题。今天,我们根据我们的经验列举概述了六个最实用最受欢迎的自然语言处理库,并对它们进行比较。不过我们列举的这几个库在功能上,在解决的任务目标上,只有部分的重叠,所以有时很难对它们进行直接比较。我们将围绕一些每个NLP库共有的特性来进行比较。 一、综述 NLTK (Natural Language Toolkit) 用于执行诸如分词,词形还原,词干提取,解析,词...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS关闭SELinux安全模块
- 2048小游戏-低调大师作品
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Red5直播服务器,属于Java语言的直播服务器
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS7,8上快速安装Gitea,搭建Git服务器
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7