An Effective Algorithm for String Cowection Using Generaliied Edit Distances- II. Computational Complexity of the Algorithm and Some Applications*

This paper deals with the problem of estimating an unknown transmitted string X, belonging to a finite dictionary H from its observable noisy version Y. In the first part of this paper [IS] we have developed an algorithm, referred to as ~go~t ~ I, to find the string Xi fH which minimizes the generalized Levenshtein distance D ( X,/Y). In this part of the paper we study the computations complexity of Algorithm I, and illustrate qu~titatively 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 102 1 most common English words of length greater than unity [23]. 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. I