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

来源期刊：东北大学学报(自然科学版)2016年第5期

论文作者：王佳英 王斌 李晓华 杨晓春

文章页码：624 - 628

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

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