the permutations from an input word of all possible edits. For a word of length n and an alphabet of size a, for edit distance 1 there are at most n deletions, n-1 transpositions, a*n alterations, and a*(n+1) insertions. Using only the 26 letters in the English alphabet, this would produce only 54*n+25 dictionary lookups, minus any duplicates (which depends on the specific letters in the word). This is relatively small when compared to a dictionary of hundreds of thousands of words. However, tens or hundreds of thousands of lookups might be required for edit distance 2 and greater. A further innovation adopted by Wolf Garbe, known as SymSpell ("sym" as in "symmetry") speeds the input-time calculation by utilizing the fact that only permutations involving deletions need to be generated for input words if the same deletion permutations are per-calculated on the dictionary. The algorithms described so far do not deal well with correct words that are not in the dictionary. Common sources of unknown words in English are compound words and inflections, such as -s and -ing. These can be accommodated algorithmically, especially if the dictionary contains the part of speech. These algorithms have also assumed that all errors of a given distance are equally probable, which is not true. Errors that involve spelling phonetically where English orthography is not phonetic are common, as are errors that repeat the same letter or confuse neighboring letters on a QWERTY keyboard. If a large set of known spelling errors and corrections is available, this data can be used to generate frequency tables for letter pairs and edit types; these can be used to more accurately rank suggestions. It is also more common than chance for a word to be spelled in the wrong dialect compared to the rest of the text, for example due to American and British English spelling differences. Spelling suggestions can also be made more accurate by taking into account more than one word at a time. Multi-word sequences are known as n-grams (where n is the number of words in the sequence). A very large database of n-grams up to 5 words in length is available from Google for this and other purposes. Others have experimented with using large amounts of data and deep learning techniques (a form of machine learning to train neural networks to perform spelling correction. References Internet search engines Spell checkers