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

摘要：

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

关键词：编辑距离、相似度、公共前缀、公共后缀、局部变化性、篡改检测

所属期刊栏目：41

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61340058;浙江省自然科学基金资助项目LZ14F020001

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

页数：共6页

页码：294-298,304