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

摘要：

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

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

分类号：TP311.12(计算技术、计算机技术)

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

在线出版日期：2014-02-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：222-227