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