计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

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

姜 华a,b,韩安琪a,b,王美佳a,b,王 峥a,b,吴雲玲a,b   

  1. (东北师范大学 a. 计算机科学与信息技术学院;b. 智能信息处理吉林省高校重点实验室,长春 130117)
  • 收稿日期:2012-10-15 出版日期:2014-01-15 发布日期:2014-01-13
  • 作者简介:姜 华(1964-),男,副教授,主研方向:文本挖掘,Web挖掘,聚类算法;韩安琪、王美佳、王 峥、吴雲玲,硕士研究生
  • 基金项目:
    吉林省发改委基金资助项目(吉发改高技[2012]747号)

Solution Algorithm of String Similarity Based on Improved Levenshtein Distance

JIANG Hua  a,b, HAN An-qi  a,b, WANG Mei-jia  a,b, WANG Zheng  a,b, WU Yun-ling  a,b   

  1. (a. School of Computer Science and Information Technology; b. University Key Laboratory of Intelligent Information Processing in Jilin Province, Northeast Normal University, Changchun 130117, China)
  • Received:2012-10-15 Online:2014-01-15 Published:2014-01-13

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

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

Abstract: 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 formula 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.

Key words: Levenshtein Distance(LD), LD algorithm, backtracking path, the longest common substring, similarity, fuzzy query

中图分类号: