Introduction to Tries

#1

Post by mriley » Mon, Aug 23, 2010, 7:05 AM UTC

Re: Introduction to Tries

#2

Post by praptak » Mon, Aug 23, 2010, 10:28 AM UTC

"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.

Re: Introduction to Tries

#3

Post by dustrider » Mon, Aug 23, 2010, 10:41 AM UTC

personally I prefer this intro: http://marknelson.us/1996/08/01/suffix-trees/

or this one which is slightly harder: http://linux.thai.net/~thep/datrie/datrie.html

Re: Introduction to Tries

#4

Post by Robin_Message » Mon, Aug 23, 2010, 10:42 AM 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.

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 arbitrary ranges (so I can, for example, use the greek alphabet only at 1 byte per character or less)? I suppose UTF-8 is already hard enough to decode.

Re: Introduction to Tries

#5

Post by jules » Mon, Aug 23, 2010, 10:55 AM 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…

Or you use a sparse data structure instead of an array in each node, for example a binary tree. This gives you ternary trees.

Re: Introduction to Tries

#6

Post by Deestan » Mon, Aug 23, 2010, 11:28 AM 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…

> Instead, you'd make the trie of an encoding, probably UTF-8

There are some new implications you need to account for if you do this, as you no longer have one node per letter, but a path per letter. E.g. subtrees will no longer correctly represent substrings, making autocompletion slightly trickier.

Re: Introduction to Tries

#7

Post by naz » Mon, Aug 23, 2010, 11:30 AM UTC

I've recently been working on directed acyclic word graphs. They are a small modification to tries and can be built with (I think) the same time complexity. For each node, count the distance from EOW when building, maintain a list of nodes with the same EOW distance and merge the ones that are equal strings. They use much less space by sharing suffixes as well as prefixes. http://en.wikipedia.org/wiki/Directed_acyclic_word_graph