4 ms·
I had actually never even heard of Tries until today. Fast prefix searching makes a lot of sense; are there any other clear use cases for Tries?
by magicmu 11y ago
I had actually never even heard of Tries until today. Fast prefix searching makes a lot of sense; are there any other clear use cases for Tries?
- birdsbolt 11y agoLarge 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.
- magicmu 11y agoAhh that makes a ton of sense, thanks!
- zem 11y agomore of a niche case, but i once achieved easy concurrent writes to an rbtree by converting it into a bunch of rbtrees hanging off a two-level trie. the point was that you only need to lock the subtree you're actually editing, because since tries are never rebalanced, edits cannot propagate upwards.