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

›› 2016, Vol. 29 ›› Issue (9): 7-.

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

邵清，叶琨

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

出版日期:2016-09-15 发布日期:2016-09-26
作者简介:邵清（1970-），女，博士，副教授。研究方向：网络智能等。叶琨（1993-），女，硕士研究生。研究方向：网络智能。
基金资助:
国家自然科学基金资助项目（61170277）；上海市教委科研创新基金资助项目（02120557）

Chinese Character String Matching Algorithm Based on Improved Edit Distance and Similarity

SHAO Qing, YE Kun

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

Online:2016-09-15 Published:2016-09-26

摘要/Abstract

摘要：

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

关键词: 编辑距离, 相似度, 归一化, 中文字符串, 近似匹配

Abstract:

A Chinese character string approximate matching algorithm based on the improved edit distance and similarity is proposed for better accuracy in Chinese string matching. Firstly the pinyin code is used by considering character of Chinese string, then dynamic programming algorithm is improved to effectively improve the accuracy of calculation; next, a normalization algorithm considering switching problems is introduced. With semantic edit and long distance the ratio of the length of the sentence as the result of the normalization, the accuracy and executive efficiency of approximate matching algorithm is improved. Experimental results show that the quality of the results by the improved algorithm is better than those by traditional algorithms with significant improvement in efficiency, recall, precision, time cost and other indicators.

Key words: edit distance, similarity, normalization, Chinese character string, approximate matching

中图分类号:

TP391.41

邵清，叶琨. 基于编辑距离和相似度改进的汉字字符串匹配[J]. , 2016, 29(9): 7-.

SHAO Qing, YE Kun. Chinese Character String Matching Algorithm Based on Improved Edit Distance and Similarity[J]. , 2016, 29(9): 7-.

[1]	邵志慧,杨俭,袁天辰,伍伟嘉. 基于排列熵和支持向量机的轨枕病害诊断[J]. 电子科技, 2022, 35(2): 52-58.
[2]	郝苗,陈临强. PMI与Hownet结合的中文微博情感分析[J]. 电子科技, 2021, 34(7): 50-55.
[3]	徐航帆,刘丛,唐坚刚,彭敦陆. 改进地标点采样的加速谱聚类算法[J]. 电子科技, 2021, 34(5): 47-53.
[4]	胡晨,胡德敏,胡钰媛,褚成伟. 一种改进的图像阴影去除方法[J]. 电子科技, 2021, 34(4): 41-46.
[5]	许凤翔. 一种改进相似度的协同过滤算法实现[J]. 电子科技, 2020, 33(2): 54-59.
[6]	卢佳伟,陈玮,尹钟. 融合TextRank算法的中文短文本相似度计算[J]. 电子科技, 2020, 33(10): 51-56.
[7]	杜美君,张伟,谢亚莲. 基于粒子群算法的PID控制器参数优化[J]. 电子科技, 2019, 32(6): 7-11.
[8]	胡德敏,程普芳. 一种改进的LeNet网络[J]. 电子科技, 2019, 32(3): 53-57.
[9]	谢林,李菲菲,陈虬. 基于稀疏自动编码机的场景识别算法[J]. 电子科技, 2019, 32(1): 38-41.
[10]	李映,李玉龙,王阳萍. 一种改进的混合协同过滤推荐算法[J]. , 2016, 29(4): 45-.
[11]	齐婷,佟国香. 基于改进的混合模式个性化选课推荐技术研究[J]. , 2016, 29(1): 152-.
[12]	张雅科. 基于模糊权重相似性的协同过滤算法研究[J]. , 2015, 28(7): 111-.
[13]	余婷. 基于结构相似度的图像去噪新方法[J]. , 2015, 28(3): 1-.
[14]	覃秋松,麦云飞. 模糊工程PID在气动位置伺服中的应用[J]. , 2015, 28(11): 104-.
[15]	方玉玲,魏赟. 基于二次网格的字符图像特征提取方法[J]. , 2015, 28(10): 72-.