12
$\begingroup$

I understand the textbook explanation of how to use dynamic programming to find the minimum edit distance between 2 strings but how do we get to pick the 2nd string?

I don't think the entire dictionary is compared as sometimes the difference is either in the middle or the end. I assume that in the end, what is suggested is the string that has the minimum edit distance after creating a certain number of $n \times m$ tables, where $n$ is the typed string length and $m$ is that of the other words that may be close.

$\endgroup$
24
$\begingroup$

Yes, the entire dictionary is compared against each word. This can be fast by using a trie and an algorithm similar to Levenshtein's.

I have built my own spelling corrector that checks words against a dictionary of about 1 million words and 12.5 million word-pairs (for basic word usage checking). It takes about 0.7 milliseconds to check a single word and provide corrective suggestions based on these two dictionaries. I'm sure it could be significantly faster; I stopped optimizing once it became fast enough for my purposes, which was to check a few paragraphs in under 1 second.

Several of the other answers have hinted toward how spelling and grammar checkers/correctors work, but let's put all the pieces together and see how we could build our own fast spelling corrector.

Disclaimer: I don't know if this is how Microsoft and Google actually do it, but it works very well for my needs.

How to build a spelling corrector

I started from this excellent article by Peter Norvig. It's worth a read if you're serious about implementing your own spelling corrector, but the most important insight is the use of Bayes' Theorem to decompose the question into independent parts. Let's start by actually stating our goal.

Goal: given the user typed word $w$, find and rank the most likely possibilities for what the user actually meant to type, $c$ ("candidate"). In other words, for each $c$ in our list of 1 million candidates, we are looking for the probability that the user wanted to type each $c$ when they actually typed $w$. Norvig's insight is to use Bayes' theorem to turn this into manageable independent sub-problems:

$$ P(c|w) = \frac{P(c)P(w|c)}{P(w)} $$

Where:

$P(c|w)$ = the probability the user meant $c$ when they actually typed $w$ (our goal)

$P(c)$ = the probability of typing $c$. This is simply a measure of the frequency of the candidate word in our language model. For example, in English, P("the") is larger than P("thaw").

$P(w|c)$ = The probability that the user would type $w$ when they meant $c$. This is our error model. For example, the probability the user would type "thew" when they meant "thaw" is probably higher than typing "thew" when they really meant "the".

$P(w)$ = The probability of typing $w$. We're simply not interested in any cases where $w$ was not typed, because we observe that it was. Therefore this value is basically 1 (or at least constant) for our purposes and we divide it out.

Since we're just trying to rank suggestions relative to each other, I'm not going to worry about making sure the probabilities actually add up to 1.

Levenshtein distance is an error model. We could say that that $P(w|c)$ = $Levenshtein(w,c)$ and we get a perfectly serviceable error model. It might even be the best we can do in some cases, e.g. if we're trying to reconstruct English text that was sent over a noisy line that caused essentially random insertion, deletion, and replacement errors. However, for a human typist, we can do better by taking into account common language-specific errors. For instance, accidentally replacing an "e" with an "a" is much more likely than with an "m". As gnasher729 pointed out, we could also take the user's keyboard layout into account.

Generating Candidate Words

Now we can get to the heart of your question: how do we generate candidates to check? Every word in our dictionary is a candidate! If we try to do this with a naïve brute-force approach, we can think of some obvious waste. For instance, we shouldn't need to fully evaluate the word "continuations" if we've already evaluated "continuation"; this hints that a Trie (or "prefix tree") might help us here. We also probably shouldn't be comparing the "s" in "continuations" against the "y" in "specificity"; surely we know by that point that neither is a good substitute for the other! This hints that we can significantly cull down our search for candidates if we keep track of compounding error while doing our search.

So our steps are:

Step 1. Organize your dictionary into a giant trie

Let's say our dictionary consists of the 12 words shown below. The corresponding trie is shown to the right. We also want to keep track of which nodes are word endings, which I've given a solid blue color:

An example trie with 12 words

Even with 1 million words, this data structure is only a few hundred megabytes and fits easily into memory. (The n-grams are the memory hogs!)

Step 2. Calculate compounding error while searching for suggestions

Let's say the user writes "saken", and we want to suggest corrections from this dictionary. We keep a list of 3-tuples containing the following information:

  1. Where we are in the word
  2. Where we are in the trie
  3. The total compounded error so far

This list starts with one entry: (first letter, root of trie, 0), as shown below.

starting conditions of using a trie to check a misspelled word

Until we have an empty list, we loop over every element in the list. If it's a valid word (that is, the trie pointer is pointing to a node marked "end-of-word"), we return it as a possible suggestion, along with its error. Then (valid word or not) we remove it from our list and use it as a new seed to continue to populate the list.

Given a starting 3-tuple as a seed, we add new elements to the list differently for each type of error (insertion, deletion, and substitution). For instance, when checking for substitution errors, we add an element for every child of our current trie node, with additional error based on the letters being substituted (taking into account surrounding letters as well). This is illustrated below for the "a" node, but we do the same for every other child. Of course, substituting "s" for "s" gets an error value of 0.

a substitution error

We always have a single possible insertion error, which is the letter we're currently on. In that case, the word-pointer moves forward, but the trie-pointer stays where it is. Deletions are the opposite: the word-pointer stays where it is, while the trie-pointer moves forward (to every child).

Here's an example traversal with mixed errors. Here we are considering the possibility that the user accidentally typed "s" instead of "t", then correctly typed "a", then accidentally inserted a "k", then accidentally type "e" when they meant to type "k". In reality, only the last row would be left in our list, but the others are left for illustration.

enter image description here

If we're using a simple Levenshtein distance error model, then our total error so far is 3.

Of course it's more likely that the user actually did mean "ke" at this point, but our job right now is to simply enumerate and score all the possible ways $w$ could have been typed instead of $c$.

Step 3. Stop traversing your trie if the error gets too large

Now that we're calculating errors as we're generating suggestions, we can simply refuse to add a new 3-tuple to our list if the total error is too high (notice the error never decreases). That culls entire branches of the trie from future traversal and keeps our search narrowly focused.

In fact a rather small limit works well here if errors are reasonably independently distributed (an example where they're not is keyboard off-by-one errors like gnasher729 demonstrated, but you could make a custom error type with its own traversal logic for this). If I have a 5% chance of making a single typo in a 6-letter word, I probably have about a (5%)^2 = 0.25% chance of making two typos in that same word. Therefore an error limit of about 3 is good enough in practice (with Levenshtein distance; obviously this depends on your error model), and significantly reduces your search space.

Another way you can cull your search is by only ever considering the shortest path (error-wise) to a given suggestion. If you implement this, you'll find you get lots of cases where the same word is being suggested via many different paths, and you really only need to keep one as your next seed.

Once you have your list of suggestions, you already have $P(w|c)$ calculated for each, so you simply need to look up $P(w)$ and you're done! In my implementation, this all happens in about 0.7 milliseconds (700 microseconds) per word, including an additional step where I account for the frequency of the word appearing next to its neighbors. There are lots of parameters you can tune to your needs, and probably lots of other ways to make this faster.

$\endgroup$
4
  • $\begingroup$ Clear explanation! I suspect that there are some errors > 3 that are likely, because of certain character combinations in English; the rare 'sch' string in a target word, for example, followed by a vowel (with vowel confusions being common--English has > 20 distinct vowels, but only five vowel letters). It would be possible to set up your trie so that 'sch' counts as a single letter, thereby reducing the error count when someone types a different string for that. $\endgroup$ Sep 7 at 13:59
  • 1
    $\begingroup$ @MikeMaxwell I'm sure that's true, but what you're really saying is that that type of error should get a low score; it's a good example of why Levenshtein isn't great in practice. The problem with coding something like 'th' as a single letter in your trie is that you'd have to know ahead of time if it's a digraph ("bath") or a compound word ("foothold"), which means a lot more work generating your dictionary. But you could also try coding it both ways and taking both paths. $\endgroup$ Sep 7 at 15:12
  • $\begingroup$ @JounceCracklePop: At least for 'th' (and 'sh'), the overwhelming majority of instances of that sequence of letters represent the digraph. But yes, there are lots of digraphs and even trigraphs in English (particularly vowels) that you'd have to be wise about encoding. Fortunately, there are also lots of free pronunciation dictionaries. $\endgroup$ Sep 8 at 19:43
  • $\begingroup$ @EricTowers Good catch! I've made that correction. $\endgroup$ Sep 8 at 22:39
19
$\begingroup$

Companies with search engines (e.g. Microsoft or Google) don't always directly search for the string with the smallest Levenshtein distance. They have a huge database of search queries, from which they have developed a huge database of commonly misspelled/mistyped variants, and what word the user probably meant to type instead.

They also have a huge corpus of text, and can use this to (for example) predict which word is most likely to come next based on what you've typed so far, or to assist with autocompletion. The set of likely words is much smaller than the set of possible words.

Don't underestimate the value of understanding exactly how real humans misspell or mistype things. For example, when you misspell something, you rarely get the first letter wrong, unless it's an ambiguous letter such as a vowel or "c" vs "k".

With all that said, let's assume that you're not doing any of that, and just want to find a string with edit distance as close as possible. The general idea is to find a set of candidate words first (e.g. all words within a certain edit distance, or all words with promising sub-matches), and then use some kind of finer-grained metric to decide which member of the set to suggest.

A simple approach is to use a trie, such as a ternary search trie. Another option is to combine k-mer matches.

$\endgroup$
5
  • $\begingroup$ Does this mean that Levenshtein distance isn't as practical in the real world? $\endgroup$ Sep 6 at 9:47
  • 3
    $\begingroup$ @heretoinfinity Do you mean in this particular application? or more in general? If the latter, Levenshtein distance definitely has its practical uses; it's commonly used in software that has to compare genetic sequences $\endgroup$
    – anjama
    Sep 6 at 11:41
  • $\begingroup$ @anjama, I meant both. $\endgroup$ Sep 6 at 14:45
  • 2
    $\begingroup$ Levenshtein distance is also the basis behind the diff algorithm, used in source control systems. For spelling correction, Levenshtein distance is one factor out of several that make sense to consider. $\endgroup$
    – Pseudonym
    Sep 6 at 15:17
  • $\begingroup$ @heretoinfinity Also, once you’ve narrowed down your list of possibilities, it’s very likely that Levenshtein distance plays an important role in picking out which one of those possibilities to go with. $\endgroup$
    – KRyan
    Sep 7 at 1:22
8
$\begingroup$

I just tried and found that the spelling checker on my phone finds a perfectly fine replacement for “gekki wirkd”. Look at your keyboard, and it is obvious.

A good spelling checker does much better than using Levenshtein distance. For example it will use keyboard distance, assuming your fingers typed the wrong letter. It knows grammar. It knows which words tend to follow which other words.

It knows which words are rarely used. Like “wether” which is a perfectly fine English word but very likely not the one you wanted. It will know where to use there, their or they’re if it’s clever. I actually typed “its clever” and the spelling checker fixed it.

All in all, writing a good spelling checker will take you ages of full time work.

$\endgroup$
2
  • $\begingroup$ Did you mean ‘Gwkki, qieks’? $\endgroup$
    – gidds
    Sep 6 at 23:09
  • 2
    $\begingroup$ @gidds "gekki wirkd" is what you get if only your right hand is one key to the left. Yours is what you get if both hands are one key to the left. Not a correction, just a different example. $\endgroup$
    – Ben
    Sep 7 at 0:19
2
$\begingroup$

There are many ways to organize data to optimize queries.

Regarding text search the classical way is to build a Suffix Tree. This allows to perform searchs in a big text with the time proportional to the pattern length, instead of the text length.

You can think about a Suffix Tree as some sort of database that performs pattern queries really fast.

The companies you mentioned wont use a classical Suffix Tree, they are probably using some more complicated, distributed proprietary data structures in order to optimize the lookups, however the point remains the same:

they trade time for space, so the have pre-build indexes/data structures/DBs that make typical search queries really fast.

Moreover they also cache a lot of search queries, so common queries don't actually have to really search the database.

The same is true for keyboards, they can take a dictionary with all English words and organize it so that when you type they can easily find the closest matches, and maybe sort them by how frequently they are used... no need to compute any form of edit distance at all.

$\endgroup$
4
  • $\begingroup$ Since the question explicitly mentions edit distance a Levenshtein Automaton is probably a better example than a suffix tree for this specific case. $\endgroup$ Sep 6 at 8:54
  • $\begingroup$ @SriotchilismO'Zaic Yes and no. It only applies regarding spelling suggestions, but is not useful to search inside a whole document. I wanted to give a broader picture that I feel was missing from the other answers. a Suffix Tree could be used for both cases, although the suggestions are easier to lookup with exact substring matches instead of levenshtein distance differences (but not impossible to do). $\endgroup$
    – GACy20
    Sep 6 at 9:20
  • $\begingroup$ Just as an added note, compressed suffix arrays (CSAs) and FM-indexes are two suffix-tree-adjacent data structures which are in common use today, especially in bioinformatics. The "spelling error problem" turns out to be very similar to the RNA-seq problem. $\endgroup$
    – Pseudonym
    Sep 7 at 0:12
  • $\begingroup$ These data structures, and their use in computational biology, are the subject of Dan Gusfield's book "Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology". There are differences between RNA/DNA sequencing and natural language spell correction which can make a difference in which algorithms are the most useful--RNA/DNA only have 4 characters in their "alphabet", for example, while the minimum in human languages is 12 (Rotokas), and most languages have at least 20-some. $\endgroup$ Sep 7 at 14:06
0
$\begingroup$

The Damerau-Levenshtein distance metric is a function that measures a distance between two strings, A and B, and, importantly, satisifes (quoting from Wikipedia)

  1. the distance from A to B is zero if and only if A and B are the same point,
  2. the distance between two distinct points is positive,
  3. the distance from A to B is the same as the distance from B to A, and
  4. the distance from A to B is less than or equal to the distance from A to B via any third point C.

This makes it ideal for consumption in a number of data-structures that are optimized for searching metric spaces.

For instance, the Burkhard-Keller tree is well suited for nearest-neighbor type searches in metric spaces and make for speedy retrieval of neighbors without comparison to the entire lexicon.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.