共查询到19条相似文献,搜索用时 62 毫秒
1.
基于Trie树的相似字符串查找算法是利用编辑距离的阈值来计算每个节点的活跃节点集,已有算法由于存在大量的冗余计算,导致时间复杂度和空间复杂度都比较高。针对这个问题,采用了基于活跃节点的对称性和动态规划算法的思想对已有算法进行改进,并对活跃节点集进行了修剪,提出了New-Trie-Stack算法。该算法避免了活跃节点的重复计算,以及已有算法在保存所有已遍历节点的活跃节点集时的空间开销。实验结果表明New-Trie-Stack算法在时间复杂度和空间复杂度上都有明显的下降。 相似文献
2.
DNA序列中基于适应性后缀树的重复体识别算法 总被引:1,自引:0,他引:1
现有的在DNA序列中识别重复体的算法多数是基于比对的,对识别速度和吞吐量有很大的限制.针对这个问题文中根据一个平衡重复体的长度和频率的定义,提出了一种基于Ukkonen后缀树的快速识别重复体的RepSeeker算法.算法采用最低限制频率,最大程度地扩展了重复体的长度,同时为了进一步地提高RepSeeker算法的效率,对Ukkonen的后缀树构造算法进行了适应性改进,在构造时加入RepSeeker算法所需的结点信息并将叶子结点和分支结点加以区分,从而使得RepSeeker算法能通过直接读取结点信息来求得子串频率和子串位置.这种改进较大地提高了RepSeeker算法的性能,而且空间开销不大.实验中使用了NCBI中的9条典型DNA序列作为测试数据,并对后缀树改进前后的重复体识别算法做了比较分析.结果表明,RepSeeker在没有损失精度的情况下缩短了算法的运行时间.实验结果与理论上的分析一致. 相似文献
3.
《计算机科学与探索》2018,(1):120-133
字符串相似性查找问题主要包括两方面,基于阈值的字符串相似性查找以及top-k字符串相似性查找。目前处理基于阈值的字符串相似性查找问题的算法多是基于过滤-验证框架的。基于该框架提出了PBsearch算法,算法在过滤阶段首次加入One-Off条件过滤掉大量的无效匹配,并在验证阶段提出了一种新的验证算法MultiThreshold算法,大大减少了计算编辑距离的次数。在top-k字符串相似性查找问题方面,提出了两种基于分割思想的算法,Pb-topk算法和PbCount-topk算法。其中,Pb-topk算法采用差值递增的策略,减少了需处理的字符串数目;PbCount-topk算法采用匹配数目划分的策略,进一步缩小了候选集的规模。最后,通过在3个真实数据集上的实验结果,验证了提出算法的高效性。 相似文献
4.
最大积实例包括最大可能解释(MPE)和最大后验估计(MAP),它们是贝叶斯网络的基本问题.针对经典算法求最大积实例的时间复杂度高,提出新算法来求解该问题.该算法将求贝叶斯网络的最大积实例问题转变成一组一元一次方程,而一元一次方程很容易求解;通过临时表来缓存计算最大积概率时的中间结果,而这些临时表可以用来优化计算最大积实例而不需要过多的额外空间开销,并能够在贝叶斯查询之间共享.通过实验证实该算法计算贝叶斯网络实例时的高效性,在计算最大积实例时的有效性. 相似文献
5.
基于人在字符串匹配过程中常用的思维,提出一种从模式串中提取特殊字符和具有特殊结构的字符组成字符串,用数组或链表来表示这种字符串的结构,使得提取出来的字符能与目标串中相应位置的字符比较的算法。用以减少比较次数,提高匹配效率。 相似文献
6.
提出一种高效海量字符串集合的模式匹配算法。给出了字符串集合模式匹配的定义,模式的预处理,字符串集合的存储结构和匹配算法,并分析了算法的复杂性和正确性。该文算法具有很好的时间复杂性和空间复杂性,因此具有很好的应用前景。 相似文献
7.
8.
一种改进的字符串匹配算法 总被引:9,自引:0,他引:9
基于字符串匹配的检测方法是入侵检测系统中的一种重要方法。在分析了几种常见的字符串匹配算法(BF、KMP、BM、Sunday等)的基础上,提出了一种改进的字符串匹配算法——sundayNcw。该算法使每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配,并且匹配次数大大减少,从而提高了匹配效率。最后,分析了该算法的性能,并用具体的实验数据给出了几种匹配算法的测试结果。 相似文献
9.
傅建明 《计算机工程与应用》1999,35(2):63-64,95
文章首先分析了字符串分割中产生汉字分离的原因,并设计了两种分割算法:正向分割算法和反向分割算法,然后对这两个算法进行分析和比较,最后给出了算法的两种应用。 相似文献
10.
现有的字符串匹配算法按照模式串从左至右或从右至左的顺序匹配,都是直接进行比较,本文提出了一种可做特殊用途的字符串匹配算法——ZZL算法。对于频繁使用的要匹配的主串和模式串来说,ZZL算法的匹配速度会非常快。 相似文献
11.
ASS算法分析与改进 总被引:4,自引:0,他引:4
本文提出了一种新的排序方法--数轴分段排序算法,此方法彻底抛弃了传统排序算法对数据反复比较和交换两种操作,以数据值同空间的对应关系完成其排序过程。其排序运算量为O,达到了排序运算量的下限。 相似文献
12.
求平面点集最近点对的一个改进算法 总被引:3,自引:0,他引:3
文中对Preparata和Shamos在1985年提出的求平面点集最近点对的一个分治算法进行了改进,使原来 归并时最多需计处3n对点对的距离,改进的为最多只需计算2n 相似文献
13.
多段采样信号十分常见,对其进行信息融合能有效提高信号处理的精度,尤其适用于低信噪比、被测频率持续时间短的情况。为提高多段采样信号频率估计的精度和扩展已有方法的适用范围,给出一种多段分频等长信号融合方法。在该方法中,因各段信号的被测频率不等,故生成频域分析参数矩阵以实现同频化效果;因同频化后各段信号之间仍然相位不连续,故设计相位差补偿因子矩阵以达到相位连续信号的效果;因相位差补偿因子矩阵包含未知参数,故生成搜索频率序列以用于实际计算并得到具有特定形式的功率谱矩阵。为验证方法的正确性,给出了数学证明。针对多种应用环境状态进行了仿真实验,结果表明该方法具有普适性,抗噪性好,频率估计精度比现有方法有较大提高。 相似文献
14.
一种基于多段降频等长信号融合的频率估计方法 总被引:1,自引:0,他引:1
为了提高多段采样信号频率估计的精度和扩展已有方法的适用范围,本文提出一种多段降频等
长信号融合方法.该方法采用频域分析参数矩阵、相位差补偿因子矩阵、搜索频率序列等措施,以解决各段
信号之间被测频率不等、相位不连续等问题.给出了四项性质作为所提方法有效性的数学证明,并针对多种
应用环境状态进行了仿真实验.结果表明,本文方法普遍适用于多段降频等长信号,抗噪性好,频率估计精
度比现有方法有较大提高. 相似文献
15.
16.
多探头超声波车流检测器 总被引:3,自引:0,他引:3
本文介绍了利用超声波原理研制的“多探头超声波车流检测器”的设计思想、设备的功能、结构和优特点,该检测器可用于检测行驶中机动车的车高、车长、车辆大中小等各种参数。 相似文献
17.
目标规划法在预测控制滚动优化及在线辨识中的应用 总被引:5,自引:1,他引:4
针对有约束多目标多自由度预测控制问题,应用目标规划方法,提出了一种既适合于参数模型又适合于非参数模型的在线滚动优化策略,并且通过计算饥仿真研究,验证了该方法的有效性.然后,对于参数模型预测控制问题,提出了一种抗扰动的最小绝对值辨识算法.由于该辨识算法可用目标规划快速求解,因此可作为慢时变工业过程控制的在线辨识算法. 相似文献
18.
针对基于关键字的搜索引擎缺乏语义的问题,提出了一种面向专业领域的语义搜索引擎模型.以领域本体形式化描述为基础,构建本体语义框架,进而给出语义搜索模型.在模型中,以概念、概念-实例以及关键字等3种扩展特征项作为基础,对查询扩展算法和文档语义标注算法进行了研究,并且构建了语义索引,通过引入向量空间模型判定扩展检索词与语义文档的相似度.实验结果表明,该模型较传统模型较大提高了检索的查准率和查全率. 相似文献