3 ms·

Here's an interesting paper. It describes a cross between a trie and a hash table. Instead of storing the string itself in the trie, it first hashes the string

by jules 17y ago

Here's an interesting paper. It describes a cross between a trie and a hash table. Instead of storing the string itself in the trie, it first hashes the string and then stores that in a trie (in a smart way). The memory usage is claimed to be very good, and the benchmarks in the paper seem to show that it's faster than a hash table for lookup... http://lampwww.epfl.ch/papers/idealhashtrees.pdf http://lampwww.epfl.ch/papers/idealhashtrees.pdf

AlisdairO 17y ago
Thanks for the link! I'll be interested to take a look.
angstrom 17y ago
Another good example that can be more performant than a hash or a trie on a given alphabet is a directed acyclic word graph. Think of it as a trie that reuses edges, but has no cycles. This makes it very compact. There's an implementation of one here that I've messed with, but it's a little expensive on the setup side. http://www.pathcom.com/~vadco/dawg.html http://www.pathcom.com/~vadco/dawg.html The final result is that each node is stored in a 32bit word with the possible characters limited to a 5 bit field. 1 bit flag for word endings and I believe he employed offsets with the rest of the bits to perform the directed lookups of the other characters in a limited A-Z uppercase only alphabet. These types of graphs tend to extremely fast at runtime, but like I mentioned, the setup is costly. However, if you were embedding this in a device this would definitely be a worthwhile investigation. This is one of those cases where a data structure fits a very constrained, but well defined requirement.
- jules 17y ago
  Interesting. How much space saving do you see? DAWGs work for sets, but can it work for key-value maps? (I don't see how, because a final leaf can belong to multiple key prefixes, and therefore multiple associated values).

3 ms·

Here's an interesting paper. It describes a cross between a trie and a hash table. Instead of storing the string itself in the trie, it first hashes the string

by jules 17y ago

AlisdairO 17y ago
Thanks for the link! I'll be interested to take a look.
angstrom 17y ago
Another good example that can be more performant than a hash or a trie on a given alphabet is a directed acyclic word graph. Think of it as a trie that reuses edges, but has no cycles. This makes it very compact. There's an implementation of one here that I've messed with, but it's a little expensive on the setup side. http://www.pathcom.com/~vadco/dawg.html http://www.pathcom.com/~vadco/dawg.html The final result is that each node is stored in a 32bit word with the possible characters limited to a 5 bit field. 1 bit flag for word endings and I believe he employed offsets with the rest of the bits to perform the directed lookups of the other characters in a limited A-Z uppercase only alphabet. These types of graphs tend to extremely fast at runtime, but like I mentioned, the setup is costly. However, if you were embedding this in a device this would definitely be a worthwhile investigation. This is one of those cases where a data structure fits a very constrained, but well defined requirement.
- jules 17y ago
  Interesting. How much space saving do you see? DAWGs work for sets, but can it work for key-value maps? (I don't see how, because a final leaf can belong to multiple key prefixes, and therefore multiple associated values).