| 一种基于尾匹配q-gram的近似串匹配算法 |
| |
| 引用本文： | 孙德才,王晓霞.一种基于尾匹配q-gram的近似串匹配算法[J].计算机科学,2014,41(6):243-249. |
| |
| 作者姓名： | 孙德才 王晓霞 |
| |
| 作者单位： | 渤海大学信息科学与技术学院 锦州121013;渤海大学大学计算机教研部 锦州121013 |
| |
| 基金项目： | 本文受辽宁省社科联2014年度辽宁经济社会发展立项重点课题(2014lslktzdian-04), 国家自然科学基金项目(61173142,2),辽宁省教育厅一般项目(L2013422,L2012397),辽宁省“百千万人才工程”项目(2012921058)资助 |
| |
| 摘 要： | 近似串匹配是生物信息学、文本检索、信号处理等领域的一个基础问题,如何提高近似串匹配的速度一直都是研究的关键问题。提出一种新的在大文本库中快速查找近似匹配的无损过滤算法。为保证在大文本库中的匹配速度,本算法使用了查询速度较快的q-gram索引。为通过提高过滤算法的过滤效率达到提升算法整体性能的目的,详细分析了含有匹配串的文本区域,提取了一些基于尾匹配q-gram特征的新过滤条件,然后用这些特征优化了过滤算法的过滤标准。实验数据表明,新过滤条件有效地提高了算法的过滤效率,提升了算法的整体性能。结果显示新算法适合各种匹配错误率下的近似匹配,算法的通用性较强。
|
| 关 键 词： | 近似串匹配 过滤算法 q-gram过滤 q元语法 |
| 收稿时间： | 2013/8/19 0:00:00 |
| 修稿时间： | 2013/10/14 0:00:00 |
Approximate String Matching Using Tail Matched q-gram |
| |
| SUN De-cai and WANG Xiao-xia.Approximate String Matching Using Tail Matched q-gram[J].Computer Science,2014,41(6):243-249. |
| |
| Authors: | SUN De-cai and WANG Xiao-xia |
| |
| Affiliation: | College of Information Science and Technology,Bohai University,Jinzhou 121013,China;Teaching and Research Institute of College Computer,Bohai University,Jinzhou 121013,China |
| |
| Abstract: | |
| |
| Keywords: | Approximate string matching Filter algorithm q-gram filter q-gram |
| 本文献已被 CNKI 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
