一种支持多种子近似串匹配的q-gram索引

摘要：

如何在大型文本库中快速找出给定串的近似串是大数据时代要解决的关键问题.基于多种子的近似串匹配算法因匹配速度快而得到众多学者的青睐,但巨大的索引空间消耗也使其难以处理大型文本库.提出了一种支持多种子的q-gram索引结构,通过该索引能够快速地计算出给定任意长度连续种子的地址集合,解决了多种子近似串匹配算法中种子的数目和长度受存储空间限制的问题.实验数据显示,新索引方案成倍地减少了存储空间的消耗.实验结果表明,提出的索引方案在大数据环境下的多种子近似匹配中具有一定的优势.

关键词：大数据、近似串匹配、种子、q-gram索引、多种子索引

所属期刊栏目：41

分类号：TP391.3(计算技术、计算机技术)

资助基金：2014年辽宁省博士科研启动基金计划20141138;辽宁省社科联2014年度辽宁经济社会发展立项重点课题2014lslktzdian-04;国家自然科学基金项目61173142,61232016,61202462,61173141,61173136;辽宁省教育厅一般项目L2013422

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

页数：共6页

页码：279-284