Match dictionary to misspelled word, corner cases 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..
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.