期刊文献+
共找到103篇文章
< 1 2 6 >
每页显示 20 50 100
一种最长扩展公共子序列新算法
1
作者 王前东 《电讯技术》 北大核心 2024年第8期1307-1314,共8页
在最长填充公共子序列问题中提出一种新问题:假设有一个完整序列C和一个不完整序列Q,长度分别为m和n,Q中丢失的元素为相邻的相同元素,要求寻找一个丢失前的序列Q,使得C和Q具有最长的公共子序列。针对此问题,首先将Q中每个元素复制m-1个... 在最长填充公共子序列问题中提出一种新问题:假设有一个完整序列C和一个不完整序列Q,长度分别为m和n,Q中丢失的元素为相邻的相同元素,要求寻找一个丢失前的序列Q,使得C和Q具有最长的公共子序列。针对此问题,首先将Q中每个元素复制m-1个并插入Q中原来的位置,生成长度为mn的扩展序列Q^(*),然后证明了C和Q的最长扩展公共子序列是两序列C和Q^(*)的最长公共子序列,最后提出一种时空复杂度为O(mn)的最长扩展公共子序列求解新算法,并用轨迹实验证明了该算法对强噪声干扰和轨迹点丢失的同时有效性。 展开更多
关键词 最长公共序列(LCS) 最长填充公共序列(LFCS) 扩展公共序列(ECS) 最长扩展公共序列(LECS)
下载PDF
基于最长公共子序列的人体运动序列检索 被引量:2
2
作者 冯林 李璞 +1 位作者 孙焘 郑虎 《系统仿真学报》 CAS CSCD 北大核心 2009年第22期7164-7167,共4页
在计算机仿真领域,运用重新组合等相关技术,可以对已经捕捉的人体运动数据实现重用,以较低的成本产生新的运动。但是,由于运动库的数据庞大,对其实施有效检索成为一个重要问题。以倒排表数据结构为基础,设计出一套针对人体运动的检索算... 在计算机仿真领域,运用重新组合等相关技术,可以对已经捕捉的人体运动数据实现重用,以较低的成本产生新的运动。但是,由于运动库的数据庞大,对其实施有效检索成为一个重要问题。以倒排表数据结构为基础,设计出一套针对人体运动的检索算法。不同于传统的最长公共子序列(Longest Common Subsequence,LCSS)的度量算法,提出了一种限制最小匹配率ρmin的有限最长公共子序列(Limited-LCSS)算法,并在此基础上针对倒排表的数据结构特点对算法进行了优化,显著的提高了算法的效率。实验表明提出的检索方法具有较好的速度和准确性。 展开更多
关键词 运动捕捉 检索 最长公共序列 倒排表
下载PDF
结合Hausdorff距离和最长公共子序列的轨迹分类 被引量:26
3
作者 魏龙翔 何小海 +1 位作者 滕奇志 高明亮 《电子与信息学报》 EI CSCD 北大核心 2013年第4期784-790,共7页
为了提高运动目标轨迹分类的准确性,该文综合考虑了轨迹的位置信息和方向信息,提出了一种结合Hausdorff距离和最长公共子序列(Longest Common SubSequence,LCSS)的轨迹分类算法。该算法首先采用改进的Hausdorff距离对轨迹的位置信息进... 为了提高运动目标轨迹分类的准确性,该文综合考虑了轨迹的位置信息和方向信息,提出了一种结合Hausdorff距离和最长公共子序列(Longest Common SubSequence,LCSS)的轨迹分类算法。该算法首先采用改进的Hausdorff距离对轨迹的位置信息进行相似性测量,然后采用改进的LCSS算法对轨迹的方向信息进行相似性测量。与其他轨迹聚类算法不同,该算法融合了Hausdorff距离和LCSS两种算法的优点,提高了轨迹分类的准确性。此外,为了进一步降低计算复杂度,该文还实现了一种基于插值的保距变换算法和一种LCSS快速算法。实验结果表明,该轨迹分类算法可以明显提高轨迹的聚类准确率,聚类准确率可达到96%;基于插值的保距变换算法和LCSS快速算法可以很大程度上降低算法的计算复杂度,下降幅度最大可达到80%。该方法可以同时满足轨迹分类对精确度、实时性和鲁棒性的要求。 展开更多
关键词 图像处理 轨迹分类 HAUSDORFF距离 最长公共序列(LCSS) 保距变换 LCSS快速算法
下载PDF
带约束最长公共子序列快速算法 被引量:7
4
作者 业宁 朱大铭 +1 位作者 张倩倩 沈丽容 《南京大学学报(自然科学版)》 CAS CSCD 北大核心 2009年第5期576-584,共9页
带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为O(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2).运用对偶原理将带约束最长公共... 带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为O(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2).运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题,并建立带权的ref树结构,构造包含约束序列的约束覆盖子集,约简带约束覆盖子集并从中搜索关键路径,再通过关键路径构造CLCS,该算法将算法时间复杂度提升到O(nlogn+(q+r)L),r是约束序列的长度,q是两序列序偶的个数,L是两序列的最长公共子序列(LCS)长度. 展开更多
关键词 带约束最长公共序列 快速算法 对偶算法
下载PDF
基于滑动窗口最长公共子序列Wi-Fi指纹定位算法 被引量:3
5
作者 张明洋 陈剑 +1 位作者 闻英友 赵宏 《东北大学学报(自然科学版)》 EI CAS CSCD 北大核心 2014年第10期1390-1394,共5页
针对基于Wi-Fi瞬时指纹定位算法中由于RSS信号的时变特性引起的Wi-Fi定位精度差问题,提出了一种基于滑动窗口最长公共子序列指纹定位算法.该算法将时间序列的RSS信号指纹转化为基于滑动窗口的数据模型,增加了指纹特征信息,提高比对准确... 针对基于Wi-Fi瞬时指纹定位算法中由于RSS信号的时变特性引起的Wi-Fi定位精度差问题,提出了一种基于滑动窗口最长公共子序列指纹定位算法.该算法将时间序列的RSS信号指纹转化为基于滑动窗口的数据模型,增加了指纹特征信息,提高比对准确性.通过计算请求定位数据与样本的最长公共子序列来获得样本点的相似性,解决由于窗口伸缩或滑动窗口中个别采样点无信号引起的比对不准确问题,从而提高了定位的精确性和鲁棒性.实验结果表明,所提定位算法的结果明显优于瞬时指纹定位算法. 展开更多
关键词 室内定位 指纹 滑动窗口 时间序列 最长公共序列
下载PDF
最长公共子序列算法在程序代码相似度度量中的应用 被引量:7
6
作者 于海英 赵俊岚 《内蒙古大学学报(自然科学版)》 CAS CSCD 北大核心 2008年第2期225-229,共5页
阐述了最长公共子序列算法在程序代码结构相似度度量中的应用,列举了两种计算最优值和一种获取最长公共标识符子序列的算法.根据最优值得到结构相似度值,进而可以查找出结构相似程序对.最后探讨了程序代码相似度的实际应用.
关键词 最长公共序列算法 最优值 结构相似度 最长公共标识符子序列
下载PDF
基于最长公共子序列的非同步相似轨迹判断 被引量:11
7
作者 刘宇 王前东 《电讯技术》 北大核心 2017年第10期1165-1170,共6页
针对非同步相似轨迹判断问题,提出了一种基于最长公共子序列理论的相似轨迹判断新算法。首先,求出查询轨迹线段与候选轨迹线段之间的距离;其次,利用最长公共子序列算法,计算两轨迹的最长公共子轨迹长度;最后,根据相似度门限,判断轨迹是... 针对非同步相似轨迹判断问题,提出了一种基于最长公共子序列理论的相似轨迹判断新算法。首先,求出查询轨迹线段与候选轨迹线段之间的距离;其次,利用最长公共子序列算法,计算两轨迹的最长公共子轨迹长度;最后,根据相似度门限,判断轨迹是否相似。数值实例验证了所提算法能够提高非同步轨迹的相似度。 展开更多
关键词 侦察监视 最长公共序列 非同步相似轨迹 最长公共子轨迹
下载PDF
一种带匹配路径约束的最长公共子序列长度算法 被引量:9
8
作者 王前东 《电子与信息学报》 EI CSCD 北大核心 2017年第11期2615-2619,共5页
在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题,该文提出一种带匹配路径约束的最长公... 在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题,该文提出一种带匹配路径约束的最长公共子序列算法。首先定义带匹配路径约束的最长公共子序列模型,其次推出该序列的性质,最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法。基础算法和快速算法时间复杂度分别为O(mnt)和O(mn),m,n,t分别为序列Q,C,I的长度。 展开更多
关键词 最长公共序列 匹配路径约束 带约束的最长公共序列 带匹配路径约束的最长公共序列
下载PDF
基于格代数的最长公共子序列近似求解 被引量:2
9
作者 孙焘 朱晓明 《计算机科学》 CSCD 北大核心 2017年第2期270-274,共5页
多条序列的最长公共子序列可以代表多条序列的公共信息,其在诸多领域里有着重要的应用,如信息检索、基因序列匹配等。求解多条序列的最长公共子序列是著名的NP难问题,本质为多解问题。一些近似算法虽然时间复杂度较低,但只能求出单解,... 多条序列的最长公共子序列可以代表多条序列的公共信息,其在诸多领域里有着重要的应用,如信息检索、基因序列匹配等。求解多条序列的最长公共子序列是著名的NP难问题,本质为多解问题。一些近似算法虽然时间复杂度较低,但只能求出单解,对于有多解的序列集合,求得的结果信息量损失较大。因此提出一个新的近似算法来解决最长公共子序列问题。算法引入了代数结构"格",通过动态规划求解出两条序列的公共格,并递归求解当前格与当前序列的公共格。公共格中的路径保存了多条公共子序列使得最终求解出的最长公共子序列为多个。对算法的相关定理给出了理论证明,并通过实验验证了算法的正确性。 展开更多
关键词 最长公共序列 近似算法 贪心算法
下载PDF
基于最长公共子序列的随机路径选择算法设计 被引量:2
10
作者 王防修 周康 《计算机工程与设计》 CSCD 北大核心 2014年第6期2170-2173,共4页
针对传统算法只能求出一个最长公共子序列而无法求出多个最长公共子序列,设计了一种可求多个最长公共子序列的算法。简述了最长公共子序列的算法原理,描述了求最长公共子序列长度的动态规划算法,在此基础上求出一个最长公共子序列,通过... 针对传统算法只能求出一个最长公共子序列而无法求出多个最长公共子序列,设计了一种可求多个最长公共子序列的算法。简述了最长公共子序列的算法原理,描述了求最长公共子序列长度的动态规划算法,在此基础上求出一个最长公共子序列,通过对算法改进得到可求多个最长公共子序列的随机路径选择算法。该算法具有计算速度快、占用内存小、计算机易于实现等优点。其核心是寻优路径的选择,提出了寻找最优解的路径选择问题,讨论并给出了搜索多个可行解的快速算法,该算法充分利用了动态规划算法计算过程中提供的寻优方向信息得到最优路径的随机选择算法,与传统算法相比可求多个最长公共子序列。 展开更多
关键词 最长公共序列 最优子结构 动态规划 随机路径选择 最优解
下载PDF
基于状态压缩的最长公共上升子序列快速算法 被引量:2
11
作者 郭冬梅 《计算机技术与发展》 2014年第5期40-43,共4页
探讨了最长公共上升子序列(LCIS)问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列(LCS)和最长上升子序列(LIS)相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计... 探讨了最长公共上升子序列(LCIS)问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列(LCS)和最长上升子序列(LIS)相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O(mn)、空间复杂度为O(m)或O(n)的基于状态压缩的快速LCIS算法。 展开更多
关键词 最长公共上升子序列 最长公共序列 最长上升子序列 动态规划 状态压缩
下载PDF
最长公共子序列算法的分析与实现 被引量:8
12
作者 郑翠玲 《武夷学院学报》 2010年第2期44-48,共5页
本文首先分析最长公共子序列的特点,利用动态规划法求出最长公共子序列的长度数组和状态数组并通过矩阵搜索求出所有有效的跳跃点,构造了求解所有最长公共子序列的算法并通过程序给予实现。算法能有效避免重复搜索,时间效率大大提高,特... 本文首先分析最长公共子序列的特点,利用动态规划法求出最长公共子序列的长度数组和状态数组并通过矩阵搜索求出所有有效的跳跃点,构造了求解所有最长公共子序列的算法并通过程序给予实现。算法能有效避免重复搜索,时间效率大大提高,特别适用于基因工程中的基因片段分析。 展开更多
关键词 最长公共序列 动态规划法 矩阵搜索
下载PDF
最长公共子序列算法在文字录入测试中的应用 被引量:2
13
作者 贾志先 《计算机与现代化》 2007年第1期112-114,共3页
测试Word中的文字录入内容,是开发Office等考试软件过程中的一个关键技术问题。常用的处理方法是关键字检测法。通过检测Word文件中的关键字,可以测试出考生操作的大概结果,但是很不准确。利用最长公共子序列算法进行文字录入测试,可以... 测试Word中的文字录入内容,是开发Office等考试软件过程中的一个关键技术问题。常用的处理方法是关键字检测法。通过检测Word文件中的关键字,可以测试出考生操作的大概结果,但是很不准确。利用最长公共子序列算法进行文字录入测试,可以很好地解决这一问题。 展开更多
关键词 最长公共序列算法 文字录入测试 关键字检测
下载PDF
基于分层匹配和最长公共子序列的SCD文件比较算法
14
作者 徐睿 陈宏君 +2 位作者 张磊 周磊 文继锋 《计算机系统应用》 2016年第12期176-181,共6页
IEC61850通信已经在电力系统中广泛使用,其中变电站通信系统使用SCD文件进行描述.SCD文件是XML格式的层次化结构,不适合直接用文本按行对比来分析差异.同时由于SCD文件层次结构多,使用纯结构化的比较方法,会导致比较结果冗长,执行效率低... IEC61850通信已经在电力系统中广泛使用,其中变电站通信系统使用SCD文件进行描述.SCD文件是XML格式的层次化结构,不适合直接用文本按行对比来分析差异.同时由于SCD文件层次结构多,使用纯结构化的比较方法,会导致比较结果冗长,执行效率低.本文基于SCD文件的特征,提出了分层匹配的半结构化半文本比较思路.先按照智能电子设备、连接接入点、逻辑设备等层次结构,提取关键属性名,进行对齐匹配.之后在逻辑设备范围内,针对逻辑节点的内容,采用最长公共子序列的匹配算法对比局部文本内容,该算法可去除仅调整顺序不影响实体内容的无效差异,比较速度快,比较结果准确直观. 展开更多
关键词 IEC61850 SCD/ICD文件 层次比较 最长公共序列
下载PDF
算法分析与设计课程中最长公共子序列问题的教学探讨
15
作者 刘文强 周波 +2 位作者 桑海涛 顾泽元 韩娜 《中国教育技术装备》 2014年第24期109-111,共3页
介绍算法分析与设计课程中最长公共子序列问题的动态规划算法,利用该算法解决最长递减子序列问题和回文词的构造问题,通过这两个问题的求解,有助于学生举一反三,启发学生思维,以学致用,提高问题求解能力。
关键词 最长公共序列 动态规划 递减子序列 回文词
下载PDF
最长公共子序列问题的改进快速算法 被引量:9
16
作者 李欣 舒风笛 《计算机应用研究》 CSCD 2000年第2期28-30,共3页
现在几个最常用的解决最长公共子序列(LCS)问题的算法的时间复杂度分别是O(pn),O(n(m-p)).这里m、n两个待比较字符串的长度,p是最长公共子串的长度.给出一种时间复杂度为O(p(m-p));空间复杂度为O(... 现在几个最常用的解决最长公共子序列(LCS)问题的算法的时间复杂度分别是O(pn),O(n(m-p)).这里m、n两个待比较字符串的长度,p是最长公共子串的长度.给出一种时间复杂度为O(p(m-p));空间复杂度为O(m+n)的算法.与以前的算法相比;不管在p<<m的情况下,还是在p接近m时,这种算法都有更快的速度. 展开更多
关键词 最长公共序列 算法 差分压缩算法 字符串
下载PDF
采用改进最长公共子序列的人名消歧 被引量:5
17
作者 林翠萍 吴扬扬 《华侨大学学报(自然科学版)》 CAS 北大核心 2016年第2期201-206,共6页
将名词、形容词、动名词和命名实体作为文本特征,考虑词序与词频,结合特征项的语义,提出一种基于改进最长公共子序列的文本聚类(LCSC)方法.实验结果表明:相对于传统的余弦值聚类方法,LCSC方法在人名消歧的P-IP指标上,F平均值由74.2%提... 将名词、形容词、动名词和命名实体作为文本特征,考虑词序与词频,结合特征项的语义,提出一种基于改进最长公共子序列的文本聚类(LCSC)方法.实验结果表明:相对于传统的余弦值聚类方法,LCSC方法在人名消歧的P-IP指标上,F平均值由74.2%提高到了84.9%;相对于最长公共子序列方法,总体性能也提高了3.7%. 展开更多
关键词 人名消歧 文本相似度 最长公共序列 层次聚类
下载PDF
最长公共子序列的量子算法 被引量:3
18
作者 徐文旭 廖明宏 《电子学报》 EI CAS CSCD 北大核心 2007年第B12期99-103,共5页
本文给出了求给定两个序列最长公共子序列(Longest Common Subsequence,LCS)问题的量子算法,能在O(n)时间内求解两个长为n字符序列的最长公共子序列.算法在分析传统动态规划填表过程潜在并行性的基础上,对填表过程进行量子化,... 本文给出了求给定两个序列最长公共子序列(Longest Common Subsequence,LCS)问题的量子算法,能在O(n)时间内求解两个长为n字符序列的最长公共子序列.算法在分析传统动态规划填表过程潜在并行性的基础上,对填表过程进行量子化,并通过带有量子存储器的量子Oracle,完成量子并行填表的计算.算法最后对前面计算获得的所有局部LCS的均匀叠加态应用Grover搜索,找出最终解,相对于经典动态规划实现了二次加速. 展开更多
关键词 量子算法 最长公共序列 量子Oracle
下载PDF
求解最长循环公共子序列问题的两个算法 被引量:2
19
作者 郑子君 王洪 余成 《计算机应用研究》 CSCD 北大核心 2020年第11期3334-3337,3358,共5页
最长循环公共子序列(LCCS)是两个字符串在所有可能的循环移位操作下能得到的最长公共子序列(LCS)。针对穷举移位量求解LCCS效率过低的问题,设法对候选移位量进行筛选。通过证明循环移位操作对两字符串间LCS长度增量影响的上下限,得到最... 最长循环公共子序列(LCCS)是两个字符串在所有可能的循环移位操作下能得到的最长公共子序列(LCS)。针对穷举移位量求解LCCS效率过低的问题,设法对候选移位量进行筛选。通过证明循环移位操作对两字符串间LCS长度增量影响的上下限,得到最优移位量的必要条件,从而减小了求解LCCS的枚举量;在此基础上,建立了求解LCCS的迭代方法,只经过少数几次迭代便可消除绝大部分无效候选移位量;此外,还提出一个可在O(mn)时间复杂度下快速估算LCCS长度的近似算法。大量随机模拟表明,当两字符串间的相似度明显高于随机字符串的相似度时,提出的两种算法表现良好。 展开更多
关键词 最长公共序列 循环字符串 文本相似度 动态规划
下载PDF
求最长公共子序列长度的一个新方法 被引量:1
20
作者 林清波 吴锤红 《福建农业大学学报》 CSCD 1998年第4期505-509,共5页
提出了一个求序列X最长单调子序列的方法,若X的长度为n,则此方法所需时间为O(nlogn),空间占用为O(n).利用该方法可有效地求出X,Y两序列最长公共子序列的长度.如果X的长度为m,Y的长度为n,此时空间占用为O... 提出了一个求序列X最长单调子序列的方法,若X的长度为n,则此方法所需时间为O(nlogn),空间占用为O(n).利用该方法可有效地求出X,Y两序列最长公共子序列的长度.如果X的长度为m,Y的长度为n,此时空间占用为O(m+n);若Y中的各个元素在X中平均重复出现至多常数次,则所需时间为O(m+nlogn).作为应用之一,该方法可以用于文本的比较、等级考试录入文本的评测等. 展开更多
关键词 最长单调子序列 最长公共序列 动态选择树
下载PDF
上一页 1 2 6 下一页 到第
使用帮助 返回顶部