基于改进编辑距离的字符串相似度求解算法

被引：72

作者：

姜华 ^{[1
,2
]}

韩安琪 ^{[1
,2
]}

王美佳 ^{[1
,2
]}

王峥 ^{[1
,2
]}

吴雲玲 ^{[1
,2
]}

机构：

[1] 东北师范大学计算机科学与信息技术学院

[2] 东北师范大学智能信息处理吉林省高校重点实验室

来源：

计算机工程 | 2014年 / 40卷 / 01期

关键词：

编辑距离; LD算法; 回溯路径; 最长公共子串; 相似度; 模糊查询;

D O I：

暂无

中图分类号：

TP301.6 [算法理论]; TP391.1 [文字信息处理];

学科分类号：

081202 ; 081203 ; 0835 ;

摘要：

编辑距离(LD)算法在求解两个字符串的相似问题时只考虑了编辑操作次数,未考虑字符串之间的公共子串对相似度的影响。为此,提出一种基于改进编辑距离的字符串相似度求解算法,对字符串相似度度量公式及Levenshtein矩阵计算方法进行改进。在计算编辑距离时,以原有矩阵求出两字符串的最长公共子串及所有LD回溯路径。选取一个单词作为源串,一组与源串不同程度相似的单词为目标串,将改进的相似度度量公式与现有的字符串相似度计算方法进行比较,改进公式减少了进入胜者表的目标串数,相似度的样本极差和标准差分别为0.331和0.150。实验结果表明,改进算法在不改变空间复杂度的情况下,计算字符串相似度的准确性更高,且查询方式更灵活。

引用

页码：222 / 227

页数：6

共 4 条

[1] Levenshtein距离在编程题自动评阅中的应用研究 [J].