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

Q-gram Index for Approximate String Matching with Multi-seeds

作　　者：孙德才[1] 王晓霞[2] 

机构地区：[1]渤海大学信息科学与技术学院,锦州121013 [2]s渤海大学大学计算机教研部,锦州121013

出　　处：《计算机科学》2014年第9期279-284,共6页Computer Science

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

摘　　要：如何在大型文本库中快速找出给定串的近似串是大数据时代要解决的关键问题。基于多种子的近似串匹配算法因匹配速度快而得到众多学者的青睐,但巨大的索引空间消耗也使其难以处理大型文本库。提出了一种支持多种子的q-gram索引结构,通过该索引能够快速地计算出给定任意长度连续种子的地址集合,解决了多种子近似串匹配算法中种子的数目和长度受存储空间限制的问题。实验数据显示,新索引方案成倍地减少了存储空间的消耗。实验结果表明,提出的索引方案在大数据环境下的多种子近似匹配中具有一定的优势。How to find out all approximate strings of a given string from a big text database quickly is a key issue in the age of big data. Approximate string matching algorithm based on multi-seeds is researched for its fast searching speed. But it is difficult to process large text database due to its huge memory consumption, Here,a new q-gram index was proposed to solve the problem of multi-seeds used in approximate string matching algorithms. In the proposed index, the addresses of consecutive seed with arbitrary length can be computed out quickly. The experimental results demonstrate that the space consumption is decreased largely. As a result, the proposed index is of great practicality to deal with large database in the age of big data.

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

分 类 号：TP391.3[自动化与计算机技术—计算机应用技术]