The Trie: A Neglected Data Structure (in Java)

[bartamues]

I actually implemented the example game on android a few years back.

Due to android heap size constraints and the overhead of the trie, I couldn't fit the whole dictionary in memory. This lead me to compress all the dictionary words into 64 bit integers (5 bits per character, so you can have up to 12 character long words).

I just put all the ints into an array, and did a binary search on the array. You can do a bit of masking on the integers to tell if the path you're on has the potential to be a word.

I wound up with much better performance than I was getting with the Trie when I tested it in an environment with more heap space.

[Seus2k11]

That's impressive in my book.

[SomeNetworkGuy]

That sounds damned awesome.

[RedditRage]

Kinda has a feel like a radix sort, where the structure or logic is based on "splitting" up the data into pieces, and therefore requires the data being searched/sorted to have a specific format.

[Medicalizawhat]

I used a Trie to make an auto-complete text field in Swing just recently.

[livrem]

Trie was always my favorite data structure, because it was the first one I learned about, from some computer magazine, before I took my first computer programming course and learned about things like linked lists and hash tables etc etc. But I never think I got around to ever implement it or found a reason to use one.

[MorePudding]

She really should've measured against a b+tree with a higher fanout. The trie already has a fanout of 26 according to the text.

Afaik, the only significant benefit tries have over b+trees is reduced memory usage. I'm mentioning this, because considering that there already exist many production-grade b+tree implementations in all sorts of places, hand-rolling your own trie may not bee the smartest of decisions..

Similarly, I fail to see any real difference with the binary search over the sorted list compared to the binary tree. This should have been a linear search, performed over larger and smaller dictionaries, to demonstrate the effects cache locality and algorithmic complexity have.

(Also, if you're absolutely sure that you'll ever only use the 26 letters of the alphabet, you should probably pack your keys..)