This study deals with the problem of estimating a transmitted string X//s, when the only observable string is its noisy version Y. Y is assumed to contain substitution, deletion and insertion errors. Based on three generalized edit distances of substitution, insertion and deletion and on the properties of the noisy channel through which X//s is transmitted, a distance D(X/Y) is defined between a word X contained in the dictionary H and the noisy string Y. The best estimate X* of X//s is defined as that element of H which minimizes this distance. Using dynamic programming principles, an algorithm is then presented which yields x* without computing individually the distances between every word of H and Y.

Additional Metadata
Journal Proceedings - IEEE Computer Society Conference on Pattern Recognition and Image Processing
Citation
Kashyap, R.L. (R. L.), & Oommen, J. (1979). EFFECTIVE ALGORITHM FOR STRING CORRECTION USING A GENERALIZED DISTANCE. Proceedings - IEEE Computer Society Conference on Pattern Recognition and Image Processing, 184–191.