A Fast Generative Spell Corrector Based on Edit Distance

One of the main challenges in the implementation of web-scale online search systems is the disambiguation of the user input when portions of the input queries are possibly misspelt. Spell correctors that must be integrated with such systems have very stringent restrictions imposed on them; primarily they must possess the ability to handle large volume of concurrent queries and generate relevant spelling suggestions at a very high speed. Often, these systems consist of highend server machines with lots of memory and processing power and the requirement from such spell correctors is to minimize the latency of generating suggestions to a bare minimum.

In this paper, we present a spell corrector that we developed to cater to high volume incoming queries for an online search service. It consists of a fast, per-token candidate generator which generates spell suggestions within a distance of two edit operations of an input token. We compare its performance against an n-gram based spell corrector and show that the presented spell candidate generation approach has lower response times.