Journal of East China Normal University(Natural Sc ›› 2018, Vol. 2018 ›› Issue (5): 154-163.doi: 10.3969/j.issn.1000-5641.2018.05.013

Previous Articles     Next Articles

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

ZHANG Heng, CHEN Liang-yu   

  1. 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: 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: