并行后缀树的构造及查询算法

针对生物信息领域中传统后缀树构造算法在时间和空间上的限制,从结构并行的角度提出了一种新颖的、适用于生物信息学应用的并行后缀树结构和相应的构造算法·该算法首先将给定字符串分成若干连续的片段,并在各个处理机上分别构造这些片段的后缀树,形成了一种分布于多个处理机上的并行后缀树结构·该并行算法不仅大大缩短了后缀树的构造时间,而且避免了主存大小的限制·经分析,其性能优于现有的任何一种并行算法·在此基础上,提出了一种高效的基于这种并行后缀树的字符串匹配算法,解决了传统后缀树的基本查询问题·     

基于GPU的大规模基因片段并行匹配的方法

后缀树和后缀数组广泛用于生物信息学领域中,特别是通过启发式算法在对DNA基因片段进行匹配的阶段.本文提出了在GPU的平台下,利用多核和超多核体系构成的后缀树以及后缀数组并行匹配大规模基因片段,从而加速基因搜索匹配过程.相对于后缀树,后缀数组二分搜素算法具有内存占用少,缓存使用率高等优点.在GPU的性能评估中,后缀数组执行效率明显超过后缀树,后缀数组占用的空间仅为后缀树的20%~30%.相对于CPU的串行实现,后缀树组达到了约99倍的加速比.实验结果表明在基因片段匹配的过程中,基于GPU的后缀数组二分搜索是一种高效且实用的方法.     

基于后缀树的图像识别研究

分析了后缀树在一维和二维字符串处理方面的优势．以后缀树为索引，将后缀树和最低公共祖先问题相结合，提出了一个在仅考虑平移变换操作的条件下．进行图像精确识别的算法，并从时间复杂度上证明了其优于传统的二：维精确模式匹配算法。     

基于改进后缀树算法中英文聚类引擎的实现

提出一种基于改进后缀树与交互聚类思想相结合的算法ISTC算法, 通过改造传统后缀树结构实现了对文档标题和摘要的层次化聚类, 同时用交互聚类的方式替代了传统的递归算法. ISTC算法具有语言无关性, 不仅适用于基于单词的西方文字, 而且可以在不引入词典分词技术的情况下有效地处理基于单字的中文字符. 在此算法基础上, 设计并实现了基于改进后缀树算法的交互聚类引擎, 在不同的网络环境下对其 进行了系统测试, 并与其他元搜索引擎进行了对比. 实验结果表明, 使用改进后缀树算法进 行实时交互式聚类是可行的.     

一种时序数据局部相关对象聚类算法

针对高维时序数据中局部相关模式的聚类问题,建立了一种基于相关子模式的spCluster模型,讨论了该模型与平均平方残值的关系.并以此模型为基础,提出了适用于时序数据的确定性双聚类算法sp-TSC,该算法首先利用spCluster模型将局部相关的数据对象符号化,然后将字符序列插入到泛化后缀树中,利用后缀树的性质避免了穷举局部相关子模式的各种组合,有效减小了搜索空间,从而可以在数据矩阵尺寸的线性时间内发现全部最大δ-spCluster.理论分析和实验表明,该算法是高效可行的.     

基于后缀树思想构造Web生物数据搜索的数据模型

针对Web上的公共生物学数据资源,提出一种适合于在线搜索生物学数据的数据模型.该模型基于后缀树思想,通过建立生物体的DNA、RNA、蛋白质序列数据的后缀树结构,并将之转化为更加空间有效的后缀数组,然后搜索数组以找到查询序列的近似匹配.结果表明,这种数据模型比常规的线性搜索模型在时间和空间开销上更加高效.     

基于后缀树的网页聚类算法性能改善研究

网页聚类技术是快速定位搜索引擎返回结果中用户最需要资料的方法。基于后缀树聚类算法是利用网页集中共享的短语来对网页集进行聚类。本文研究怎样充分利用后缀中的共享短语之间的关系提高后缀树性能的方法。     

XML路径表达式中公共子查询的优化技术

研究了XML路径表达式的相关查询算法,提出了基于标注后缀树的XML路径表达式公共子查询的优化算法,通过冗余消除技术来提高路径表达式的查询效率·在REOA测试集上,通过对设计的查询进行测试,分析了基于标注后缀树的XML路径表达式公共子查询的优化算法的性能·实验结果表明,基于标注后缀树的XML路径表达式冗余消除技术可以极大地提高路径表达式的查询效率·     

大型音乐哼唱检索系统中的近似匹配算法及性能评测

研究了大型音乐哼唱检索系统中采用的近似匹配算法的性能问题,为了支持对于多种近似匹配算法的比较研究,开发了一个独立于算法的测试平台.所研究的基本算法包括后缀树、隐马尔科夫模型(HMM)、编辑距离、动态时间规整(DTW)和单侧连续匹配(OSCM)方法,用于测试的音乐数据库包括72 000首音乐片段.通过构造1 500个不同类型错误的查询方法,对其中3类方法算法进行了大量实验,分析评价了它们的性能.实验结果表明,基于单侧连续匹配的算法不仅查询速度快,而且在用户哼唱只包含与旋律轮廓方向相同的错误时,查询的准确率是100%,在用户哼唱包含两个以内与旋律轮廓方向相反的错误时,前10位的命中率也在90%左右,是适用于大型哼唱检索系统的查询算法.图11,表1,参8.     

基于BM算法的匹配算法的改进

对SNORT的原有规则匹配算法BM算法改进,利用规则树实现了BM算法的多模式匹配功能,在跳跃方面主要依靠于最短模式串与规则树首字符重复出现间隔距离双重控制,在首字符不匹配的情况下,移动模式串的最大距离就是前缀树中最短模式串长度,在整个匹配过程中,最大移动距离是由该前缀树中最短模式串的长度决定;而首字符匹配时,最大移动距离是由规则树首字符重复出现间隔距离决定。