String correction using the Damerau-Levenshtein distance

Abstract

Background: In the string correction problem, we are to transform one string into another using a set of prescribed edit operations. In string correction using the Damerau-Levenshtein (DL) distance, the permissible edit operations are: substitution, insertion, deletion and transposition. Several algorithms for string correction using the DL distance have been proposed. The fastest and most space efficient of these algorithms is due to Lowrance and Wagner. It computes the DL distance between strings of length m and n, respectively, in O(mn) time and O(mn) space. In this paper, we focus on the development of algorithms whose asymptotic space complexity is less and whose actual runtime and energy consumption are less than those of the algorithm of Lowrance and Wagner.

Results: We develop space- and cache-efficient 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. Our algorithms require O(s min{m,n}+m+n) space, where s is the size of the alphabet and m and n are, respectively, the lengths of the two strings. Previously known algorithms require O(mn) space. The space- and cache-efficient algorithms of this paper are demonstrated, experimentally, to be superior to earlier algorithms for the DL distance problem on time, space, and enery metrics using three different computational platforms.

Conclusion: Our benchmarking shows that, our algorithms are able to handle much larger sequences than earlier algorithms due to the reduction in space requirements. On a single core, we are able to compute the DL distance and an optimal edit sequence faster than known algorithms by as much as 73.1% and 63.5%, respectively. Further, we reduce energy consumption by as much as 68.5%. Multicore versions of our algorithms achieve a speedup of 23.2 on 24 cores.

Keywords: Cache efficient; Damerau-Levenshtein distance; Edit distance; String correction.

Fig. 1

DL trace example

Fig. 2

DL trace recurrence. a substitution b insertion c deletion d translate A[k:i] to B[l:j] where (a _k,b _j) and (b _l,a _i) form a transposition opportunity

Fig. 3

Computing H by strips

Fig. 4

DL trace splitting opportunities. a No center crossing b With center crossing

Fig. 5

Cache misses for DL distance algorithms on Xeon4

Fig. 6

Run time of DL distance algorithms, in seconds, on Xeon4

Fig. 7

CPU and cache energy consumption of DL distance algorithms, in joules, on Xeon4

Fig. 8

Cache misses for DL trace algorithms on Xeon4

Fig. 9

Run time of DL trace algorithms, in seconds, on Xeon4

Fig. 10

CPU and cache energy consumption of DL trace algorithms, in joules, on Xeon4

Fig. 11

Cache misses of parallel DL distance algorithms on Xeon4

Fig. 12

Run time of parallel DL distance algorithms, in seconds, on Xeon4

Fig. 13

CPU and cache energy consumption of parallel DL distance algorithms, in joules, on Xeon4

Fig. 14

Cache misses for parallel DL trace algorithms on Xeon4

Fig. 15

Run time of parallel DL trace algorithms, in seconds, on Xeon4

Fig. 16

CPU and cache energy consumption of parallel DL trace algorithms, in joules, on Xeon4

Fig. 17

Run time of DL distance algorithms, in seconds, on Xeon6

Fig. 18

Run time of DL trace algorithms, in seconds, on Xeon6

Fig. 19

Run time of parallel DL distance algorithms, in seconds, on Xeon6

Fig. 20

Run time of parallel DL trace algorithms, in seconds, on Xeon6

Fig. 21

Run time of DL distance algorithms, in seconds, on Xeon24

Fig. 22

Run time of DL trace algorithms, in seconds, on Xeon24

Fig. 23

Run time of parallel DL distance algorithms, in seconds, on Xeon24

Fig. 24

Run time of parallel DL trace algorithms, in seconds, on Xeon24