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

Solution Algorithm of String Similarity Based on Improved Levenshtein Distance

作　　者：姜华 韩安琪[1,2] 王美佳 王峥 吴雲玲 

机构地区：[1]东北师范大学计算机科学与信息技术学院,长春130117 [2]东北师范大学智能信息处理吉林省高校重点实验室,长春130117

出　　处：《计算机工程》2014年第1期222-227,共6页Computer Engineering

基　　金：吉林省发改委基金资助项目(吉发改高技[2012]747号)

摘　　要：编辑距离(LD)算法在求解两个字符串的相似问题时只考虑了编辑操作次数,未考虑字符串之间的公共子串对相似度的影响。为此,提出一种基于改进编辑距离的字符串相似度求解算法,对字符串相似度度量公式及Levenshtein矩阵计算方法进行改进。在计算编辑距离时,以原有矩阵求出两字符串的最长公共子串及所有LD回溯路径。选取一个单词作为源串,一组与源串不同程度相似的单词为目标串,将改进的相似度度量公式与现有的字符串相似度计算方法进行比较,改进公式减少了进入胜者表的目标串数,相似度的样本极差和标准差分别为0.331和0.150。实验结果表明,改进算法在不改变空间复杂度的情况下,计算字符串相似度的准确性更高,且查询方式更灵活。When calculating the similarity of strings, the Levenshtein Distance（LD） algorithm only considers the operating times and ignores the common substrings of two strings. Aiming at this problem, an improved Levenshtein distance algorithm is proposed to calculate the similarity. The new algorithm improves the formula of similarity and the Levenshtein matrix. When calculating the distance, the new algorithm calculates the longest common substring and all the LD backtracking paths in the original matrix at the same time. Selecting a word in the experiment as a source string, a set of similar words of the different degrees of the source string as a target string, the new similarity measure rmula is compared with the existing string similarity calculation method, the new formula reduces the number of target strings into the winner table with similarity sample range and standard deviation of 0.331 and 0.150, respectively. Experimental results show that the new algorithm has higher accuracy and more flexible searching way in the same space complexity.

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

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]