Re:String Interning – Trie vs. Hash Table Deathmatch
by birdsbolt on Monday June 29, 2015 @05:13PM
(#9801136)
Large dictionaries (set of words) can compactly be represented with tries.
For words with similar prefixes and suffixes directed acyclic word graph is a much better option (reuses prefixes and suffixes, not just the prefix as in trie), it's a little bit slower to build but fast to traverse if done right.
Any problem where there's a lot of suffix/prefix reusage benefits from a proper trie implementation (or suffix array/tree as alternative) - ex. lempel-ziv compression.
For words with similar prefixes and suffixes directed acyclic word graph is a much better option (reuses prefixes and suffixes, not just the prefix as in trie), it's a little bit slower to build but fast to traverse if done right.
Any problem where there's a lot of suffix/prefix reusage benefits from a proper trie implementation (or suffix array/tree as alternative) - ex. lempel-ziv compression.