基于Spark的通用后缀树并行构造算法

• 作者: 周经亚 高可攀
• 来源期刊: 福建电脑
• 关键词: 通用后缀树 Spark 弹性分布式数据集 子树划分 子树合并 构造算法
• 年，卷（期）: 2018,（5）
• 所属期刊栏目: 基金项目论文
• 页码范围: 4-7
• 页数: 4页
• 字数: 3431字
• 语种: 中文
• DOI: 10.16707/j.cnki.fjpc.2018.05.002

摘要

通用后缀树因其优良的结构特征被广泛应用于序列匹配、最长公共子序列查找等场合.在大数据时代,待处理序列的规模往往十分庞大,这给通用后缀树的构造带来巨大挑战.为应对这一挑战,本文提出一种并行分布式的通用后缀树构造算法.该算法采用子树划分与合并的思想,将构造过程分解为多个子任务并行执行,算法基于Spark平台设计实现,字符序列以弹性分布式数据集(RDD)形式存储,任务在RDD上分布式执行.基于真实数据集的实验表明,对数十亿字符序列构造通用后缀树,其构造过程可在7分钟内完成,由此可见,本文所提算法可高效解决大规模通用后缀树构造问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周经亚	苏州大学计算机科学与技术学院	2	10	1.0	2.0
2	高可攀	苏州大学计算机科学与技术学院	1	1	1.0	1.0