EFFECTIVE ALGORITHM FOR STRING CORRECTION USING A GENERALIZED DISTANCE.

作     者：Kashyap, R.L. Oommen, B.J. 

出 版 物：《Proceedings - IEEE Computer Society Conference on Pattern Recognition and Image Processing》 

年 卷 期：1979年

页      面：184-191页

核心收录：

主　　题：PATTERN RECOGNITION SYSTEMS 

摘      要：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.