Ternary search trees are really great and relatively compact. A while ago, I compared memory use of storing a dictionary (the SOWPODS word list) in Rust using various tries (as measured with the heapsize crate):
- Trie, using a HashMap to store edges: 691MB
- Trie, using a sorted Vec to store edges: 44MB
- Ternary search tree: 18MB
A typical ternary search trie is even more compact, but I implemented randomized ternary search tries, which uses two extra member variables in each node for bookkeeping (in these measurements u16s).
It's one of those data structures that makes perfect sense in CS theory but is only applicable in a limited set of real world problems.
For now we're beholden to implementation of our architectures, their quirks and side effects.
The point of suffix tries is finding substrings. I.e. build a suffix trie of all of Shakespear's works in linear time and memory (linear w.r.t. the total length of the string). And then, given a potential quote of length K, see if it is in Shakespear's work in O(K) time. The big draw there is that the complexity of string lookups does not depend on the length of the big text against which you are matching. This finds practical use in genome sequencing.
[1] Though there is an O(k) search approach too: http://www.sciencedirect.com/science/article/pii/S1570866703...
Heck, as far as I can tell, this approach is just another way of storing a tree.
I've of the more interesting data structures for things like this are Ternary Search Trees after each subtree starts with a common prefix. That would have been an interesting comparison.
https://en.m.wikipedia.org/wiki/Ternary_search_tree