An algorithm for finding the EditDistance between two strings.

See:

R. A. Wagner and M. J. Fisher. The string-to-string correction problem. Journal of the Association for Computing Machinery, 21(1):168-173, January 1974.

The Wagner Fisher algorithm employs dynamic programming methods to calculate the Levenshtein Distance (see EditDistance) between any pair of strings. It uses an iterative process to find successive distances between increasingly longer pairs of prefixes of the two strings, computed with the aid of a matrix.

''Doesn't Levenshtein's publication predate that of Wagner and Fisher? Or did Levenshtein never publish an algorithm?''

'''Google is your friend ...''' An excellent explanation can be found at
* http://www.ling.ohio-state.edu/~xflu/384/handouts/editcost.pdf

----

The DiffAlgorithm page claims that the Hunt-Mc''''''Ilroy algorithm is better than the Wagner Fisher algorithm.
----
See also:
* AlgorithmsRoadMap
----
CategoryAlgorithm