3 ms·
I thought one advantage of Tries over Hash tables is fast prefix searching.
by afsina 11y ago
I thought one advantage of Tries over Hash tables is fast prefix searching.
- tgarv 11y agoYeah that's definitely the case. This test was for string interning though, so I assume the prefix checking wasn't really necessary so the trie doesn't gain any advantage from having that capability (though I admit I wasn't familiar with the concept of string interning before reading this post so I could be missing something).
- alienasa 11y agoIt seems to be that you've hit the nail on the head: Hash Tables are faster than Tries when your only requirement is that you don't duplicate storage.
- magicmu 11y agoI 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.
- kazinator 11y agoBut the point of interning is that you're reducing the strings to atoms (perhaps represented as machine words such as pointers). Whereas a prefix search says, no, the items are not atoms, they have a structure which we can divide into a prefix and as suffix, which are independently significant in some way that we need to search for one or the other. If this is for the identifiers in a programming language which has some hacky reflection features (like iterate over all class methods that begin with "Get"---some aspect-oriented programming systems come to mind here) then it could help to have a fast prefix search (assuming the performance of that even matters).
- SEJeff 11y agoThat is the perfect use case for tries. For reference (and an excellent writeup): http://blog.vulcanproxy.com/trie-based-http-requests-routing/ http://blog.vulcanproxy.com/trie-based-http-requests-routing...