String correction using the Damerau-Levenshtein distance.

Area of Science:

• Computer Science
• Bioinformatics
• Computational Linguistics

Background:

• The string correction problem involves transforming one string into another using edit operations like substitution, insertion, deletion, and transposition.
• The Damerau-Levenshtein (DL) distance quantifies the minimum number of these operations required.
• Existing algorithms, such as Lowrance and Wagner's, offer O(mn) time and space complexity.

Purpose of the Study:

• To develop novel algorithms for computing the Damerau-Levenshtein (DL) distance.
• To improve upon the space and time efficiency of existing DL distance algorithms.
• To reduce the energy consumption associated with string correction computations.

Main Methods:

• Development of space- and cache-efficient algorithms for DL distance calculation.
• Implementation of algorithms to find optimal edit sequences.
• Experimental benchmarking across multiple computational platforms.

Main Results:

• Achieved O(s min{m,n}+m+n) space complexity, a significant reduction from the O(mn) of previous algorithms.
• Demonstrated experimental superiority in time, space, and energy metrics.
• Enabled processing of substantially larger sequences due to reduced memory requirements.

Conclusions:

• The new algorithms handle larger sequences efficiently due to reduced space needs.
• Single-core performance shows significant speedups (up to 73.1% for DL distance, 63.5% for edit sequences) and energy reduction (up to 68.5%).
• Multicore implementations achieve notable speedups, with 23.2x on 24 cores.