采用BWT的多核并行的子串匹配算法

摘要：

针对P-BWT精确匹配算法存在只支持短串查询并且只能工作在单处理器上的问题,提出了一个多核并行的支持任意查询长度的精确查询算法.改进了P-BWT索引上的查询过程,当一个查询串跨越了多个数据分片时,首先在其匹配的最后一个分片上查询,然后依次在前面分片上进行验证.进一步提出了一个多核并行查询算法来减少搜索和验证过程的迭代次数.实验结果表明,所述算法可以高效并行地完成子串匹配任务.

关键词：BWT、全文索引、精确匹配、并行、多核

所属期刊栏目：37

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

资助基金：国家自然科学基金资助项目61322208,61272178,61129002,61572122,61532021;教育部高等学校博士学科点专项科研基金资助项目20110042110028

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

页数：共5页

页码：624-628