I have been working on a Ternary Search Trie implementation for Python on and off for a while. This is definitely a good read for some other methods for fuzzy string search. The benefits of the TST (versus other Trie formulations) is summarized on my blog.[1] I think I will do a follow up post covering their characteristics in comparison to the methods Nikita covered in this post.

The author mentions at the end that he didn't consider Tries. However, I think they are valuable data structure.

[1] http://blog.hackthology.com/ternary-search-tries-for-fast-fl...