]> BibSonomy publications for /bibtex/1e378e3e7081bc260d3789d05fe66989c http://www.bibsonomy.org/burst/bibtex/1e378e3e7081bc260d3789d05fe66989c BibSonomy BuRST Feed for /bibtex/1e378e3e7081bc260d3789d05fe66989c 2008-10-12T00:39:32+02:00 A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances. about Levenshtein and Damerau editdistanz from dblphttp://www.bibsonomy.org/bibtex/27647daf53f3c46bff7ab25d918717763/thomas thomas 2006-10-07T22:13:55+02:00 PDF damerau distance levenshtein matching uni
A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances.
Heikki Hyyrö Nord. J. Comput. 10 29-39 (2003)
to PDF damerau distance levenshtein matching uni by thomas on 2006-10-07 22:13:55 ]]> Nord. J. Comput.129-39A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances.102003PDF damerau distance levenshtein matching uni 2006-10-07 22:13:55.0 A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances. about Levenshtein and Damerau editdistanz from dblphttp://www.bibsonomy.org/bibtex/27647daf53f3c46bff7ab25d918717763/tmalsburg tmalsburg 2006-05-14T11:44:27+02:00 B_scanpathsimilarity algorithm article editdistance stringsimilarity toread
A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances.
Heikki Hyyrö Nord. J. Comput. 10 29-39 (2003)
to B_scanpathsimilarity algorithm article editdistance stringsimilarity toread by tmalsburg on 2006-05-14 11:44:27 ]]> Nord. J. Comput.129-39A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances.102003B_scanpathsimilarity algorithm article editdistance stringsimilarity toread 2006-05-14 11:44:27.0The edit distance between strings A and B is defined as the minimum number of edit operations needed in converting A into B or vice versa. The Levenshtein edit distance allows three types of operations: an insertion, a deletion or a substitution of a character. The Damerau edit distance allows the previous three plus in addition a transposition between two adjacent characters. To our best knowledge the best current practical algorithms for computing these edit distances run in time O(dm) and O(⌈m/w⌉(n + σ)), where d is the edit distance between the two strings, m and n are their lengths (m ≤ n), w is the computer word size and σ is the size of the alphabet. In this paper we present an algorithm that runs in time O(⌈d/w⌉m + ⌈n/w⌉σ) or O(⌈d/w⌉n + ⌈m/w⌉σ). The structure of the algorithm is such, that in practice it is mostly suitable for testing whether the edit distance between two strings is within some pre-determined error threshold. We also present some initial test results with thresholded edit distance computation. In them our algorithm works faster than the original algorithm of Myers. A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances. dblphttp://www.bibsonomy.org/bibtex/27647daf53f3c46bff7ab25d918717763/dblp dblp 2004-01-14T00:00:00+01:00 dblp
A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances.
Heikki Hyyrö Nord. J. Comput. 10 29-39 (2003)
to dblp by dblp on 2004-01-14 00:00:00 ]]> Nord. J. Comput.129-39A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances.102003dblp 2004-01-14 00:00:00.0