North-Holland Spelling correction using probabilistic methods.pdf

Pattern Recognition Letters 2 (1984) 147-154 March 1984 North-Holland Spelling correction using probabilistic methods* R.L K A SH Y AP School of Electrical Engineering, Purdue University, West Lafayette, IN 47907, USA B.J. O O M M E N The Carleton University, Dept. of Computer Science, Ottawa, KIS 5R6, Ontario, Canada Received 13 July 1983 Abstract: A probabilistic procedure is suggested for the automatic correction of spelling and typing errors in printed English texts. The heart of the procedure is a probabilistic model for the generation of the garbled word from the correct word. The garbler can delete or insert symbols in the word or substitute one or more symbols by other symbols. An expression is derived for P(Y I X), the probability of generating a garbled word Y from a correct word X. The model is probabilistically consistent. Using the expression for P(Y I X), we can derive an estimate of the correct word from the garbled word Y so as to minimize the average probability of error in the decision. One of the important features of the expression P(Y I X) is that it can be com- puted recursively. Experiments conducted using the dictionary of 1025 most common English words indicate that the accuracy of correction by this scheme is substantially greater than that which can be obtained by other algorithms especially while dealing with garbled words derived from relatively short words of length less than 6. Key words: String correction, probabilistic string correction, string editing techniques, Levenshtein distance, minimum proba- bility of error string correction, modeling noisy channels, text editing, word processor. 1. Introduction The problem of automatic correction of spelling and typing errors has received considerable atten- tion in the literature over the past two decades. The basic problem in text correction is that a garbled word is given to us, which is derived from a correct word (unknown to us) by multiple errors of 3 typ