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

doi:10.3969/j.issn.1000-5641.2018.05.013

华东师范大学学报(自然科学版) ›› 2018, Vol. 2018 ›› Issue (5): 154-163.doi: 10.3969/j.issn.1000-5641.2018.05.013

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

张衡, 陈良育

华东师范大学上海市高可信计算重点实验室, 上海 200062

收稿日期:2018-07-04 出版日期:2018-09-25 发布日期:2018-09-26
通讯作者: 陈良育,男,副教授,研究方向为计算机软件与理论.E-mail:lychen@sei.ecnu.edu.cn. E-mail:lychen@sei.ecnu.edu.cn
作者简介:张衡,男,硕士研究生,研究方向为自然语言处理.E-mail:51174500154@stu.ecnu.edu.cn.
基金资助:
国家自然科学基金（11471209）

Optimization of the Levenshtein algorithm and its application in repeatability judgment for test bank

ZHANG Heng, CHEN Liang-yu

Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200062, China

Received:2018-07-04 Online:2018-09-25 Published:2018-09-26

摘要/Abstract

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

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

Abstract: In order to overcome the disadvantages of the Levenshtein distance algorithm for long text and large-scale matching, we propose an early termination strategy for the Levenshtein distance algorithm. Firstly, according to the intrinsic relationship between elements in the Levenshtein distance matrix, we sum up a recurrence relation. Based on this relation, an early termination strategy is proposed to determine early-on whether two texts satisfy the predefined similarity threshold. Through several tests on different subjects, it is demonstrated that the early termination strategy can significantly reduce calculation time.

Key words: bank match, text similarity, Levenshtein edit distance

中图分类号:

TP311.5

张衡, 陈良育. Levenshtein算法优化及在题库判重中的应用[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 154-163.

ZHANG Heng, CHEN Liang-yu. Optimization of the Levenshtein algorithm and its application in repeatability judgment for test bank[J]. Journal of East China Normal University(Natural Sc, 2018, 2018(5): 154-163.

参考文献

[1] HALL P, DOWLING G. Approximate string matching[J]. ACM Computing Survey, 1980, 12(4):381-402.
[2] WAGNER R, FISCHER M. The string-to-string correction problem[J]. Journal of the ACM, 1974, 21(1):168-173.
[3] 章成志. 基于多层特征的字符串相似度计算模型[J]. 情报学报, 2005, 24(6):696-701.
[4] MONGE A, ELKAN C. The field matching problem:Algorithms and applications[C]//Proc of ACM International Conference on Knowledge Discovery and Data Mining. New York:ACM, 1996:267-270.
[5] NIRENBURG S, DOMASHNEV C, GRANNES D. Two approaches to matching in example-based machine translation[C]//Proc of the 5th International Conference on Theoretical and Methodological Issues in Machine Translation. Kyoto:TMI, 1993:47-57.
[6] JIN L, LI C, MEHROTRA S. Efficient record linkage in large data sets[C]//Proc of the 8th International Conference on Database System for Advanced Application. Kyoto:DASFAA, 2003:137-146.
[7] 邵清, 叶琨. 基于编辑距离和相似度改进的汉字字符串匹配[J]. 电子科技, 2016, 29(9):7-11.
[8] 廖宏建, 杨玉宝, 唐连章.改进的编辑距离计算及其在自动评分中的应用[J]. 广州大学学报(自然科学版), 2012, 11(4):79-83.
[9] LEVENSHTEIN V. Binary codes capable of correcting deletions, insertions and reversals[J]. Soviet Physics Doklady, 1966, 10(1):845-848.
[10] 玛依热·依布拉音, 米吉提·阿不里米提, 艾斯卡尔·艾木都拉.基于最小编辑距离的维语词语检错与纠错研究[J]. 中文信息学报, 2008, 22(3):110-114.
[11] 姜华, 韩安琪, 王美佳, 等. 基于改进编辑距离的字符串相似度求解算法[J]. 计算机工程, 2014, 40(1):222-227.
[12] 何锋, 谷锁林, 陈彦辉. 基于编辑距离相似度的文本校验技术研究与应用[J]. 飞行器测控学报, 2015, 34(4):389-394.
[13] LI G, DENG D, WANG J, et al. Pass-join:A partition-based method for similarity joins[J]. Proceedings of the VLDB Endowment, 2011, 5(3):253-264.

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

Optimization of the Levenshtein algorithm and its application in repeatability judgment for test bank

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价