The trie is my favorite data structure. It allows you to build inverted indices (i.e. hashmaps) that can also be used for prefix lookups of tokens and for spell

The trie is my favorite data structure. It allows you to build inverted indices (i.e. hashmaps) that can also be used for prefix lookups of tokens and for spelling/typo correction. With a trie, it's very efficient to calculate Levenshtein distances. Here's a post (http://stevehanov.ca/blog/?id=114 http://stevehanov.ca/blog/?id=114) that has a good primer on that. If you love this sort of thing, here's a fast and neat memory efficient Trie variant: https://db.in.tum.de/~leis/papers/ART.pdf https://db.in.tum.de/~leis/papers/ART.pdf (Adaptive Radix Tree). I've used ART as a building block to create an open source typo tolerant search engine called Typesense (https://github.com/typesense/typesense https://github.com/typesense/typesense).