Talk:Wagner–Fischer algorithm
| This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||
| |||||||||||||||
Did Levenshtein publish this algorithm?
[edit ]Although everyone seems to think that Levenshtein invented Levenshtein distance and the Wagner-Fishcher algorithm, Kukich (1992) states that
The first minimum edit distance spelling correction algorithm was implemented by Damerau [1964]. About the same time, Levenshtein [1966] developed a similar algorithm for correcting deletions, insertions, and reversals (transpositions).
So what he invented is quite different from what the vanilla Wagner-Fischer algorithm computes. QVVERTYVS (hm?) 21:33, 10 June 2015 (UTC) [reply ]
- Never mind. Kukich is mistaken. A glance at the original paper (or rather, its English translation) shows that Levensthein did not consider transpositions, but substitutions of the form 0->1 and 1->0; he assumed a binary alphabet. QVVERTYVS (hm?) 21:38, 10 June 2015 (UTC) [reply ]
- The distance metric was published by Levenshtein with examples that he calculated by hand. The Wagner-Fischer algorithm is a method for calculating Levenshtein distance. I personally believe that they used the Needleman-Wunsch method for optimal string matching and altered it to produce Levenshtein distance. 135.84.167.41 (talk) 17:01, 23 September 2019 (UTC) [reply ]
Pseudo-code
[edit ]Does the proposed algorithm return the Levenshtein distance? I was under the impression that for the Levenshtein distance the cost of the substitution operation was 2, rather than 1 as in the pseudo-code proposed on this page. — Preceding unsigned comment added by 92.221.143.252 (talk • contribs) 21:05, 5 December 2016 (UTC) [reply ]
Pseudo-code does not match proof
[edit ]The pseudo-code looks at insert and delete operations in the case where the characters are equal, but the proof does not. The proof chooses zero-cost substitution when the characters are equal without considering insertion and deletion. The code takes the minimum of the insert, delete, or zero-substitution options. The code could be match the proof by replacing "substitutionCost := 0;" with "d[i,j] := d[i-1,j-1];" and placing the minimization expression under the else clause, knowing that the characters are not equal.
The question I have is can the zero-cost substitution be beaten by an insert or deletion operation with lower cost, as the code allows?