T9 Trie Word Completion Algorithm
t9/trie/TrieBuilder.java File Reference

Go to the source code of this file.


class  t9.trie.TrieBuilder


package  t9.trie

Detailed Description

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

Ian Kaplan, www.bearcave.com, iank@bearcave.com

Definition in file TrieBuilder.java.

 All Classes Namespaces Files Functions Variables