A Trie is a multiway tree that can be used to store dictionaries. There are several uses for this data structure. One of them is the word completion look up that most cell phone text message applications use. This was originally used for the T9 algorithm for supporting SMS text messaging on numeric pad phones.
The T9 algorithm is patented. With the advent of smart phones like the Android and the iPhone, which support full alphabetic entry, the application for this algorithm has fallen into disuse. Hopefully the word completion algorithm is not patented.
I thought that this was a cool algorithm. At some point I'd like to integrate it into a messaging Android App that I have in mind. But I don't know when I'll get to writing this, so, in the mean time, I've published it here.
You can download the code as a .tar.gz file by clicking here.
You can browse the Doxygen formatted documentation and code here.
Ian Kaplan, September 2013
Last revised: