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

doi:10.3969/j.issn.1000-5641.2018.05.013

Abstract

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

CLC Number:

TP311.5

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.

References

[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.