Comment on The Trie: A Neglected Data StructureComments−fogleman12yShould mention that tries can be heavily compressed into DAWGs (Directed Acyclic Word Graphs) by eliminating common subtrees. I've used this in word games on iOS where I want a small memory footprint.P.S. I love tries!−nathell12y"How to Squeeze a Lexicon" by Ciura and Deorowicz [1] is a good and practical introduction to DAWGs.[1]: http://sun.aei.polsl.pl/~mciura/publikacje/lexicon.pdf
Comments
Should mention that tries can be heavily compressed into DAWGs (Directed Acyclic Word Graphs) by eliminating common subtrees. I've used this in word games on iOS where I want a small memory footprint.
P.S. I love tries!
"How to Squeeze a Lexicon" by Ciura and Deorowicz [1] is a good and practical introduction to DAWGs.
[1]: http://sun.aei.polsl.pl/~mciura/publikacje/lexicon.pdf