Learning a spelling error model from search query logs
Published 1 January 2005Open access
Hafiz Farooq Ahmad, Grzegorz Kondrak
Citations109
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper investigates using the Expectation Maximization algorithm to learn edit distance weights directly from search query logs, without relying on a corpus of paired words.
Abstract
Applying the noisy channel model to search query spelling correction requires an error model and a language model. Typically, the error model relies on a weighted string edit distance measure. The weights can be learned from pairs of misspelled words and their corrections. This paper investigates using the Expectation Maximization algorithm to learn edit distance weights directly from search query logs, without relying on a corpus of paired words.
Keywords
Computer Science
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
Communications of the ACMA technique for computer detection and correction of spelling errors
1,573 Citations1964Fred J. Damerau
The method described assumes that a word which cannot be found in a dictionary has at most one error, which might be a wrong, missing or extra letter or a single transposition.
ACM Computing SurveysTechniques for automatically correcting words in text
1,256 Citations1992Karen Kukich
Research aimed at correcting words in text has focused on three progressively more difficult problems: nonword error detection; (2) isolated-word error correction; and (3) context-dependent work correction, which surveys documented findings on spelling error patterns.
IEEE Transactions on Pattern Analysis and Machine IntelligenceLearning string-edit distance
861 Citations1998Eric Sven Ristad, P.N. Yianilos
The stochastic model allows us to learn a string-edit distance function from a corpus of examples and is applicable to any string classification problem that may be solved using a similarity function against a database of labeled prototypes.
Communications of the ACMFast text searching
728 Citations1992Sun Wu, Udi Manber
T h e string-matching problem is a very c o m m o n problem; there are many extensions to t h i s problem; for example, it may be looking for a set of patterns, a pattern w i t h "wi ld cards," or a regular expression.
An improved error model for noisy channel spelling correction
537 Citations2000Eric Brill, Robert C. Moore
A new channel model for spelling correction, based on generic string to string edits, is described, which gives significant performance improvements compared to previously proposed models.
A spelling correction program based on a noisy channel model
265 Citations1990Mark D. Kernighan, Kenneth Church +1 more
A new program is described, correct, which takes words rejected by the Unix® spell program, proposes a list of candidate corrections, and sorts them by probability, and the probability scores are the novel contribution of this work.
Empirical Methods in Natural Language ProcessingSpelling Correction as an Iterative Process that Exploits the Collective Knowledge of Web Users.
212 Citations2004Silviu Cucerzan, Eric Brill
This paper presents an approach that uses an iterative transformation of the input query strings into other strings that correspond to more and more likely queries according to statistics extracted from internet search query logs.
Pronunciation modeling for improved spelling correction
190 Citations2001Kristina Toutanova, Robert C. Moore
The proposed method builds an explicit error model for word pronunciations by modeling pronunciation similarities between words and achieves a substantial performance improvement over the previous best performing models for spelling correction.
IGI Global eBooksWeb Usage Mining in Search Engines
40 Citations2011Ricardo Baeza‐Yates
This chapter focuses on Web usage mining of logs of queries and user clicks to improve search engines and Websites and considers other kinds of Web mining such as link analysis, content mining, or Web dynamics.