Shutterstock, Inc.
Edit distance based spellcheck

Abstract:

Various aspects of the subject technology relate to systems, methods, and machine-readable media for edit distance based spellcheck. A system may include a search engine using edit distance based spellcheck covering a set of valid words in a language model describing probabilities for each candidate word. The subject system first identifies strings that are one edit away from a source word, selects at least one of the strings with the highest probability in the language model and uses that selected string as the spelling correction. If there are no valid words found, the subject system determines the edit distance between the source word and all candidate words in the language model whose length differential with the source word is smaller than a threshold and whose first character is the same as that of the source word, and selects the candidate word with the highest language probability and lowest edit distance.