Enhanced Levenshtein Edit Distance Method functioning as a String-to-String Similarity Measure | ||
| Iraqi Journal for Computers and Informatics ijci | ||
| Article 1, Volume 42, Issue 1, December 2016, Pages 48-54 | ||
| Authors | ||
| Abbas M. Al-Bakry; Marwa K. Al-Rikaby | ||
| Abstract | ||
| Levenshtein is a Minimum Edit Distance method; it is usually used in spell checking applications for generating candidates. The method computes the number of the required edit operations to transform one string to another and it can recognize three types of edit operations: deletion, insertion, and substitution of one letter. Damerau modified the Levenshtein method to consider another type of edit operations, the transposition of two adjacent letters, in addition to the considered three types. However, the modification suffers from the time complexity which was added to the original quadratic time complexity of the original method. In this paper, we proposed a modification for the original Levenshtein to consider the same four types using very small number of matching operations which resulted in a shorter execution time and a similarity measure is also achieved to exploit the resulted distance from any Edit Distance method for finding the amount of similarity between two given strings. | ||
| Keywords | ||
| Levenshtein; Distancem; method; functioning; String; Similarity; measure | ||
|
Statistics Article View: 157 PDF Download: 45 |
||