ngram overlap

Find Levenshtein distance (Edit distance) to every dictionary term.

Enumerate all the ngrams in the query string as well as in the lexicon.

Use the ngram index (wildcard search to retrive all lexicon terms) matching any of the query ngrams.

Threshold by no. of matching ngrams.

weight by keyboard layout, assume initial letter correct, etc…

We can use Jaccard coefficient