T9 Trie Word Completion Algorithm
t9.trie.TrieBuilder Class Reference

List of all members.

Public Member Functions

TrieNode addWord (TrieNode root, Pair word)
TrieNode buildTrie (Collection< Pair > words)
TreeSet< PairlistTrie (TrieNode root)

Protected Member Functions

void listTrie (TrieNode root, String prefix, Collection< Pair > words)

Detailed Description

TrieBuilder Sep 3, 2013

Support for the construction of a String prefix "trie". In this case the prefix tree has a single root, which will be the letter that starts all of the words in the tree. The tree is a directed graph, but it is not ordered in the way a binary tree is. Instead the tree is ordered by the structure of the words.

A tree containing the words:

    child ===>
    a - b - a - n - d - o - n
    *   |   |               *
        |   l - e
        |   |   *
        |   |
        |   u - s - e
        |           *
        c - a - d - e - m - i - c
            |                   *
            c - e - p - t
                        a - b - l - e

The words are ordered in the child direction. The siblings are the words that have the same prefix. The star indicates an end-of-word.

Note that the sibling words are lexically ordered.

Each word has an associated relative frequency that annotates the last character in the word. Relative frequency is the frequency ordering within a corpus. For example, the word "a" is the 5th most frequent word out of a set of 5000 words.

Ian Kaplan, iank@bearcave.com

Definition at line 94 of file TrieBuilder.java.

Member Function Documentation

TrieNode t9.trie.TrieBuilder.addWord ( TrieNode  root,
Pair  word 

Iterate over the characters in a word and add them to the Trie if they are not already there.

rootthe root of the Trie
aPair container that contains the String to be inserted and the relative frequency value.
the root of the prefix trie

Definition at line 186 of file TrieBuilder.java.

TrieNode t9.trie.TrieBuilder.buildTrie ( Collection< Pair words)

Add a collecton of Pair objects to the prefix Trie.

wordsa list of sorted words that all start with the same letter
the root of the trie constructed for the words

Definition at line 227 of file TrieBuilder.java.

void t9.trie.TrieBuilder.listTrie ( TrieNode  root,
String  prefix,
Collection< Pair words 
) [protected]

Return a Collection of Pair objects that consist of the words in the tree and the relative frequency for each word.


Definition at line 243 of file TrieBuilder.java.

TreeSet<Pair> t9.trie.TrieBuilder.listTrie ( TrieNode  root)

Return the contents of the Trie as a list of words and frequency values.

rootthe root of the prefix Trie
a sorted TreeSet containing the Pair objected lexically sorted by the String values.

Definition at line 264 of file TrieBuilder.java.

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables