T9
T9 Trie Word Completion Algorithm
t9/trie/TrieBuilder.java
Go to the documentation of this file.
00001 
00031 package t9.trie;
00032 
00033 import java.util.Collection;
00034 import java.util.TreeSet;
00035 
00094 public class TrieBuilder {
00095 
00131     private TrieNode listInsert(TrieNode sibling, char letter) {
00132         TrieNode head = sibling;
00133         TrieNode trail = head;
00134         while (head != null) {
00135             if (letter == head.getLetter()) {
00136                 break;
00137             }
00138             else if (letter < head.getLetter()) {
00139                 TrieNode newSib = new TrieNode(letter);
00140                 trail.setSib(newSib);
00141                 newSib.setSib(head);
00142                 head = newSib;
00143                 break;
00144             }
00145             trail = head;
00146             head = head.getSib();
00147             if (head == null) {
00148                 TrieNode newSib = new TrieNode(letter );
00149                 trail.setSib(newSib);
00150                 head = newSib;
00151             }
00152         }
00153         return head;
00154     }
00155  
00156 
00163     private TrieNode insertSibling(TrieNode head, char letter) {
00164         TrieNode sibling = head.getSib();
00165         if (sibling == null) {
00166             TrieNode newSib = new TrieNode(letter);
00167             head.setSib(newSib);
00168             head = newSib;
00169         }
00170         else {
00171             head = listInsert(sibling, letter );
00172         }
00173         return head;
00174     }
00175 
00176 
00177 
00186     public TrieNode addWord(TrieNode root, Pair word) {
00187         if (word != null) {
00188             TrieNode head = root;
00189             TrieNode trail = head;
00190             char letters[] = word.word.toCharArray();
00191             for (char letter : letters) {
00192                 if (root == null) {
00193                     root = new TrieNode( letter );
00194                     trail = root;
00195                 }
00196                 else if (head == null) {
00197                     TrieNode newChild = new TrieNode(letter);
00198                     trail.setChild(newChild);
00199                     trail = newChild;
00200                 }
00201                 else if (head.getLetter() != letter){
00202                     head = insertSibling( head, letter );
00203                     trail = head;
00204                     head = head.getChild();
00205                 }
00206                 else {
00207                     trail = head;
00208                     head = head.getChild();
00209                 }
00210             }
00211             if (head == null) {
00212                 head = trail;
00213             }
00214             head.setEOW();
00215             head.setFrequency(word.frequency);
00216         }
00217 
00218         return root;
00219     }  
00220 
00227     public TrieNode buildTrie( Collection<Pair> words ) {
00228         TrieNode root = null;
00229         for (Pair word : words) {
00230             root = addWord(root, word);
00231         }
00232         return root;
00233     }
00234 
00243     protected void listTrie( TrieNode root, String prefix, Collection<Pair> words ) {
00244         String newPrefix = prefix;
00245         for (TrieNode curRoot = root; curRoot != null; curRoot = curRoot.getChild()) {
00246             // traverse down the sibling list
00247             TrieNode sib = curRoot.getSib();
00248             listTrie(sib, newPrefix, words );
00249             newPrefix = newPrefix + curRoot.getLetter();
00250             if (curRoot.isEOW()) {
00251                 Pair pair = new Pair(newPrefix, curRoot.getFrequency());
00252                 words.add(pair);
00253             }
00254         }
00255     }
00256     
00264     public TreeSet<Pair> listTrie(TrieNode root)
00265     {
00266         TreeSet<Pair> words = new TreeSet<Pair>();
00267         listTrie(root, "", words);
00268         return words;
00269     }
00270 
00271 }
 All Classes Namespaces Files Functions Variables