| 基于匹配区域特征的相似字符串匹配过滤算法孙德才 |
| |
| 引用本文： | 孙德才,孙星明,张伟,刘玉玲.基于匹配区域特征的相似字符串匹配过滤算法孙德才[J].计算机研究与发展,2010,47(4). |
| |
| 作者姓名： | 孙德才 孙星明 张伟 刘玉玲 |
| |
| 作者单位： | 湖南大学计算机与通信学院,长沙,410082 |
| |
| 基金项目： | 国家“九七三”重点基础研究发展计划基金项目(2006CB303000);;国家自然科学基金重点项目(60736016);;国家自然科学基金项目(60573045,60873198,60973113,60973128);;国家“九七三”重点基础研究发展计划基金前期研究专项项目(2009CB326202);;高等学校博士学科点专项科研基金项目(20050532007)~~ |
| |
| 摘 要： | 相似字符串匹配过滤算法因其适合大库查找而被广泛应用,为通过提高过滤算法的过滤效率加快匹配速度,提出一种基于匹配区域特征的过滤算法.该算法将模式串和文本串分割成固定长度为kq+1的逻辑块,并从各块中提取了2个新的匹配区域特征:q-gram命中的均匀性和q-gram有效命中的区域性.新算法利用这些新特征优化了传统过滤标准,提高了算法的过滤效率;并改进了QUASAR中基于分块策略的过滤区确定方案.实验结果表明,新算法与改进前相比有效地加快了匹配速度,尤其在误差率较小时改进效果更佳.
|
| 关 键 词： | 相似字符串匹配 过滤算法 匹配区域特征 过滤效率 q-gram |
A Filter Algorithm for Approximate String Matching Based on Match-Region Features |
| |
| Sun Decai,Sun Xingming,Zhang Wei, Liu Yuling.A Filter Algorithm for Approximate String Matching Based on Match-Region Features[J].Journal of Computer Research and Development,2010,47(4). |
| |
| Authors: | Sun Decai Sun Xingming Zhang Wei Liu Yuling |
| |
| Affiliation: | School of Computers and Communications;Hunan University;Changsha 410082 |
| |
| Abstract: | Approximate string matching is a basic problem in computer science.It is widely used in various areas.The aim of this study is to improve the speed of approximate string matching.Filter algorithm for approximate string matching is discussed because it is suitable for large-scale text searching.A novel filter algorithm based on match-region features is presented.Firstly,a q-gram index is used to preprocess text.Secondly,both pattern and text are logically divided into blocks of fixed size kq+1,and then new m... |
| |
| Keywords: | approximate string matching filter algorithm match-region feature filtration efficiency q-gram |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
