近似串匹配过滤算法研究  

Research on Filtering Algorithm of Approximate String Matching

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

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

出　　处：《计算机技术与发展》2015年第4期171-176,共6页Computer Technology and Development

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

摘　　要：近似串匹配在众多研究领域都有广泛的应用,如文本检索、生物信息学等。文中对基于过滤技术的Off-line模式近似串匹配算法进行了相关研究。首先介绍了串匹配的基础知识和近似串匹配技术的应用分类;然后阐述了Off-line模式近似串匹配算法常用的索引结构;接着详细介绍了近似串匹配过滤算法的研究现状,并阐述了几个经典过滤算法的过滤原理;最后在实验中对比了这些经典过滤算法的性能差异,实验数据显示提高过滤效率和减少过滤时间是加快过滤算法匹配速度所要解决的关键问题。研究表明,基于留空q-gram的过滤算法是近似串匹配未来研究的方向。Approximate string matching is widely used in many areas, such as text retrieval, computational biology, etc. In this paper, a survey on filter-based approximate suing matching algorithm of Off-line mode is done. First,the preliminaries of string matching and the classifications of approximate suing matching techniques are introduced. Next, some index structures which are often used in Off-line ap- proximate string matching algorithms are illustrated. Then, the research status quo of approximate suing matching is described in detail, and some classical filter algorithms are illustrated. Last, the performance of these classical filtering algorithms is given in experiment, and experimental data shows that enhancing filtration efficiency and decreasing filtration time are two key issues of improving matching speed. The research shows that the filter algorithms based on gapped q-gram is a fmther research direction of approximate suing matching.

关 键 词：串匹配 近似串匹配 过滤算法 q-gram过滤 

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