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

摘要：

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

关键词：后缀数组构造、倍增法、GPGPU、CUDA

所属期刊栏目：32

分类号：TP311(计算技术、计算机技术)

资助基金：教育部高等学校博士学科点专项科研基金项目20050145024

在线出版日期：2012-02-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：830-836