基于局部变化性的改进编辑距离算法

王卫红，李 君

（浙江工业大学计算机科学与技术学院，杭州310023）

·开发研究与工程应用·

基于局部变化性的改进编辑距离算法

王卫红，李 君

（浙江工业大学计算机科学与技术学院，杭州310023）

针对经典编辑距离算法在求解字符串相似度时计算效率过低的问题，提出一种改进的编辑距离算法。先求得2个字符串的最长公共前缀和最长公共后缀，再根据经典编辑距离算法得到2个字符串剩余部分之间的编辑距离，由反证法证明该编辑距离即为2个原始字符串的编辑距离。在此基础上，分析改进算法的优势并将其应用于网页篡改检测中。实验结果表明，与经典算法相比，改进算法在求解同一网址的网页相似度时具有更高的计算效率。

编辑距离；相似度；公共前缀；公共后缀；局部变化性；篡改检测

中文引用格式：王卫红，李 君.基于局部变化性的改进编辑距离算法［J］.计算机工程，2015，41（7）：294⁃298，304.

英文引用格式：Wang Weihong，Li Jun.Improved Edit Distance Algorithm Based on Local Variability［J］.Computer Engineering，2015，41（7）：294⁃298，304.

1 概述

字符串相似度问题在抄袭检测系统、数据清洗、信号处理、搜索引擎等领域具有广泛应用。根据计算所依据特征的不同，计算方法可以划分为3种方法［1⁃2］：基于字面相似的方法，基于统计关联的方法，基于语义相似的方法。基于编辑距离的相似度算法是基于字面相似方法中的一种，它从整体上考虑了文本上下文之间的语义关系，是一种经典而广为使用的方法。

近年来，对基于编辑距离相似度算法的研究偏重于算法效果的改善。比如考虑到字符串之间公共子串对相似度的影响，对相似度度量公式和编辑距离计算方法进行了改进［3］。……