|
T9
T9 Trie Word Completion Algorithm
|
Go to the source code of this file.
Classes | |
| class | t9.trie.TrieBuilder |
Packages | |
| package | t9.trie |
A string prefix "Trie", which also contains the relative frequency for each word in the Trie.
According to "Algorithms in Java", Third Edition by Robert Sedgewick the Trie was first "discovered" by de la Briandais in 1959 and given the name Trie by Fredkin in 1960.
The Trie algorithm for this class is of my own design. I looked for other algorithms but didn't find an algorithm that was memory efficient (several algorithms I found replaced the sibling list with a vector with an element for each letter, instead of the sibling prefix list I use).
It is important to note that the Trie is ordered on the basis of the letters that make up the words that are stored in the Trie. Although the sibling lists are ordered, the is no other lexical ordering in the tree.
The prefix Trie is designed for words that share the same first character and the root of the Trie is this character.
Sep 2, 2013
Copyright Ian Kaplan 2013
Definition in file TrieBuilder.java.
1.7.4 
