一种空间高效的多核并行近似子串匹配方法

摘要

子串匹配问题是信息检索、信号处理以及生物信息学等领域中的研究重点.随着文本数据的快速增长,在大数据集上高效地完成近似子串匹配是一项挑战.另一方面,多核架构已经成为当今的主流计算机架构,如何在大规模数据中利用多核的优势提高近似子串匹配的效率是本文的研究重点.BWT索引是生物信息学中广泛应用的索引方法,其特点是索引空间小,支持高效压缩和子串匹配.但现有的基于BWT的方法没有考虑多个查询串上的计算共享以及多核资源的动态分配.本文在传统的BWT搜索方法基础上对搜索过程进行了改进,采用过滤和验证的方式完成近似子串匹配.首先,对查询串进行分割重组来减少搜索过程中的重复计算.其次,利用多核优势,动态地按需分配处理器资源从而提高搜索和验证的效率.最后,实验研究展示了本文提出的方法的高效性.