Public Member Functions
TrieNode	addWord (TrieNode root, Pair word)
TrieNode	buildTrie (Collection< Pair > words)
TreeSet< Pair >	listTrie (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:

 a
 abandon
 able
 abuse
 academic
 accept
 acceptable

    child ===>
    sibling
      |
      |
      V

    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.

Author:: 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.

Parameters:

root	the root of the Trie
a	Pair container that contains the String to be inserted and the relative frequency value.

Returns:: 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.

Parameters:

words a list of sorted words that all start with the same letter

Returns:: 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.

Parameters:

root
prefix
words

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.

Parameters:

root	the root of the prefix Trie

Returns:: 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:

t9/trie/TrieBuilder.java

Public Member Functions

Protected Member Functions

Detailed Description

Member Function Documentation