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

影!fJ学何论文 摘 要 相似字符串匹配是计算机科学中的一个基础问题，它在很多领域都有广泛的 应用，如信息检索、计算生物学和模式识别等。研究快速、准确和低耗的相似字 符串匹配算法对这些方向的发展有一定的推动作用。 q-gram索引具有语言独立性和高容错性，适合中文处理。过滤算法能根掘过 滤条件快速抛弃文本中与匹配无关的文本片段，适合大库查找。q-gram索引和过 滤算法经常结合使用，q-gram过滤算法因其简单、快速而得到广泛应用。为对中 文语料库进行相似字符串匹配，提高q-gram过滤算法的匹配速度，本文主要从中 文索引结构、索引优化、匹配区域特征挖掘等方面进行研究。 为对中文语料库进行相似字符串匹配，本文提出一种中文Bigram二级哈希索 引结构，索引中使用哈希函数把中文GB2312编码表中的所有汉字映射到一维连续 的整数空间中，并采用二级存储方式存储中文Bigram项。 为提高索引速度和减少索引占用空间，本文对索引进行了优化。采用链表式 内存管理方案对地址列表的内存分配进行管理，这种方法提高了内存的使用效率。 采用了索引压缩技术减少索引占用的内存空间，实验中针对多种压缩算法进行对 比，得出了适合三元组地址列表的中文Bigram索引压缩方法。 为通过提高过滤算法的过滤效率加快匹配速度，提出一种基于匹配区域特征 的过滤算法。该算法将模式串和文本串都分割成固定长度的逻辑块，并从各块中 提取了新的匹配区域特征。新算法利用新特征优化了基础过滤准则，提高了算法 的过滤效率，并改进了基于分块策略的过滤区确定方案。实验结果表明当误差率 较低时，新算法要明显好于改进前算法，在误差率要求较小的相似字符串匹配系 统中新算法具有较好的应用前景。 关键词：相似字符串匹配；过滤算法；O-gram索引；索引压缩；匹配区域特征； 过滤准则 丰丌似7符串幔配过滤并法研歹[ Abstract wasabasicissuein science．Itwas Approximatestringmatching computer usedinvariousfieldssuchasInformation widely Retrieve，ComputationalBiology, Pattern on for Recognition，eta1．Researchingapproximatestringmatchinghighspeed， andlow willbea totheseareas． highaccuracy consumptionpush indexhasthemeritof and it tolerant，and Q-gram languageindependencegarble wasoftenusedto Chinese．Filtercouldthrowoffalotoftext processing algorithm by filter itwasoftenusedfor in was used criterion，SO matchingbigtext．Q-gramwidely forits and itwas usedwithfilter simplehighspeed，andalways algo