Abstract

Spell checking is the problem of correcting an input word to an intended word. We shall first consider the case where the input word is not a dictionary word, and then show how the techniques here can be extended to enable the correction of dictionary words.

The Damerau-Levenshtein edit distance measures the distance between two strings, and can be used to implement a basic spell checker for non-dictionary input words. The talk introduces GNU Aspell as an extension of this basic implementation, taking phonetics into account. An important feature of a spell-checker is the ability to rank suggestions to the user. We shall see how the edit distance metric can be extended to provide this ranking.

In the case where the input word is in the dictionary, probabilistic techniques can be used to generate and rank candidate sentences. Suggestions of potential intended words can then be made to the user.