Levenshtein算法优化及在题库判重中的应用

来源：华东师范大学学报·哲学社会科学版杂志2018年第5期北京时间：

作者：张衡, 陈良育

单位：张衡,男,硕士研究生,研究方向为自然语言处理.E-mail:51174500154@stu.ecnu.edu.cn.

摘要：为了解决Levenshtein距离算法在长文本和大规模匹配效率的不足，本文针对Levenshtein距离算法提出一种提前终止的优化策略.首先根据Levenshtein距离矩阵中元素内在的联系，归纳总结出一个递推关系式.再依据此递推关系式，提出一种提前终止策略，可提前判断两个文本是否满足预先设定的相似度阈值.经过多个学科题库判重实验的佐证，本文的提前终止策略能显著减少计算时间.

关键词：题库匹配,文本相似度,Levenshtein编辑距离,

基金资助：国家自然科学基金（11471209）