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