改进版编辑距离下的字符串相似度计算方法 (2014年)

简介：
本文提出了一种基于改进版编辑距离算法的字符串相似度计算方法，旨在提高长字符串及包含重复子串情况下的匹配精度与效率。该研究于2014年完成。 编辑距离（LD）算法在评估两个字符串的相似性时仅考虑了所需的操作次数，而忽略了公共子串对相似度的影响。为此，提出了一种基于改进编辑距离的字符串相似度求解算法，该方法优化了现有字符串相似度度量公式及Levenshtein矩阵计算方式。 新的算法通过原有的矩阵来确定两字符串之间的最长公共子串以及所有LD回溯路径，在此基础上进行改进以提高准确性和效率。选取一个单词作为源串，并选择一组与之不同程度相异的单词为目标串，然后将新提出的相似度度量公式与其他现有的方法进行了比较分析。 实验结果显示，改进后的算法减少了进入胜者表的目标字符串数量，同时降低了样本极差和标准差值（分别为0.331 和 0）。这表明该优化方案在实际应用中能够有效提高计算效率并增强结果的可靠性。