24
$\begingroup$

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.

Improve this question
$\endgroup$
0
16
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ All I know about metric spaces is from semantics, so a question: are there any decent (for any value of decent) embeddings of the Levenshtein metric into an ultrametric? Offhand, that might give a rise to binary-tree-ish algorithm. $\endgroup$ – Neel Krishnaswami Jan 7 '11 at 20:40
  • $\begingroup$ I'm not entirely sure. I suspect the answer is no in general, but I have nothing to point to. $\endgroup$ – Suresh Venkat Jan 7 '11 at 22:00
  • $\begingroup$ The second paper on boytsov.info/pubs is a good survey of possible solutions for near-neighbor search under the Levenshtein and Damereau-Levenshtein edit distance. $\endgroup$ – a3nm Aug 31 '12 at 15:34
  • $\begingroup$ @NeelKrishnaswami An embedding into an ultrametric would have distortion at least $\Omega(\log d)$ where $d$ is the string length. This follows from a distortion lower bound for embedding into $L_1$ due to Krauthgamer and Rabani, since ultrametrics embed isometrically into Euclidean space, which embeds isometrically into $L_1$. $\endgroup$ – Sasho Nikolov Sep 4 '18 at 6:04
9
$\begingroup$

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

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

Improve this answer
$\endgroup$
1
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
4
$\begingroup$

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$.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't understand this answer. The question asks how one can efficiently find a word in a large dictionary with close Levenshtein distance to a given input, not about how to compute the Levenshtein distance or about comparison to the output of a black box spell checker... $\endgroup$ – Huck Bennett Jan 7 '11 at 21:51
  • $\begingroup$ @Huck Bennett: I thought @Grigory Javadyan is building Did you mean? feature. Besides Did you mean? returns the word that is very close to the given input and does it pretty efficiently. :) $\endgroup$ – Pratik Deoghare Jan 7 '11 at 22:08
  • $\begingroup$ I think your ideas are good, but it seems that Grigory is asking for something deeper and more specific. $\endgroup$ – Huck Bennett Jan 8 '11 at 9:11
  • $\begingroup$ @Huck Bennett: Yes you are right! :) $\endgroup$ – Pratik Deoghare Jan 8 '11 at 9:17
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ How do you train a ML model so that words that are nearby in Levenshtein distance map to similar vectors? What training procedure and loss function do you use for that? Can you summarize the method in your answer, so that the answer is still useful even if the link stops working, and so that we don't have to dig through your notebook to understand the method you are using? Also, can you evaluate how well it works in some quantitative way? Is this better than the alternatives? $\endgroup$ – D.W. Sep 4 '18 at 4:35
  • $\begingroup$ As it stands, this is (I think) a poor fit for CSTheory. That is, no idea of what is specifically suggested, and no theoretical justification for it. $\endgroup$ – Clement C. Sep 4 '18 at 6:06
  • $\begingroup$ @D.W. Sorry about that--I've made a pretty substantial edit which should be comprehensive incase the link goes down (or incase you don't want to poke through the notebook). Although this isn't really CS theory because it's not research, I do think it's a practical approach because it's fast and easy for both training and inference. $\endgroup$ – michaelsnowden Sep 5 '18 at 21:29
  • 1
    $\begingroup$ You are training on random strings. The expected Levenshtein distance between two such strings will be approximately the length of the longer string. Thus, it's very easy to estimate this distance on random strings, but that's not useful for dealing with real-world data. I suspect your embeddings might just encode the length of the string, and thus you might have built a fancy way to do something trivial and useless. This is a problem with using ML; it is very sensitive to the loss function you use. $\endgroup$ – D.W. Sep 5 '18 at 22:03
  • $\begingroup$ @D.W. If you look at the results in the notebook, the retrieval ended up returning decent results--not just strings of the same length. I would really encourage you to skim it. I wouldn't call it trivial and useless. $\endgroup$ – michaelsnowden Sep 5 '18 at 23:15

Your Answer

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