Spelling Correction as an Iterative Process that Exploits the Collective Knowledge of Web Users

Spelling correction as an iterative process that exploits the collective knowledge of web users Silviu Cucerzan and Eric Brill Microsoft Research One Microsoft Way Redmond, WA 98052 {silviu,brill}@microsoft.com Abstract Logs of user queries to an internet search engine pro- vide a large amount of implicit and explicit informa- tion about language. In this paper, we investigate their use in spelling correction of search queries, a task which poses many additional challenges beyond the traditional spelling correction problem. We pre- sent an approach that uses an iterative transformation of the input query strings into other strings that corre- spond to more and more likely queries according to statistics extracted from internet search query logs. 1 Introduction The task of general purpose spelling correction has a long history (e.g. Damerau, 1964; Rieseman and Hanson, 1974; McIlroy, 1982), traditionally focus- ing on resolving typographical errors such as in- sertions, deletions, substitutions, and transpositions of letters that result in unknown words (i.e. words not found in a trusted lexicon of the language). Typical word processing spell checkers compute for each unknown word a small set of in-lexicon alternatives to be proposed as possible corrections, relying on information about in-lexicon-word frequencies and about the most common keyboard mistakes (such as typing m in- stead of n) and phonetic/cognitive mistakes, both at word level (e.g. the use of acceptible instead of acceptable) and at character level (e.g. the misuse of f instead of ph). Very few spell checkers attempt to detect and correct word substitution errors, which refer to the use of in-lexicon words in inap- propriate contexts and can also be the result of both typographical mistakes (such as typing coed instead of cord) and cognitive mistakes (e.g. prin- cipal and principle). Some research efforts to tackle this problem have been made; for example Heidorn et al. (1982) and Garside et al. (1987) de- veloped systems that rely on syntactic patterns to detect substitution errors, while Mays et al. (1991) employed word co-occurrence evidence from a large corpus to detect and correct such errors. The former approaches were based on the imprac- tical assumption that all possible syntactic uses of all words (i.e. part-of-speech) are known, and presented both recall and precision problems be- cause many of the substitution errors are not syn- tactically anomalous and many unusual syntactic constructions do not contain errors. The latter ap- proach had very limited success under the assump- tions that each sentence contains at most one misspelled word, each misspelling is the result of a single point change (insertion, deletion, substitu- tion, or transposition), and the defect rate (the rela- tive number of errors in the text) is known. A different body of work (e.g. Golding, 1995; Gold- ing and Roth, 1996; Mangu and Brill, 1997) fo- cused on resolving a limited number of cognitive substitution errors, in the framework of context sensitive spelling correction (CSSC). Although promising results were obtained (92-95% accu- racy), the scope of this work was very limited as it only addressed known sets …

Content truncated to 500 words