1
$\begingroup$

I'm trying to think of corner-cases where I can skip having to linear-search through my dictionary in my problem; For a given word w1, find all matches with the least editing distance from it in the dictionary D (Levenshtein distance).

The dictionary can contain 500.000 words so a linear search through it can tend to be quite costly. The tricks I've come up with so far includes;

  • Check if D contains wi (distance = 0) before beginning search
  • Since a lower bound for the Levenshtein distance is abs(w1.length-w2.length) I don't calculate the Levenshtein distance for two words if their length-difference is greater than the smallest Levenshtein distance I've found so far
  • I re-use parts of my Wagner-Fischer-matrices if two words I've searched for after one another have letters in common
  • I calculate all the words you can get using one operation on wi and check if any of those are in the dictionary data structure (of the 'physical' dictionary) -> if so I return them and stop the search (since I've already checked that the word isn't in the dictionary).

Are there any more cases in where I can manage to skip searching through the whole thing? I've thought about calculating all words that you can get with a distance of two from a word, but it feels like it's too costly combinatorically..

$\endgroup$
  • $\begingroup$ Use a trie. You can lookup prefixes for words and see all possible endings. $\endgroup$ – user3853544 Feb 2 '17 at 15:18
  • $\begingroup$ Never used that data structure before, care to explain how I could use of it? $\endgroup$ – Nyfiken Gul Feb 2 '17 at 15:33
  • $\begingroup$ I could but Wikipedia will do a better job :) en.wikipedia.org/wiki/Trie $\endgroup$ – user3853544 Feb 2 '17 at 15:59
  • $\begingroup$ Right, thanks - but I'm not really sure how it'd effectivize my program since it's not only prefixes that determine the editing distance between two words. $\endgroup$ – Nyfiken Gul Feb 2 '17 at 16:08
  • 1
    $\begingroup$ You could use a suffix and a prefix tree. Maybe a combination of both to determine possible matches then sort the possible matches using Levenshtein distance $\endgroup$ – user3853544 Feb 2 '17 at 16:09
1
$\begingroup$

Are we talking about a dictionary containing words of some language? Then there are many, many tricks you can use.

Your dictionary may contain 500,000 words, but people don't use that many. And they don't make arbitrary spelling mistakes, but typically only a small number. So you could have a second dictionary containing previous results. If I enter "wierd" you find "weird" after a lengthy search, but then you add "wierd" to a second dictionary.

You can look at the word and decide what is most likely the correct spelling. Like "messsage" is probably "message", without consulting your dictionary. You could map "messsege" to "m, vowel, s, vowel, g, optional vowel", and have a second dictionary for mapped words, which would tell you that your word is likely either "message" or "massage". This will work best for complicated words that nobody knows how to spell correctly.

If you know that your word was typed on a keyboard, there are errors that are more likely than others. If you know that your word was scanned by a scanner, there's a completely different set of errors, like "wam" might really be "warn" (nobody would make that mistake typing on their keyboard). For keyboard entry, the user's fingers might have moved to a different position on the keyboard. Like "leubpard" is "keyboard" with the right hand moved one position to the right. That's a case where simple algorithms fail completely.

Split your dictionary into the 5,000 most common and the 495,000 less common words. Most likely you find a good match within the first 5,000 and can remove most items in the large list that cannot be better.

$\endgroup$
0
$\begingroup$

If you only need to find a single match: if you find a match at edit distance one, you can immediately stop without searching for any other matches -- that's the best one you'll ever find.

Why? The edit distance is a non-negative integer, so the only smaller edit distance possible is zero. However, you already checked that the word is not in the dictionary (that was your first bullet point), so edit distance is zero. That means that as soon as you find a distance-one match, you know you'll never find anything better.


Another trick: Suppose the best match you have found so far has edit distance $k$, and now you are comparing word w to word d. Then it suffices to use an "early-out" version of the edit distance computation: if the edit distance between w and d is $\ge k$, we don't care what its precise value is, as this is not a better match. This can be used to speed up the computation a little bit: rather than computing the entire matrix, we only compute the elements that are most $k$ away from the diagonal.

If you want all matches of the minimal edit distance, change $\ge k$ to $>k$.


As mentioned in my comment to your prior question, there's lots written on spelling correction and this problem. There are many data structures, algorithms, and tricks documented in the literature and online. I suggest you spend some quality time doing some research and familiarizing yourself with them.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Yes, I know, although my approach to edit-distances of 1 is as I wrote above (I generate all of them). The problem with just jumping out of the loop when I've found a one-distamce word is that I need to output all one-distance words. Thanks for the tips, have tried looking up stuff online bit will definitely try harder then! :) $\endgroup$ – Nyfiken Gul Feb 2 '17 at 19:10
  • $\begingroup$ @NyfikenGul, huh, I didn't see that anywhere in the question. Anyway, see edited answer for another trick (which is compatible with finding all words at the same distance). $\endgroup$ – D.W. Feb 2 '17 at 19:14
  • $\begingroup$ "For a given word w1, find the all matches with the least editing distance from it in the dictionary D (Levenshtein distance).". Yea, I've played around with that thought aswell - though I'm afraid it'll clash with one of the other 'mechanisms' I've implemented, ehich is that if two words D[i] and D[i+1] share the same first P letters I only need to build the matrix for D[i+1] from the (P+1)th row down (meaning I can 'reuse' the old one to some extent). Hmm, this is a really tricky one.. $\endgroup$ – Nyfiken Gul Feb 2 '17 at 19:30
  • $\begingroup$ @NyfikenGul, I don't understand what your last comment is saying or what you are responding to or how that relates to my answer. I'm not seeing a clash with the second trick in my answer. $\endgroup$ – D.W. Feb 2 '17 at 19:43
  • $\begingroup$ I wonder if I maybe could make use of the 'triangle property' somehow? I.e. L(x, y) <= L(z, y) + L(z, x). Maybe I can run that against the least-distance-matches of the previous w to get an upper bound for L(x, di)? $\endgroup$ – Nyfiken Gul Feb 2 '17 at 19:44
0
$\begingroup$

Best is pointless if best is terrible
If the distance is 20% + of the word then it is not a legitimate match

In addition to match length threshold also match letters
Say your threshold is 20% then also need 80% common letters

You would need to modify the algorithm as it does not come to an answer until the end but a form that gives up when a threshold cannot be obtained

$\endgroup$
  • $\begingroup$ I feel you, but for this specific situation I need to output the word(s) with the least editing distance from the word, however large the editing distance may be - but I agree with you that if I were to implement it for 'everyday' purposes I'd certainly have some kind of threshold! Thanks for the input :) $\endgroup$ – Nyfiken Gul Feb 2 '17 at 21:21

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.