Linear Space String Correction Algorithm Using The Damerau-Levenshtein Distance

摘要

We develop linear space algorithms to compute the Damerau-Levenshtein (DL) distance between two strings as well as to find a sequence of edit operations of length equal to the DL distance. The Damerau-Levenshtein (DL) distance between two strings is the minimum number of substitutions, inserts, deletes, and transpositions of adjacent characters required to transform one string into the other. In our previous research, we developed algorithms that run in 0(mn) time using only 0(s * min {m, n} + m + n) space, where s is the size of the alphabet comprising the strings. In this paper, we develop algorithms to compute the DL distance and corresponding edit sequence using 0(m+n) space and 0(mn) time. Extensive experiments conducted on three computational platforms-Xeon E5 2603, I7 -x980 and Xeon E5 2695 -show that, our algorithms, in addition to using less space, are much faster than earlier algorithms. In fact, our fastest algorithm for the DL distance is up to 56.4% faster than the fastest algorithm when run on a single core. The single core speedup to find the corresponding edit sequence is up to 57.4%. Our algorithms may be adapted to run on multicores providing a speedup up to 59.3%.