Spelling suggestion is a feature of many computer software applications used to suggest plausible replacements for words that are likely to have been misspelled. Spelling suggestion features are commonly included in Internet search engines, word processors, spell checkers, medical transcription, automatic query reformulation, and frequency-log statistics reporting. Algorithms Any spell checker must have some data about the words in the target language, either in general usage or with specialized knowledge (like medical vocabulary). This can come from: A dictionary of all known words. A text corpus which includes typical text, known to be correctly spelled. A list of frequently misspelled words, mapping errors to corrections. Logs of human text input, such as from a popular search engine. This is essentially a crowdsourced corpus, but it is assumed there will be some spelling mistakes. Data might be included about when people click on a spelling suggestion or make a second, very similar query; this creates a crowdsourced mapping of misspelled words to reliable corrections. A list of frequently misspelled words, possibly including multi-word phrases, can simply be consulted to see if any of the input words or phrases are listed. To make use of a dictionary without a pre-existing mapping from misspellings to corrections, the typical technique is to calculate the edit distance between an input word and any given word in the dictionary. The Levenshtein distance metric considers an "edit" to be the insertion, deletion, or substitution (with another letter) of one letter. The Damerau–Levenshtein distance adds transpositions (the swapping of neighboring letters). Dictionary words that are an edit distance of 1 away from the input word are considered highly likely as corrections, edit distance 2 less likely, and edit distance 3 sometimes included in suggestions and sometimes ignored. A text corpus can be summed up as a dictionary of known words, with a frequency of appearance for each word. This can be used to sort the spelling suggestions. For example, if there are multiple suggestions of edit distance 1, the words that appear most frequently in the corpus are most likely to be the desired correction. Because a dictionary of known words is very large, calculating the edit distance between an input word and every word in the dictionary is computationally intensive and thus relatively slow. Various data structures can be utilized to speed up storage lookups, such as BK-trees. A faster approach adopted by Peter Norvig generates all