相似字符串匹配过滤算法研究

摘要

相似字符串匹配是计算机科学中的一个基础问题,它在很多领域都有广泛的应用,如信息检索、计算生物学和模式识别等。研究快速、准确和低耗的相似字符串匹配算法对这些方向的发展有一定的推动作用。
　　 q-gram索引具有语言独立性和高容错性,适合中文处理。过滤算法能根掘过滤条件快速抛弃文本中与匹配无关的文本片段,适合大库查找。q-gram索引和过滤算法经常结合使用,q-gram过滤算法因其简单、快速而得到广泛应用。为对中文语料库进行相似字符串匹配,提高q-gram过滤算法的匹配速度,本文主要从中文索引结构、索引优化、匹配区域特征挖掘等方面进行研究。
　　 为对中文语料库进行相似字符串匹配,本文提出一种中文Bigram二级哈希索引结构,索引中使用哈希函数把中文GB2312编码表中的所有汉字映射到一维连续的整数空间中,并采用二级存储方式存储中文Bigram项。
　　 为提高索引速度和减少索引占用空间,本文对索引进行了优化。采用链表式内存管理方案对地址列表的内存分配进行管理,这种方法提高了内存的使用效率。采用了索引压缩技术减少索引占用的内存空间,实验中针对多种压缩算法进行对比,得出了适合三元组地址列表的中文Bigram索引压缩方法。
　　 为通过提高过滤算法的过滤效率加快匹配速度,提出一种基于匹配区域特征的过滤算法。该算法将模式串和文本串都分割成固定长度的逻辑块,并从各块中提取了新的匹配区域特征。新算法利用新特征优化了基础过滤准则,提高了算法的过滤效率,并改进了基于分块策略的过滤区确定方案。实验结果表明当误差率较低时,新算法要明显好于改进前算法,在误差率要求较小的相似字符串匹配系统中新算法具有较好的应用前景。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪论

1.1 研究目的及意义

1.2 Q-gram过滤算法研究现状

1.2.1 相似字符串匹配简介

1.2.2 Q-gram索引

1.2.3 过滤算法研究现状

1.3 本文主要工作与结构

第2章 中文索引与精确字符串匹配

2.1 索引结构简介

2.1.1 常用序列索引

2.1.2 Q-gram索引

2.1.3 中文处理与q-gram索引

2.2 中文Bigram二级哈希索引结构

2.2.1 GB2312编码

2.2.2 中文Bigram二级哈希索引

2.2.3 中文字符串精确匹配

2.3 中文Bigram二级哈希索引实验分析

2.3.1 实验语料库简介

2.3.2 实验结果

2.4 小结

第3章 索引优化

3.1 索引压缩

3.1.1 整数序列编码d-gaps

3.1.2 参数编码和无参数编码

3.1.3 位编码和字节编码

3.1.4 索引压缩处理过程

3.2 索引建立

3.2.1 索引建立与压缩

3.2.2 索引建立与内存管理

3.3 索引更新方案

3.4 索引压缩实验分析

3.4.1 各序列整数值与出现次数统计实验

3.4.2 各压缩编码性能对比实验

3.4.3 索引压缩效果

3.5 小结

第4章 相似字符串匹配过滤算法及改进

4.1 相似字符串过滤算法

4.1.1 过滤算法简介

4.1.2 过滤准则

4.1.3 相似字符串过滤算法匹配过程

4.2 匹配区域特征提取

4.3 基于匹配区域特征的改进过滤算法AdBlock

4.3.1 文本预处理、输入查询和查询预处理

4.3.2 过滤区确定

4.3.3 过滤、验证和输出

4.4 AdBlock算法伪代码

4.5 AdBlock算法退化

4.6 实验结果及分析

4.6.1 实验环境

4.6.2 算法性能分析

4.7 结论

结论

参考文献

附录A 攻读硕士学位期间发表的论文目录

附录B 攻读硕士学位期间参加的项目

致谢