On-line linear time construction of sequential binary suffix trees

Suffix trees are the key data structure for text string matching, and are used in wide application areas such as bioinformatics and data compression. Ukkonen algorithm is deeply investigated and a new algorithm, which decreases the number of memory operations in construction and keeps the result tree sequential, is proposed. The experiment result shows that both the construction and the matching procedure are more efficient than Ukkonen algorithm.

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

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

基于并行子树构建的XML解析方法

XML解析的高耗时特点制约着XML应用系统整体性能的提高,并行化是一种重要的优化手段。现有的并行XML解析算法存在的问题是需要通过预处理进行数据划分,才能实现分片并行完全解析处理。预处理往往很耗时,若进行优化处理,则实现复杂。提出的方法可实现对XML数据任意分片直接进行解析,并行构建各个片断中的子树,再通过子树合并获得全局的文档树。实验结果表明该方法能有效利用多核计算环境,并行实现XML解析。

后缀树的并行构造算法

后缀树是一种非常重要的数据结构,它在与字符串处理相关的各种领域里有着非常广泛的应用。构造后缀树是应用后缀树解决问题的前提和关键。虽然很多现有的后缀树构造算法都是线性时间和空间的,但是,当被索引的字符串的长度很长时,构造其后缀树所消耗的时间和空间仍将非常巨大,这极大地限制了后缀树的实际应用。而并行技术是解决这一问题的很好途径,因此人们提出了后缀树的并行构造算法。本文对后缀树的三种并行构造算法进行了综述,通过系统的比较和分析,总结出当前存在的问题,并指明了下一步的研究方向。

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

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

高等教育自学考试试卷平行性及其评价维度初探

高等教育自学考试是一种典型的标准参照测验。试卷的平行性可以界定为相同专业下同一课程的不同试卷在形式、内容、功能和分数结果上的一致性和可比性，它对自学考试的科学性和有效性具有非常重要的意义。对自学考试试卷平行性的度量和控制，可以从试卷结构、题目内容、题目功能和结果数据四个方面进行。

基于Spark的序列数据质量评价

随着序列数据在实际中的广泛应用,序列数据质量评价成为学术、工业等众多领域的热门研究问题。目前主流的序列数据质量评价方法是基于概率后缀树模型进行数据质量评价,然而这种方法难以实现对大规模数据的处理。为解决此问题,提出了基于Spark的序列数据质量评价算法STALK(sequential data quality evaluation with Spark),并且采用了改进的剪枝策略来提高算法效率。具体地,在Spark平台下,利用大规模序列数据高效建立生成模型,并根据生成模型对查询序列的数据质量进行快速评价。最后通过真实序列数据集验证了STALK算法的有效性、执行效率和可扩展性。

基于负载均衡的模糊概念并行构造算法

提高模糊概念格直接构造效率是形式概念分析领域的主要问题之一,而当前基于模糊伽罗瓦联系的闭包运算仍是构造模糊概念的主要计算负荷,为此,提出一种基于负载均衡的并行构造模糊概念算法.该算法使用树状结构组织,遍历由自然数区间简化的搜索空间,逐级并行产生模糊概念、缩减搜索区间,并通过重新划分子搜索空间,实现各个计算节点负载均衡.实验结果表明,所提出的算法在稀疏数据集上表现优秀,能够有效地提高模糊概念构造效率.

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

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