A string correction algorithm for cursive script recognition

This paper deals with a method of estimating a correct string X from its noisy version Y produced by a cursive script recognition system. An accurate channel model that allows for splitting, merging, and substitution of symbols is introduced. The best estimate X is obtained by using a dynamic programming search which combines a known search strategy (stack decoding) with a trie structure representation of a dictionary. The computational complexity of the algorithm is derived and compared with that of a method based on the generalized Levenshtein metric. Experimental results with the algorithm on English text based on a dictionary of the 1027 most commonly occurring words are described.