Talk:Damerau-Levenshtein distance
From Wikipedia, the free encyclopedia
There is an error in this algorithm. String indices start at 0, but the algorithm starts string comparision at index = 1. The first character will not be tested and when i = lenStr1, str1[i] will be out of range. —The preceding unsigned comment was added by 68.15.100.248 (talk • contribs) 28 June 2006.
- There's no error — string indices start at 1, and are properly swept by the main loop. It's the d array which is indexed from zeros. The 0-th row and column are filled by two separate loops, so they can be accessed with d[i-1, j] and d[i, j-1] expressions in main loop. --CiaPan 14:33, 29 March 2007 (UTC)
The last sentence:
An extension of the edit distance algorithm, that does satisfy a triangle inequality is described in the paper: F.J. Damerau. A technique for computer detection and correction of spelling errors, Communications of the ACM, 1964
actually links to this paper:
- Source Journal of the ACM (JACM) archive
- Volume 22 , Issue 2 (April 1975) table of contents
- Pages: 177 - 183
- Year of Publication: 1975
- ISSN:0004-5411
- Authors:
- Robert A. Wagner Department of Systems and Information Sciences, Vanderbilt University, Nashville, TN
- Roy Lowrance 255 West Squire Drive, Rochester, NY and Vanderbilt University, Nashville, Tennessee
- Publisher ACM Press New York, NY, USA
I suspect that this is in fact the intended paper and that the sentence just needs to be re-written. —The preceding unsigned comment was added by 151.193.220.27 (talk • contribs) 9 March 2007.
