Efficient data structures for building a fast spell checker I'm trying to write a spell-checker which should work with a pretty large dictionary. I really want an efficient way to index my dictionary data to be used using a Damerau-Levenshtein distance to determine which words are closest to the misspelled word.

I'm looking for a data structure who would give me the best compromise between space complexity and runtime complexity.

Based on what I found on the internet, I have a few leads regarding what type of data structure to use:

Trie



This is my first thought and looks pretty easy to implement and should provide fast lookup/insertion. Approximate search using Damerau-Levenshtein should be simple to implement here as well. But it doesn't look very efficient in terms of space complexity since you most likely have a lot of overhead with pointers storage.

Patricia Trie



This seems to consume less space than a regular Trie since you're basically avoiding the cost of storing the pointers, but I'm a bit worried about data fragmentation in case of very large dictionaries like what I have.

Suffix Tree



I'm not sure about this one, it seems like some people do find it useful in text mining, but I'm not really sure what it would give in terms of performance for a spell checker.

Ternary Search Tree



These look pretty nice and in terms of complexity should be close (better?) to Patricia Tries, but I'm not sure regarding fragmentation if it would be better of worse than Patricia Tries.

Burst Tree



This seems kind of hybrid and I'm not sure what advantage it would have over Tries and the like, but I've read several times that it's very efficient for text mining.



I would like to get some feedback as to which data structure would be best to use in this context and what makes it better than the other ones. If I'm missing some data structures who would be even more appropriate for a spell-checker, I'm very interested as well.
I've encountered same problem, but took different approach.
You can construct some kind of "hash" function, which will for similar word give same or near number.

Problem is, that function which will give "good" result for words with inserting/removing, will give "bad" for transition, and vice versa.
Example: map letters to numbers, similar letter to adjacent numbers, and just sum them for every letter in word.
Then create hash-tables with sets for each key and find intersection for word.

May be some results can be achieved if we look at "space" оf words. X for changing letter, Y for adding/removing, Z for transition, or something like that.

However this is only abstract ideas, I haven't enough time to implement them.