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 searchSince 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 farI re-use parts of my Wagner-Fischer-matrices if two words I've searched for after one another have letters in commonI 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.. 
Match dictionary to misspelled word, corner cases
optimization;strings;dictionaries;program optimization