An effective algorithm for string correction using generalized edit distance-II. Computational complexity of the algorithm and some applications
This paper deals with the problem of estimating an unknown transmitted string Xs belonging to a finite dictionary H from its observable noisy version Y. In the first part of this paper  we have developed an algorithm, referred to as Algorithm I, to find the string X+ H which minimizes the generalized Levenshtein distance D( X Y). In this part of the paper we study the computational complexity of Algorithm I, and illustrate quantitatively the advantage Algorithm I has over the standard technique and other algorithms. Its superiority has been shown for various dictionaries, including the one consisting of the 1021 most common English words of length greater than unity . A comparison between Algorithm I and other algorithms used to correct misspelled words of a regular language is also made here. Some applications of Algorithm I are also discussed.
Kashyap, R.L. (R. L.), & Oommen, J. (1981). An effective algorithm for string correction using generalized edit distance-II. Computational complexity of the algorithm and some applications. Information Sciences, 23(3), 201–217. doi:10.1016/0020-0255(81)90056-6