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. Sev...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2019-06-01
|
| Series: | BMC Bioinformatics |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s12859-019-2819-0 |
| _version_ | 1819019281472421888 |
|---|---|
| author | Chunchun Zhao Sartaj Sahni |
| author_facet | Chunchun Zhao Sartaj Sahni |
| author_sort | Chunchun Zhao |
| collection | DOAJ |
| description | 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(m n) time and O(m n) 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(m n) 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. |
| first_indexed | 2024-12-21T03:32:49Z |
| format | Article |
| id | doaj.art-8459eebf03174c459c2e921ea699d74b |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-12-21T03:32:49Z |
| publishDate | 2019-06-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-8459eebf03174c459c2e921ea699d74b2022-12-21T19:17:25ZengBMCBMC Bioinformatics1471-21052019-06-0120S1112810.1186/s12859-019-2819-0String correction using the Damerau-Levenshtein distanceChunchun Zhao0Sartaj Sahni1Department of Computer and Information Science and Engineering, University of FloridaDepartment of Computer and Information Science and Engineering, University of FloridaAbstract 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(m n) time and O(m n) 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(m n) 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.http://link.springer.com/article/10.1186/s12859-019-2819-0Edit distanceDamerau-Levenshtein distanceCache efficientString correction |
| spellingShingle | Chunchun Zhao Sartaj Sahni String correction using the Damerau-Levenshtein distance BMC Bioinformatics Edit distance Damerau-Levenshtein distance Cache efficient String correction |
| title | String correction using the Damerau-Levenshtein distance |
| title_full | String correction using the Damerau-Levenshtein distance |
| title_fullStr | String correction using the Damerau-Levenshtein distance |
| title_full_unstemmed | String correction using the Damerau-Levenshtein distance |
| title_short | String correction using the Damerau-Levenshtein distance |
| title_sort | string correction using the damerau levenshtein distance |
| topic | Edit distance Damerau-Levenshtein distance Cache efficient String correction |
| url | http://link.springer.com/article/10.1186/s12859-019-2819-0 |
| work_keys_str_mv | AT chunchunzhao stringcorrectionusingthedameraulevenshteindistance AT sartajsahni stringcorrectionusingthedameraulevenshteindistance |