检索结果-南通市图书馆

一种带匹配路径约束的最长公共子序列长度算法

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

电子与信息学报 2017年第11期39卷 2615-2619页

作者：王前东中国电子科技集团公司第十研究所成都610036

在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题,该文提出一种带匹配路径约束的最长公... 详细信息

在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题,该文提出一种带匹配路径约束的最长公共子序列算法。首先定义带匹配路径约束的最长公共子序列模型,其次推出该序列的性质,最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法。基础算法和快速算法时间复杂度分别为O(mnt)和O(mn),m,n,t分别为序列Q,C,I的长度。

关键词：最长公共子序列匹配路径约束带约束的最长公共子序列带匹配路径约束的最长公共子序列

基于滑动窗口最长公共子序列Wi-Fi指纹定位算法

在线全文

学校读者我要写书评

暂无评论

东北大学学报（自然科学版） 2014年第10期35卷 1390-1394页

作者：张明洋陈剑闻英友赵宏东北大学信息科学与工程学院辽宁沈阳110819 东北大学医学影像计算教育部重点实验室辽宁沈阳110819

针对基于Wi-Fi瞬时指纹定位算法中由于RSS信号的时变特性引起的Wi-Fi定位精度差问题,提出了一种基于滑动窗口最长公共子序列指纹定位算法.该算法将时间序列的RSS信号指纹转化为基于滑动窗口的数据模型,增加了指纹特征信息,提高比对准确... 详细信息

针对基于Wi-Fi瞬时指纹定位算法中由于RSS信号的时变特性引起的Wi-Fi定位精度差问题,提出了一种基于滑动窗口最长公共子序列指纹定位算法.该算法将时间序列的RSS信号指纹转化为基于滑动窗口的数据模型,增加了指纹特征信息,提高比对准确性.通过计算请求定位数据与样本的最长公共子序列来获得样本点的相似性,解决由于窗口伸缩或滑动窗口中个别采样点无信号引起的比对不准确问题,从而提高了定位的精确性和鲁棒性.实验结果表明,所提定位算法的结果明显优于瞬时指纹定位算法.

关键词：室内定位指纹滑动窗口时间序列最长公共子序列

在线全文

学校读者我要写书评

暂无评论

最长公共子序列查询算法研究

最长公共子序列查询算法研究

作者：翟璐莎燕山大学

学位级别：硕士

最长公共子序列问题是计算机科学领域的一个经典问题,用于返回多个序列的最长公共子序列,简称为MLCS。MLCS问题在基因检测、序列相似性比对、模式识别、数据挖掘、代码克隆检测、文献查重、网页聚类等领域有着重要应用。目前求解MLCS问... 详细信息

最长公共子序列问题是计算机科学领域的一个经典问题,用于返回多个序列的最长公共子序列,简称为MLCS。MLCS问题在基因检测、序列相似性比对、模式识别、数据挖掘、代码克隆检测、文献查重、网页聚类等领域有着重要应用。目前求解MLCS问题通常采用基于动态规划的算法和基于匹配点的算法。随着字符序列数量和长度的增长,已有算法从效率和扩展性的角度不能满足实际需求。本文针对MLCS问题进行研究,研究内容如下。首先,提出一种基于单哈希的最长公共子序列算法SFLCS,该算法首先按序列中字符间后继关系生成每个序列的后继表,进而用有向无环图表示所有序列的后继表。在此基础上,通过哈希的方式快速存取字符间的后继关系。和已有方法采用双哈希来记录前驱及后继的方式相比,本文提出的单哈希方法在提升效率的同时,降低了所用内存空间。其次,针对单哈希方法空间代价高,无法处理长序列的问题,提出一种基于分治策略的最长公共子序列算法DCLCS算法。基于表示所有序列后继表的有向无环图,DCLCS算法首先预处理生成基于前preevel层匹配顶点的子图,然后对该子图中所有出度为零的顶点逐一处理,在处理每个顶点时,删除前一个被处理顶点所占用空间,从而降低了系统的空间代价,可以处理更长的序列。并在此基础上提出了top-k最长公共子序列的概念,设计和实现相应的算法来求解给定的n个序列中,所有k个序列的最长公共子序列中最长的公共子序列。最后,基于真实数据集进行实验,验证了本文算法的高效性。

关键词：最长公共子序列分治划分单哈希 top-k

基于教学目标分类法的算法设计与分析课程思政教学方案设计——以“最长公共子序列问题”为例

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

公关世界 2022年第2期 43-44页

作者：周晓宁陆召瑞吴予萌南京航空航天大学金城学院信息工程学院

针对如何提高算法设计与分析课程的育人功能,提出基于教学目标分类法的课程思政教学设计方案,进行教学研究。阐述了算法设计与分析课程的教学目标、教学实施方案以及教学效果评价方法,并以"最长公共子序列问题"为例,探讨教学方案设计的... 详细信息

针对如何提高算法设计与分析课程的育人功能,提出基于教学目标分类法的课程思政教学设计方案,进行教学研究。阐述了算法设计与分析课程的教学目标、教学实施方案以及教学效果评价方法,并以"最长公共子序列问题"为例,探讨教学方案设计的合理性和可行性。

关键词：算法设计与分析教学研究教学目标分类法课程思政最长公共子序列

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

基于格代数的最长公共子序列近似求解

计算机科学 2017年第2期44卷 270-274页

作者：孙焘朱晓明大连理工大学创新创业学院辽宁116024

多条序列的最长公共子序列可以代表多条序列的公共信息,其在诸多领域里有着重要的应用,如信息检索、基因序列匹配等。求解多条序列的最长公共子序列是著名的NP难问题,本质为多解问题。一些近似算法虽然时间复杂度较低,但只能求出单解,... 详细信息

多条序列的最长公共子序列可以代表多条序列的公共信息,其在诸多领域里有着重要的应用,如信息检索、基因序列匹配等。求解多条序列的最长公共子序列是著名的NP难问题,本质为多解问题。一些近似算法虽然时间复杂度较低,但只能求出单解,对于有多解的序列集合,求得的结果信息量损失较大。因此提出一个新的近似算法来解决最长公共子序列问题。算法引入了代数结构"格",通过动态规划求解出两条序列的公共格,并递归求解当前格与当前序列的公共格。公共格中的路径保存了多条公共子序列使得最终求解出的最长公共子序列为多个。对算法的相关定理给出了理论证明,并通过实验验证了算法的正确性。

关键词：最长公共子序列格近似算法贪心算法

在线全文

学校读者我要写书评

暂无评论

基于最长公共子序列的随机路径选择算法设计

计算机工程与设计 2014年第6期35卷 2170-2173页

作者：王防修周康武汉轻工大学数学与计算机学院湖北武汉430023

针对传统算法只能求出一个最长公共子序列而无法求出多个最长公共子序列,设计了一种可求多个最长公共子序列的算法。简述了最长公共子序列的算法原理,描述了求最长公共子序列长度的动态规划算法,在此基础上求出一个最长公共子序列,通过... 详细信息

针对传统算法只能求出一个最长公共子序列而无法求出多个最长公共子序列,设计了一种可求多个最长公共子序列的算法。简述了最长公共子序列的算法原理,描述了求最长公共子序列长度的动态规划算法,在此基础上求出一个最长公共子序列,通过对算法改进得到可求多个最长公共子序列的随机路径选择算法。该算法具有计算速度快、占用内存小、计算机易于实现等优点。其核心是寻优路径的选择,提出了寻找最优解的路径选择问题,讨论并给出了搜索多个可行解的快速算法,该算法充分利用了动态规划算法计算过程中提供的寻优方向信息得到最优路径的随机选择算法,与传统算法相比可求多个最长公共子序列。

关键词：最长公共子序列最优子结构动态规划随机路径选择最优解

基于改进Fast-DTW的多维地磁序列匹配算法研究

在线全文

学校读者我要写书评

暂无评论

现代信息科技 2024年第8期8卷 89-92,96页

作者：姚霆宇余学祥韩雨辰朱平安徽理工大学空间信息与测绘工程学院安徽淮南232001 安徽理工大学矿山采动灾害空天地协同监测与预警安徽普通高校重点实验室安徽淮南232001 安徽理工大学矿区环境与灾害协同监测煤炭行业工程研究中心安徽淮南232001

传统单点的地磁匹配定位算法运算量大,且定位时效性及定位精度较差。针对该问题,采用基于序列的快速动态时间规整算法Fast-DTW实现多维的地磁序列匹配,并利用最长公共子序列LCS的有序聚类进行优化。离线阶段通过坐标转换法构建四维地磁... 详细信息

传统单点的地磁匹配定位算法运算量大,且定位时效性及定位精度较差。针对该问题,采用基于序列的快速动态时间规整算法Fast-DTW实现多维的地磁序列匹配,并利用最长公共子序列LCS的有序聚类进行优化。离线阶段通过坐标转换法构建四维地磁指纹库,在线阶段进行实时地磁序列匹配,获得定位结果。实验结果表明,该算法的定位时效性及精度均有提升。

关键词：地磁室内定位快速动态时间规整算法最长公共子序列地磁指纹库

在线全文

学校读者我要写书评

暂无评论

基于最长公共子序列的非同步相似轨迹判断

电讯技术 2017年第10期57卷 1165-1170页

作者：刘宇王前东中国西南电子技术研究所成都610036

针对非同步相似轨迹判断问题,提出了一种基于最长公共子序列理论的相似轨迹判断新算法。首先,求出查询轨迹线段与候选轨迹线段之间的距离;其次,利用最长公共子序列算法,计算两轨迹的最长公共子轨迹长度;最后,根据相似度门限,判断轨迹是... 详细信息

针对非同步相似轨迹判断问题,提出了一种基于最长公共子序列理论的相似轨迹判断新算法。首先,求出查询轨迹线段与候选轨迹线段之间的距离;其次,利用最长公共子序列算法,计算两轨迹的最长公共子轨迹长度;最后,根据相似度门限,判断轨迹是否相似。数值实例验证了所提算法能够提高非同步轨迹的相似度。

关键词：侦察监视最长公共子序列非同步相似轨迹最长公共子轨迹

在线全文

学校读者我要写书评

暂无评论

采用改进最长公共子序列的人名消歧

华侨大学学报（自然科学版） 2016年第2期37卷 201-206页

作者：林翠萍吴扬扬华侨大学计算机科学与技术学院福建厦门361021

将名词、形容词、动名词和命名实体作为文本特征,考虑词序与词频,结合特征项的语义,提出一种基于改进最长公共子序列的文本聚类(LCSC)方法.实验结果表明:相对于传统的余弦值聚类方法,LCSC方法在人名消歧的P-IP指标上,F平均值由74.2%提... 详细信息

将名词、形容词、动名词和命名实体作为文本特征,考虑词序与词频,结合特征项的语义,提出一种基于改进最长公共子序列的文本聚类(LCSC)方法.实验结果表明:相对于传统的余弦值聚类方法,LCSC方法在人名消歧的P-IP指标上,F平均值由74.2%提高到了84.9%;相对于最长公共子序列方法,总体性能也提高了3.7%.

关键词：人名消歧文本相似度最长公共子序列层次聚类