Computing the Levenshtein distance quickly

Question

Given a huge database of allowed words (alphabetically sorted) and a word, find the word from the database that is closest to the given word in terms of Levenshtein distance.

The naive approach is, of course, to simply compute the levenshtein distance between the given word and all the words in the dictionary (we can do a binary search in the database before actually computing the distances).

I wonder if there is a more efficient solution to this problem. Maybe some heuristic that lets us reduce the number of words to search, or optimizations to the levenshtein distance algorithm.

Links to papers on the subject welcome.

Answer 1

What you are asking about is the problem of near-neighbor search under the edit distance. You didn't mention whether you're interested in theoretical results or heuristics, so I'll answer the former.

The edit distance is somewhat nasty to deal with for building near-neighbor search structures. The main problem is that as a metric, it behaves (sort of) like other well known bad metrics like $\ell_1$ for the purpose of dimensionality reduction and approximation. There's a rather vast body of work to read on this topic, and your best source is the set of papers by Alex Andoni: by following pointers backward (for example from his FOCS 2010 paper) you'll get a good set of sources.

Answer 2

Levenshtein automatons: http://en.wikipedia.org/wiki/Levenshtein_automaton

BK trees: http://en.wikipedia.org/wiki/BK-tree

Answer 3

If you have a small number of mis-edits that you are going to tolerate, then you can try to use a dotted suffix tree. Disclaimer: I wrote that paper, but it solves what you want: it has a high disk space cost, but queries are really fast.

In general, it is better to look at it the other way around: you have an index of all of the words in the dictionary. Now, for an input word w, if it is in the dictionary, stop. Otherwise, generate all variations at distance 1 and look for those. If they are not there, look for variations at distance 2, and so on...

There are several improvements to this basic idea.

Answer 4

A simple solution is to store the words as a trie. You can then compute the Levenshtein distance of the query word against the trie with the standard dynamic programming algorithm, instead of computing it against each word separately. The worst case time complexity is not improved asymptotically, but if you expand the most promising branches first, you get something like $O(m^{k+1} \cdot \sigma^{k})$ time for query length $m$, alphabet size $\sigma$, and edit distance $k$.

Answer 5

I wrote an answer to a very similar question at cs.stackexchange.com (https://cs.stackexchange.com/a/2096/1490) and then I found this question. The answer there is for approximate near neighbor search in the edit distance (i.e. the algorithm outputs a string which is approximately as close to the query string as the nearest neighbor of the query string). I am posting here since I am not finding any of the references I gave there in the answers given here.

Answer 6

I think what you want is the Wagner-Fischer algorithm: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm The key insight is that, since the dictionary you are traversing through is sorted, two consecutive words are very likely to share a long prefix so you don't need to update the whole matrix for each distance calculation.

Answer 7

You can use Did you mean?

And then find the Levenshtein distance between the answer returned by "Did you mean"" and input string using Dynamic Programming.

Answer 8

One way is to train a machine learning model to map the words to vectors and map the levenshtein distance to the euclidean distance. Then you can build a KDTree out of the vectors for the dictionary you want to use. I created a jupyter notebook that does this here: https://gist.github.com/MichaelSnowden/9b8b1e662c98c514d571f4d5c20c3a03

As per D.W.'s comments:

1. training procedure = stochastic gradient descent with adaptive gradients
2. loss function = mean squared error between true edit distance and euclidean distance
3. training data = random strings between 1 and 32 characters long (could be improved with data that matches an actual distribution of common typos)
4. quantitative results: After training for roughly 150 epochs with a batch size of 2048 (wall time = approximately one minute), using word embeddings of 512 dimensions, with one hidden layer, the average absolute error between the true edit distance and the predicted edit distance sits at around 0.75, meaning the predicted edit distance is roughly one character off

Summary of the model structure:

1. Create a learned embedding for each character, including the null character (used later to right-pad text under the character limit)
2. Pad the right side of the text with the null character until it is at the character limit (32)
3. Concatenate these embeddings
4. Run the embeddings through a feed-forward neural net to produce a lower-dimensional word embedding (512-dimensional)
5. Do this for both words
6. Find the euclidean distance between the vectors
7. Set the loss to be the mean squared error between the true Levenshtein distance and the euclidean distance

My training data is just random strings, but I think the results could really improve if the training data was (typo/correct word) pairs. I ended up just using /usr/share/dict/words because it's commonly available.