一种适合于GPU计算的并行后缀数组构造算法

• 作者: 孙伟东 马宗民
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 后缀数组构造 倍增法 GPGPU CUDA
• 年，卷（期）: 2011,（5）
• 所属期刊栏目: 计算机软件与数据库技术
• 页码范围: 830-836
• 分类号: TP311
• 字数: 7702字
• 语种: 中文

摘要

后缀数组广泛应用于序列分析、字符串匹配和文本压缩,近年来,有关后缀数组构造和应用算法的不断探索构成了计算机科学中一个非常活跃的研究领域.在对现有串行算法进行了分析和对比之后,提出了一种新的、简洁的适合于GPU计算的并行后缀数组倍增构造算法,以排序方法替代传统的分组策略,不但能独立完成后缀数组的并行构造,还可与现存的串行倍增算法结合使用,以达到最高的执行效率.实验结果表明该算法在解决实际应用问题时,具有易于实现、执行速度快和可扩展性强等优点,尤其在处理小字符集的数据时效率更高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马宗民	东北大学信息科学与工程学院	85	820	15.0	24.0