邵　清，叶　琨

(上海理工大学 光电信息与计算机工程学院，上海 200093)



基于编辑距离和相似度改进的汉字字符串匹配

邵清，叶琨

(上海理工大学 光电信息与计算机工程学院，上海 200093)

为解决中文字符串匹配精度较低的问题，提出了一种基于编辑距离和相似度改进的汉字字符串近似匹配算法，针对汉字字符串特点，使用汉字拼音和五笔编码计算；通过改进动态规划算法，能够有效提高编辑距离的计算准确度以及执行效率；再引入考虑交换问题的归一化算法，以语义编辑距离与长句长度的比值作为归一化结果，以此来提高近似匹配算法的准确度。实验结果表明，改进后算法计算的相似度质量要优于改进前的算法结果，且对提高算法效率和查全率、查准率和时间性能等指标均有明显改善，证明该算法的可行性和有效性。

编辑距离；相似度；归一化；中文字符串；近似匹配

随着信息技术的广泛应用，作为基础性研究的字符串匹配面对越来越多的挑战[1]。从20世纪70年代开始，字符串匹配问题的研究[2]就得到许多学者的关注，并且研究成果已广泛应用于生物、医学、犯罪取证等领域。目前，计算字符串相似度的算法有多种，其中编辑距离算法作为常用的字符串相似度求解算法，具有应用广泛、查找有效和时间复杂度较低等优势。文献[3]将整条记录看作一个字符串，计算两个字符串的编辑距离，从而判断两条记录的相似匹配程度，但是由于字符串长短不一，可能存在冗余属性对；……