Tries are a very interesting data structure. Tries are designed to compress string prefixes
to allow the storage of large string datasets in a memory-efficient manner.
Tries are built as trees of substrings. In fact, the word "trie" was selected because the
word "tree" was already taken; initially trie was pronounced identicially as tree, but
spelled differently to differentiate the two structures.
There are many different flavors of trie, each with different trade offs.
# Static Tries
# Dynamic Tries
* Array Trie
* Patricia array
* Burst Trie
* HAT Trie
* Judy
* B-Trie
* Suffix Trees
* LOUDS-Sparse / LOUDS-Dense / Surf
* Radix Trie
* Compact Trie
* R-way Trie
* De la Briandais Trie
* List Trie
* Ternary Search Trie
* Double-array
# Node Label Map
In practice, most tries don't actually store the characters on each node, but instead
store them in a Node Label Map, which is a data structure mapping from unique integer IDs
to substrings.
There are different NLM implementations, each again offering different trade-offs.
* m-Bonsai
* FK-hash