Introduction to Tries • Hacker News Board

Re: Introduction to Tries

#11

Post by shadytrees » Mon, Aug 23, 2010, 1:20 PM UTC

Robin_Message wrote: post #4

praptak wrote: post #2

"First, lookup time is O(1) in the size of the trie." The article skims over the tricky part - the dependency on the size of the alphabet. Which you can no longer treat as insignificant in the days of unicode.

Good luck building a Unicode trie -- the branching factor would be too high, never mind lookup time. Instead, you'd make the trie of an encoding, probably UTF-8 (off the top of my head) that would enable you to keep the branching factor at 256, which is already rather large but doable (You can switch to Judy arrays if the wasted space bothers you.) Does anyone know, is there a Unicode encoding that enables you to map…

Ternary search tries attempt to solve this problem (among others):

http://en.wikipedia.org/wiki/Ternary_search_tree

http://www.strchr.com/ternary_dags

Re: Introduction to Tries

#12

Post by Roboprog » Mon, Aug 23, 2010, 1:38 PM UTC

praptak wrote: post #2

"First, lookup time is O(1) in the size of the trie." The article skims over the tricky part - the dependency on the size of the alphabet. Which you can no longer treat as insignificant in the days of unicode.

Well, the version of this I did in C for the shop I was at about 10 years ago had a "memcmp"-like interface. Just pass in a pointer to the start of the bytes (int, asciiz, unicode if you will) and the length.

I also dynamically allocated the key/pointer arrays within each node so that while it was sparsely populated, it was only big enough to hold the largest byte defined in that node (e.g. - 'A' = (char) 65, so byte positions 0 to 65 would be present, but not 66 to 255 until needed.

I was nice to see the impression of my coworkers when a bunch of qsort() / bsearch() code was replaced with this. We could afford the memory, and the speedup was fairly impressive.

Re: Introduction to Tries

#13

Post by carterschonwald » Mon, Aug 23, 2010, 3:06 PM UTC

for an excellent example of a trie implementation, the haskell bytestring trie datastructure is really nice to look at. Its docs can be found at http://hackage.haskell.org/package/bytestring-trie and the very readable sourcecode at http://hackage.haskell.org/packages/archive/bytestring-trie/...

edit: note that its not strictly a trie, but can be used as one, in general its more like it does a trie-like key value lookup.

edit: it is also worth noting that its pretty fast, counting reading data in from the file system and other overhead, loading 1.5 million key - value pairs of realworld production data into the trie, and then making my first query, in under 30 seconds. And thats without even doing the sort of preprocessing that can make it much much faster! (namely, lexigraphically sorting the strings I'm using as keys before doing the k-v insertions)

Re: Introduction to Tries

#14

Post by VolatileVoid » Mon, Aug 23, 2010, 3:11 PM UTC

This is interesting. I wonder if you could use the a similar algorithm for mapping sentences. That is, construct a ternary DAG and keep inserting words (rather than letters) into the trie.

Re: Introduction to Tries

#15

Post by silentbicycle » Mon, Aug 23, 2010, 3:23 PM UTC

VolatileVoid wrote: post #14

This is interesting. I wonder if you could use the a similar algorithm for mapping sentences. That is, construct a ternary DAG and keep inserting words (rather than letters) into the trie.

Yes, of course. You can index tries with pretty much anything, though elements with constant-time comparison (individual bytes/chars, pointers, hashes, etc.) will have less overhead.