中文模糊匹配算法优化：同音字/近音字处理与编辑距离扩展

本文主要探讨了在中文信息检索系统中处理同音字和近音字的模糊匹配算法。针对用户经常产生的输入错误，如使用拼音输入法时的语音相同但字形或意义不同的同音字（如“江”与“姜”）以及相近发音的近音字（如前后鼻音和平舌卷舌的混淆），文章提出了改进的算法。 首先，文章介绍了扩展的动态规划剪枝算法。传统的动态规划方法在处理Edit Distance（编辑距离）时，通过非严格单调递增的主对角线策略，结合cut-off heuristic剪枝算法，减少了不必要的计算。作者在原有基础上增加了额外的条件，确保剪枝的有效性。 接着，扩展了改进的TU过滤算法，将算法扩展到了更广义的编辑距离概念。作者引入了新的“坏字符”定义，限制了成功的最小化路径在以当前位置为中心的一定范围内，以便更快地确定匹配的无效区域。当遇到过多的“坏字符”时，算法会跳过这些位置，转而计算更精确的子串匹配。 针对同音字和近音字的特殊性，算法对这类替换赋予了较小的权重（cost为0.5），而对其他替换和插入删除操作赋予较高权重（cost为1）。这样可以在保持召回率的同时，提高效率，尤其在处理大量数据时，达到了接近子线性的搜索速度。 实验结果显示，改进后的算法在歌曲名称数据库和用户查询日志中表现出色，显著提高了检索系统的召回率，对于实际应用具有很高的实用价值。同时，算法设计也充分考虑了输入字符串与数据库条目的局部偏差，增强了中文信息检索系统的鲁棒性和准确性。 本文的研究重点在于如何利用模糊匹配算法处理中文信息检索中的特定挑战，提供了一种有效的方法来处理同音字和近音字问题，这在提高检索性能和用户体验方面具有重要意义。