一种分布式后缀树构造与匹配算法

提出一种基于消息传递模式的分布式后缀树构造算法(DPSTG)及相应的并行匹配算法.DPSTG算法按不同的字符将原始字符串的后缀树分解成若干个子后缀树后由多个处理器并行构造.处理器间通过消息传递方式连接各个子后缀树,匹配时首先将要查找的字符串分割成若干不同首字符的子字符串,然后在构造相应首字符子后缀树的处理器上实现多个子字符串的并行匹配.理论分析表明DPSTG算法的时间复杂度要优于现有的大多数后缀树并行生成算法.模拟实验结果表明DPSTG算法的并行加速比随着待处理字符串的长度增加而提高.     

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

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

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

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

基于线性浓密树的并行数据库查询优化算法

查询优化是并行数据库的核心技术。基于线性浓密树的查询优化方法是对基于浓密树(Bushy-Tree)查询优化方法的一种改进,这种优化方法大大地缩减了查询执行计划空间,确保了并行查询执行计划的优化性。     

借用外存构造后缀数组的优化算法

为一个巨大的文本集合构造后缀数组是目前搜索引擎领域中的一个热点问题．对已存在的后缀数组的外存构造算法加以优化．优化后的算法仍然遵循原有方法的基本原则,但采用不同的实现策略,保证了算法在最坏情况下的较好的时间复杂度。     

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

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

基于后缀树的基因数据可搜索加密方法

为保障用户免遭侵犯隐私的风险,提出了一种特别支持基因数据的可搜索加密方法.针对目前密文搜索方案大多数仅支持通过关键字进行搜索,而无法用于不含关键字的基因数据的问题,利用后缀树和伪随机函数等密码学原语构建安全索引,实现对密文基因数据的任意子字符串搜索.安全性证明该方法满足动态自适应安全,利用理论分析和真实数据对效率进行测评.该方法可以对基因数据进行高效安全的任意子字符串搜索,保护数据完整性和隐私性,在个性化医疗大众化的环境下具备广阔的应用前景.     

基于排序树的字符串集合快速匹配算法

字符串匹配是计算机科学研究的基础问题,主要研究在目标字符串中发现多特征字符串。其被广泛用于网络审计系统等其他实际工程中的应用中。目前,对于特征字符串集合匹配的问题的研究较少,在实际中也没有很理想的算法,因此在基于BM和AG算法研究的基础上,提出了一种基于排序树的快速匹配算法,通过与其它算法比较以及实验研究,表明本算法效率有了很大的提高。图6,参10。     

并行查询中的处理机分派算法研究

讨论了并行查询中丛生树的自顶向下和自底向上两类处理机分派算法和优点及其不足之处，在此基础上提出了一个新的处理机分派的调度算法，本算法可达到近似最优调度效果。     

后缀树算法在舆情聚类中的应用

针对网络舆情分析的需求背景,研究了通过后缀树算法发现文本文档之间的公共短语串,按公共短语串实现文档聚类。网页文档的标题和摘要能代表文档的主要思想,应用后缀树算法实现对标题和摘要自动聚类,从而实现舆情信息自动聚类。     

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

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

找K个最小生成树的并行算法

基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log~2n+Klogn~*)时间及O(n~2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n~2)处理器,这里n 是图的顶点数.     

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

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

改进的基于后缀树的Web搜索结果聚类算法

为提高Web 搜索精度和检准率, 在后缀树聚类算法基本模型的基础上, 提出了一种改进的基于后缀树的搜索结果聚类算法。将向量空间模型与后缀树聚类相结合, 改善了基类合并的效果, 综合基类节点对应文本数、短语包含词语长度、短语权重及是否包含查询词作为聚类标签的筛选条件, 改进了聚类标签的合理性和可读性。以搜狗语料库中的文本分类语料库为数据源进行的实验结果表明, 该方法在一定程度上提高了聚类结果的准确率。     

基于后缀数组的快速排序算法

在搜索技术和各种流行的排序算法优缺点比较的基础上,给出了一种基于后缀数组的新的快速排序算法,该算法在时间和空间性能上均优于传统的快速排序算法;并在同等的条件下,用该方法与快速排序算法对相同的内容进行排序,结果表明:该算法特别适用于大文本的排序问题,可用于搜索技术和数据压缩中.     

带记忆的Boyer-Moore型模式匹配算法及其复杂性分析

通过构建前缀匹配自动机,使得每轮匹配后下个匹配窗口的文本总是保持左端部分为模式的一个前缀、右端部分全为未比较过的字符的形式.对于与此相应的模式匹配算法,已证明文本内的每个字符在整个匹配过程中最多被比较一次,从而字符总比较次数不超过n,已达到任意算法最坏情况下字符总比较次数的最小值.另外,在适当条件下还从理论上证明了此算法的亚线性(即字符总比较次数小于cn,其中常数c＜1).根据实验结果,算法的实际运行速度快于Boyer-Moore算法.     

用于光线跟踪的高并行度表面积启发式(SAH)KD树构建

提出一种用于光线跟踪的SAH-KD树构建方法,解决当前KD树并行算法并行度不高且效率低的问题.算法首先对所有图元包围盒在三个维度按坐标轴左值排序,得到三维上有序的包围盒索引.然后使用层次遍历构建KD树,根据每个节点包围盒选择要划分的维度,并在当前层生成所有节点在该维度下的候选划分点序列.最后计算每个节点的空间树,在GPU中计算每个候选点的SAH值,选择每个节点的最小SAH值点进行划分.实验中采用4个常用场景进行测试算法性能,并同时比较了当前高效串行与并行算法,结果证明本文提出的算法在生成同等质量KD树的情况下达到对比串行方法4~6倍以及对比并行方法的1.3~1.5倍的计算速度,并且能在线程数成倍增加时达到相近倍数的加速比.