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.