基于拼音输入法的中文字符串近似匹配技术研究

摘要

字符串匹配是计算机科学中最经典、研究最广泛的问题之一，并且已经被应用到了众多领域当中。早期的研究多集中于精确匹配领域，提出了许多单模式匹配算法和多模式匹配算法。然而随着计算机和网络的飞速发展以及新问题的不断提出，人们逐渐发现在实际应用中有时更需要进行近似字符串匹配。它在信息查询和提取、模式识别、语音识别、文本编辑、OCR纠错、入侵检测、计算生物学等许多领域均有着重要的应用价值。因此，研究高效的近似字符串匹配算法具有重要的理论价值和实际意义。
　　近似字符串匹配问题又可称为“允许误差的串匹配问题”，它主要是在文本和数据库中找出模式串，并允许模式串和它在文本中的出现形式之间存在k个差异。近似字符串匹配问题的研究虽然经历了不短的时间历程，但是其中的研究对象绝大多数主要是针对DNA等小型字符集或针对英文等中等大小字符集，而对于汉字乃至亚洲语音等大型字符集的研究却仍然不多。
　　基于上述原因，本文将基于拼音输入法对中文字符串近似串匹配查询问题进行研究与改进。论文的主要内容、贡献和创新包括如下:
　　本文首先对论文的研究背景、研究目的、主要内容和组织结构进行了简要的介绍，同时还对近似字符串匹配问题进行了综述，介绍了相关的理论及主要研究方法。针对此，提出本文的研究目标，并对基于拼音串的近似汉字串衡量标准进行了概况描述。提出了基于拼音输入法的中文字符串相似性度量标准和近似串匹配查询技术。具体包括汉字句串转换为拼音句串，查找目标句串并确定串中近似拼音串的可能位置用以构造面向拼音串的候选集，进而构造中文近似字符串候选集，最后输出近似汉字串结果。该算法的最重要特点就是在查找目标句串并确定串中近似拼音串的可能位置阶段建立了双元素倒排索引并充分运用了q-gram技术，用以充分挖掘过滤技术、倒排索引及q-gram的潜力。算法在理论上和实践中均有较好的表现。给出了系统界面演示和实验结果分析。实验测试表明所提出的方法可以有效地解决基于拼音输入的中文近似匹配问题。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 问题提出

1．3 本文贡献

1．4 组织结构

第二章 背景知识

2．1 近似字符串匹配符号和定义

2．2 动态规划技术

2．3 自动机技术

2．4 文本分片技术

2．5 BPM-BM技术

2．6 多模式匹配

2．7 本章小结

第3章 问题定义

3．1 研究目标

3．2 基于拼音串的近似汉字串衡量标准

3．3 本章小结

第4章 中文字符串近似匹配

4．1 q-gram技术

4．2 汉字转拼音

4．2．1 汉字串转换为拼音串

4．2．2 建立拼音汉字对照字典

4．3 构造面向拼音串的候选集

4．3．1 建立双元素倒排索引

4．3．2 查找近似字符串在句串中的可能位置

4．4 构造中文字符串的候选集

4．4．1 查找近似串的有效拼音字符位置

4．4．2 计算编辑距离并输出近似汉字串

4．5 本章小结

第5章 实验与分析

5．1 实验设置

5．2 系统界面

5．3 实验演示

5．3．1 不同长度查询串的查询效果演示

5．3．2 不同编辑距离的查询效果演示

5．4 影响系统性能的主要因素

5．4．1 数据文本集的大小对查询时间的影响

5．4．2 查询串的长短对查询时间的影响

5．4．3 编辑距离的大小对查询时间的影响

5．5 本章小结

第6章 总结与展望

6．1 本文工作总结

6．2 未来工作

参考文献

致谢

攻硕期间参加的项目