检索结果-南通市图书馆

基于最长公共子串挖掘的未知链路层协议帧切割算法

在线全文

学校读者我要写书评

暂无评论

计算机科学 2020年第7期47卷 227-230页

作者：陈庆超王韬冯文博尹世庄中国人民解放军陆军工程大学装备模拟训练中心石家庄050003 中国人民解放军陆军工程大学指挥控制工程学院南京210007

在日益激烈的现代电子对抗领域中,侦听方截获的原始数据一般是比特流的形式,将比特流划分为数据帧是处理截获数据的首要任务。现有方法虽然可以准确地提取相关序列实现帧切分,但是当需要处理的数据量较大时,时间和空间的消耗量过大,并... 详细信息

在日益激烈的现代电子对抗领域中,侦听方截获的原始数据一般是比特流的形式,将比特流划分为数据帧是处理截获数据的首要任务。现有方法虽然可以准确地提取相关序列实现帧切分,但是当需要处理的数据量较大时,时间和空间的消耗量过大,并且实验过程中常常需要预先设定一些阈值。为此,文中提出了一种基于最长公共子串挖掘的未知链路层协议帧切割算法,该算法通过统计一定长度的比特流的最长公共子串,逐步精确前导码和帧起始定界符,从而实现帧切分。实验数据表明,该算法相较于基于频繁序列挖掘以实现帧切分的算法,相关候选序列数量呈指数级下降,最终使得候选序列唯一。该算法的时间复杂度为O(n),且只需单次扫描,充分说明该算法可以高效地实现帧切分。

关键词：最长公共子串前导码帧起始定界符帧分割未知链路层协议

支持编辑距离约束的近似最长公共子串匹配及其优化算法

在线全文

学校读者我要写书评

暂无评论

支持编辑距离约束的近似最长公共子串匹配及其优化算法

作者：叶心东北大学

学位级别：硕士

目前许多信息都以文本的形式存放在计算机中,所以基于文本的信息检索技术,如最长公共子串匹配问题一直是文本管理、程序分析等领域的经典问题,长期以来受到广泛地关注与研究。然而最长公共子串的要求过于严格,在实际应用中,两个局部非... 详细信息

目前许多信息都以文本的形式存放在计算机中,所以基于文本的信息检索技术,如最长公共子串匹配问题一直是文本管理、程序分析等领域的经典问题,长期以来受到广泛地关注与研究。然而最长公共子串的要求过于严格,在实际应用中,两个局部非常相似的文本其中的公共部分往往不是完全精确匹配的,因此需要提供支持近似匹配的最长公共子串匹配方法。目前尚未有相关技术的报道。因此,本文重点研究支持编辑距离约束的近似最长公共子串匹配问题。本文首先综述了现有的字符串近似匹配技术,并基于此,提出了一种基于动态规划的算法,这个算法首先用最长公共子串的动态规划算法求出公共子串,再用编辑距离和最长公共子序列的动态规划方法,计算具有公共前缀的子串组成的比对区域,找到所有支持编辑距离约束的近似公共子串,最后进行长度验证找到支持编辑距离约束的近似最长公共子串。该算法可以保证O（kmn）的时间复杂度。为了进一步提高算法的效率,本文提出了基于后缀数组的公共子串匹配优化算法。该算法先采用后缀数组的方法求出所有公共子串,再将相邻连接距离不大于编辑距离阈的公共子串连接起来构造验证集,在构造验证集的过程中采用了基于公共子串位置和基于公共子串间距离的过滤策略,最后用启发式的方法在验证集中找出支持编辑距离约束的近似最长公共子串,提高了查询效率。最后,本文在三个不同的真实数据集上测试了这两种算法的性能,基于动态规划的算法,由于需要对所有具有相同前缀开始的比对区域进行动态规划计算,所以算法的性能比基于公共子串的查询算法差。实验发现,基于公共子串的算法由于采用了基于公共子串位置和公共子串间距离的过滤技术,所以该算法的性能跟两个串的公共子串的个数和长度有关系,如果公子串个数比较少,且长度都比较长,算法的性能越好。

关键词：近似匹配编辑距离动态规划后缀数组最长公共子串

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

求最长公共子串长度的算法

东南大学学报（自然科学版） 1998年第6期28卷 191-194页

作者：殷新春陈凌扬州大学师范学院

给出求２个字符串最长公共子串（ＬＣＳ）长度的递归算法、递推算法和心动阵列算法．对２个长度分别为ｎ，ｍ（ｎ≥ｍ）的字符串，递归算法的最坏时空复杂性为（ｍ＋ｎ）！／（ｍ！ｎ！），而递推算法的时空复杂性分别仅为ｍ＋ｎｍ＋Ｏ... 详细信息

给出求２个字符串最长公共子串（ＬＣＳ）长度的递归算法、递推算法和心动阵列算法．对２个长度分别为ｎ，ｍ（ｎ≥ｍ）的字符串，递归算法的最坏时空复杂性为（ｍ＋ｎ）！／（ｍ！ｎ！），而递推算法的时空复杂性分别仅为ｍ＋ｎｍ＋Ｏ（１），２ｍ＋Ｏ（１）．在心动阵列算法中，需ｍ个ＰＥ和ｎ＋ｍ的时间．最后给出了一个应用实例．

关键词：长度心动阵列算法分析最长公共子串递归算法递推算法字符串信号处理模式匹配

在线全文

学校读者我要写书评

暂无评论

求最长公共子串问题的算法分析

计算机仿真 2007年第12期24卷 97-100,116页

作者：张毅超车玫马骏中国航天科技集团公司第710研究所北京100037

高效求解2个字符串的最长公共子串(Longest Common Substring)是实现很多字符串算法的关键。文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树... 详细信息

高效求解2个字符串的最长公共子串(Longest Common Substring)是实现很多字符串算法的关键。文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树算法的时间复杂度较低,但实现较为复杂并且广义后缀树占用的空间也较多。最后提出了一个新算法,该算法使用2个字符串的广义后缀数组,在保持和广义后缀树时间复杂度相等的基础上,可以简单地实现并且占用较少的空间。

关键词：最长公共子串动态规划广义后缀树广义后缀数组

基于比对相似度动态矩阵聚类算法在基因序列中的应用

在线全文

学校读者我要写书评

暂无评论

计算机应用 2004年第8期24卷 35-37页

作者：张白妮骆嘉伟汤德佑湖南大学计算机与通信学院湖南长沙410082

基于BAG图的聚类算法 ,利用聚类单元引导类的分割 ,保证聚类结果不会产生过多的类碎片 ,但其相似分数阈值Cutoff初始值和最长公共子串最小长度阈值Threshold如何确定并没有明确给出。提出基于比对相似度动态矩阵的聚类算法 ,并在此基础... 详细信息

基于BAG图的聚类算法 ,利用聚类单元引导类的分割 ,保证聚类结果不会产生过多的类碎片 ,但其相似分数阈值Cutoff初始值和最长公共子串最小长度阈值Threshold如何确定并没有明确给出。提出基于比对相似度动态矩阵的聚类算法 ,并在此基础上明确给出了确定cutoff初始值和Threshold阈值的方法。实验结果表明该算法可以获得较好的聚类正确率。

关键词：生物序列聚类最长公共子串比对相似度动态矩阵

在线全文

学校读者我要写书评

暂无评论

一种基于DTW算法的磁场相似性度量方法

水下无人系统学报 2023年第3期31卷 430-435页

作者：胡家文刘忠乐文无敌张志强海军工程大学兵器工程学院湖北武汉430033

在舰船磁场模拟及磁探测系统的目标识别中,需要对模拟或探测磁场与真实目标磁场分布的相似程度进行评估。文中针对以往评估方法存在的问题,提出利用动态时间规整(DTW)算法计算磁场的相似度,解决了目标速度不同和起止点不一致情况下的磁... 详细信息

在舰船磁场模拟及磁探测系统的目标识别中,需要对模拟或探测磁场与真实目标磁场分布的相似程度进行评估。文中针对以往评估方法存在的问题,提出利用动态时间规整(DTW)算法计算磁场的相似度,解决了目标速度不同和起止点不一致情况下的磁场曲线相似度评估问题;为降低磁场曲线局部扰动带来的影响,利用最长公共子串对DTW算法进行了优化,提高了相似度计算精度;最后以模型试验验证了算法的正确性。与传统评估方法相比,该方法无需人工预先设置参数,能直接给出相似度评价结果,可应用于舰船磁场模拟效果评估及磁探测系统的目标识别。

关键词：舰船磁探测动态时间规整相似性度量磁场曲线最长公共子串

同方期刊数据库博看期刊评论

在线全文

学校读者我要写书评

暂无评论

最长公共子序列的快速算法及其并行实现

计算机应用 2006年第6期26卷 1422-1424,1427页

作者：刘维陈崚扬州大学信息工程学院江苏扬州225009

求生物序列的最长公共子串是生物信息学中最重要的问题之一,提出了该问题的一个快速算法,可对所有初始同字符对并行地寻找其后继同字符对,并记录下相应层次值。最后通过最大层次值回溯得到比对结果。此外,该算法采用了剪枝技术,对于明... 详细信息

求生物序列的最长公共子串是生物信息学中最重要的问题之一,提出了该问题的一个快速算法,可对所有初始同字符对并行地寻找其后继同字符对,并记录下相应层次值。最后通过最大层次值回溯得到比对结果。此外,该算法采用了剪枝技术,对于明显不能得出最优比对的同字符将中止其后继的搜索。实验结果证明,本文算法比其他算法速度快、精确度高。

关键词：生物信息学最长公共子串同字符对

基于序列比对检测的优化SRE多态蠕虫防御方法

在线全文

学校读者我要写书评

暂无评论

计算机工程与设计 2017年第9期38卷 2379-2384页

作者：赵荷赵海燕宁多彪谭良成都东软学院计算机科学与技术系四川成都611844 四川师范大学计算机学院四川成都610101

针对简化正则表达式(SRE)的多态蠕虫防御方法不足以处理蠕虫的不变部分和距离限制等问题,提出一种利用序列比对检测的优化SRE。比对一个序列在另一个序列上编写字符的过程包括3个步骤,即初始化步骤、矩阵填充和回溯步骤。初始化矩阵用... 详细信息

针对简化正则表达式(SRE)的多态蠕虫防御方法不足以处理蠕虫的不变部分和距离限制等问题,提出一种利用序列比对检测的优化SRE。比对一个序列在另一个序列上编写字符的过程包括3个步骤,即初始化步骤、矩阵填充和回溯步骤。初始化矩阵用于比较两个序列间字符的得分;填充矩阵选择最大数,保持指针指向导出参数的先前得分位置;回溯的每个分支代表一个最优的比对。考虑到上述步骤最大化了匹配总数量,而非匹配连续子串,采用逐对序列比对检测,对最长公共子串(LCS)的字符串进行匹配。评价结果表明,优化SRE方法能够成功获得连续序列,保留了多态蠕虫的所有通配符,相比于Autograph、Polygraph和SRE方法,其生成的特征码更加精确和高效。

关键词：多态蠕虫简化正则表达式匹配最长公共子串序列比对检测

在线全文

学校读者我要写书评

暂无评论

基于改进编辑距离的字符串相似度求解算法

计算机工程 2014年第1期40卷 222-227页

作者：姜华韩安琪王美佳王峥吴雲玲东北师范大学计算机科学与信息技术学院长春130117 东北师范大学智能信息处理吉林省高校重点实验室长春130117

编辑距离(LD)算法在求解两个字符串的相似问题时只考虑了编辑操作次数,未考虑字符串之间的公共子串对相似度的影响。为此,提出一种基于改进编辑距离的字符串相似度求解算法,对字符串相似度度量公式及Levenshtein矩阵计算方法进行改进。... 详细信息

编辑距离(LD)算法在求解两个字符串的相似问题时只考虑了编辑操作次数,未考虑字符串之间的公共子串对相似度的影响。为此,提出一种基于改进编辑距离的字符串相似度求解算法,对字符串相似度度量公式及Levenshtein矩阵计算方法进行改进。在计算编辑距离时,以原有矩阵求出两字符串的最长公共子串及所有LD回溯路径。选取一个单词作为源串,一组与源串不同程度相似的单词为目标串,将改进的相似度度量公式与现有的字符串相似度计算方法进行比较,改进公式减少了进入胜者表的目标串数,相似度的样本极差和标准差分别为0.331和0.150。实验结果表明,改进算法在不改变空间复杂度的情况下,计算字符串相似度的准确性更高,且查询方式更灵活。

关键词：编辑距离 LD算法回溯路径最长公共子串相似度模糊查询