排序方式: 共有14条查询结果,搜索用时 0 毫秒
1.
2.
Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system. 相似文献
3.
4.
5.
对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法.已有的分组算法大都是启发式的或蛮力的,分组效果很差.分析了DFA状态膨胀的原因,总结了某些正则表达式间的冲突状况.证明了当冲突非负和冲突独立时,正则表达式集合的最优k分组问题可归结为最大k割问题,从而说明该问题是NP-Hard的.基于局部搜索的思想,提出了一种分组算法GRELS来解决分组问题,并证明对最大k割问题,该算法的近似比是1/(1-1/k)与已有的分组算法相比,当分组数目相同时,GRELS算法分组结果的状态总数最少,并且集合发生变化时所需的更新时间最短. 相似文献
6.
7.
经典的聚类分析技术如系统聚类法和K-means等主要是处理间隔尺度的变量,而对于名义尺度变量则不适合。文章借鉴认知心理学和优化学习的思想,对名义尺度变量的聚类问题进行了研究,定义了名义尺度变量的距离度量——翻转距离,在此基础上,提出了一种目标函数优化制导的聚类算法,并演示了对名义尺度变量进行聚类的过程。实验表明,我们的算法结果可以得到合理的解释。 相似文献
8.
蛋白质是由多个氨基酸残基顺序连接而成的长链.在天然状态下,蛋白质并不是无规则的自由状态,而是自发形成特定的空间结构,以执行其特定的生物学功能.驱动蛋白质形成特定空间结构的主要因素是残基间的非共价相互作用,包括疏水作用、静电相互作用、范德华力等.因此,对残基之间远程相互作用的准确预测将有助于对蛋白质空间结构的预测,进而有助于对蛋白质生物学功能的了解.在蛋白质进化过程,有相互作用残基对之间存在一种“共进化”模式,即当一个残基发生变异时,与其有相互作用的残基也要发生相应的变异,以维持相互作用,进而维持整体空间结构以及生物学功能.基于上述生物学观察,研究者开发了多个统计模型和算法以预测残基对之间的相互作用:1)概述残基之间远程相互作用的两大类基本预测算法,包括无监督学习方法和监督学习方法;2)使用蛋白质结构预测CASP比赛结果来客观比较上述各类算法的性能,分析各个算法的特点和优势;3)从生物学观察和统计模型2个角度分析总结了未来的发展趋势. 相似文献
9.
10.
3-SAT问题有一个非常奇妙的相变现象.对于固定的变量数N,合取范式的可满足概率随着子句个数K的变化而发生剧烈的变化;当K≈4.3*N 时,可满足概率急剧地从1变为0.相变现象决定了问题的难易分布,对于快速求解算法的设计有着非常重要的意义.文章着重讨论了SAT问题的更一般形式,即2-3-SAT问题的相变现象.研究了相变点处的2-子句和3-子句个数的关系,发现了2-子句和3-子句在约束能力意义下的当量关系,并提出了如何有效地利用2-3-SAT的相变现象. 相似文献