Question

Summary

You will write an application to build a tree structure called Trie for a dictionary of English words, and use the Trie to generate completion lists for string searches.

Trie Structure

A Trie is a general tree, in that each node can have any number of children. It is used to store a dictionary (list) of words that can be searched on,
in a manner that allows for efficient generation of completion lists.

The word list is originally stored in an array, and the trie is built off of this array. Here are some examples of word lists and the tries built to store the words, followed by an explanation of the trie structure and its relationship to its source word list.

Trie 1	Trie 2	Trie 3
o(data) data 오 10,0,3 Root node is always empty. Child [0,0,3] of root stores "data" in a triplet 0 (for index of word in list), 0 (for position of first character, 'd' in "data") and 3 (for position of last character, 'a')	Child (0,0,0) of root stores common prefix "d" of its children "data" (left child) and "door" (right child), in triplet 0 (index of first word "data" in list), 0 (starting position of prefix "d"), and 0 (ending position of prefix "d"). Internal nodes represent prefixes, leaf nodes represent complete words. The left leaf node stores triplet 0 (first word in list), 1 (first index past the common prefix "d", and 3 (last index in word). The right leaf node is stored similarly.	Like in trie 2, child of root stores common prefix "d", but this time left child is "door", and right child is "data", because "door" appears before "data" in the array.

• (50 pts) buildTrie: Starting with an empty trie, builds it up by inserting words from an input array, one word at a time. The words in the input array are all lower case, and comprise of letters ONLY.
• (30 pts) completionList: For a given search prefix, scans the trie efficiently, gathers and returns an ArrayList of references to all leaf TrieNodes that hold words that begin with the search prefix (you should NOT create new nodes.) For instance, in the trie of Example 2 above, for search prefix "po" your implementation should return a list of references to these trie leaf nodes: [2,3,6],[6,3,5],[3,4,7],[4,4,5].
  NOTE:
  • The order in which the leaf nodes appear in the returned list does not matter.
  • You may NOT search the words array directly, since that would defeat the purpose of building the trie, which allows for more efficient prefix search. See the Prefix Search section above. If you search the array, you will NOT GET ANY credit, even if your result is correct.
  • If your prefix search examines unnecessary nodes (see Prefix Search section above), you will NOT GET ANY credit, even if your result is correct.

Make sure to read the comments in the code that precede classes, fields, and methods for code-specific details that do not appear here. Also, note that the methods are all static, and the Trie has a single private constructor, which means NO Trie instances are to be created - all manipulations are directly done via TrieNode instances.

You may NOT MAKE ANY CHANGES to the Trie.java file EXCEPT to (a) fill in the body of the required methods, or (b) add private helper methods. Otherwise, your submission will be penalized.

You may NOT MAKE ANY CHANGES to the TrieNode class (you will only be submitting Trie.java). When we test your submission, we will use the exact same version of TrieNode that we shipped to you.

package trie;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class TrieApp {

   static Scanner stdin = new Scanner(System.in);
  
   public static void main(String[] args)
   throws IOException {
       System.out.print("Enter words file name => ");
       String wordsFile = stdin.nextLine();
       Scanner sc = new Scanner(new File(wordsFile));
       // words appear one per line in input file
       // first line has number of words
       int numWords = Integer.parseInt(sc.nextLine());
       String[] allWords = new String[numWords];
       for (int i=0; i < allWords.length; i++) {
           allWords[i] = sc.nextLine().trim().toLowerCase();
       }
       sc.close();
      
       // build Trie
       TrieNode root = Trie.buildTrie(allWords);
       // print it for verification
       Trie.print(root, allWords);
       // do completion lists
       completionLists(root, allWords);
   }
  
   private static void completionLists(TrieNode root, String[] allWords) {
       System.out.print("\ncompletion list for (enter prefix, or 'quit'): ");
       String prefix = stdin.nextLine().trim().toLowerCase();
       while (!"quit".equals(prefix)) {
           ArrayList matches = Trie.completionList(root, allWords, prefix);
           printMatches(matches, allWords);
           System.out.print("\ncompletion list for: ");
           prefix = stdin.nextLine().trim().toLowerCase();
       }
   }
  
   private static void printMatches(ArrayList matches, String[] allWords) {
       if (matches == null) {
           System.out.println("No match");
           return;
       }
       System.out.print(allWords[matches.get(0).substr.wordIndex]);
       for (int i=1; i < matches.size(); i++) {
           System.out.print(","+allWords[matches.get(i).substr.wordIndex]);
       }
       System.out.println();
   }
  
}

package trie;

import java.util.ArrayList;

/**
* This class implements a Trie.
*
* @author
*
*/
public class Trie {
  
   // prevent instantiation
   private Trie() { }
  
   /**
   * Builds a trie by inserting all words in the input array, one at a time,
   * in sequence FROM FIRST TO LAST. (The sequence is IMPORTANT!)
   * The words in the input array are all lower case.
   *
   * @param allWords Input array of words (lowercase) to be inserted.
   * @return Root of trie with all words inserted from the input array
   */
   public static TrieNode buildTrie(String[] allWords) {
       /** COMPLETE THIS METHOD **/
      
       // FOLLOWING LINE IS A PLACEHOLDER TO ENSURE COMPILATION
       // MODIFY IT AS NEEDED FOR YOUR IMPLEMENTATION
       return null;
   }
  
   /**
   * Given a trie, returns the "completion list" for a prefix, i.e. all the leaf nodes in the
   * trie whose words start with this prefix.
   * For instance, if the trie had the words "bear", "bull", "stock", and "bell",
   * the completion list for prefix "b" would be the leaf nodes that hold "bear", "bull", and "bell";
   * for prefix "be", the completion would be the leaf nodes that hold "bear" and "bell",
   * and for prefix "bell", completion would be the leaf node that holds "bell".
   * (The last example shows that an input prefix can be an entire word.)
   * The order of returned leaf nodes DOES NOT MATTER. So, for prefix "be",
   * the returned list of leaf nodes can be either hold [bear,bell] or [bell,bear].
   *
   * @param root Root of Trie that stores all words to search on for completion lists
   * @param allWords Array of words that have been inserted into the trie
   * @param prefix Prefix to be completed with words in trie
   * @return List of all leaf nodes in trie that hold words that start with the prefix,
   *            order of leaf nodes does not matter.
   * If there is no word in the tree that has this prefix, null is returned.
   */
   public static ArrayList completionList(TrieNode root,
                                       String[] allWords, String prefix) {
       /** COMPLETE THIS METHOD **/
      
       // FOLLOWING LINE IS A PLACEHOLDER TO ENSURE COMPILATION
       // MODIFY IT AS NEEDED FOR YOUR IMPLEMENTATION
       return null;
   }
  
   public static void print(TrieNode root, String[] allWords) {
       System.out.println("\nTRIE\n");
       print(root, 1, allWords);
   }
  
   private static void print(TrieNode root, int indent, String[] words) {
       if (root == null) {
           return;
       }
       for (int i=0; i < indent-1; i++) {
           System.out.print(" ");
       }
      
       if (root.substr != null) {
           String pre = words[root.substr.wordIndex]
                           .substring(0, root.substr.endIndex+1);
           System.out.println(" " + pre);
       }
      
       for (int i=0; i < indent-1; i++) {
           System.out.print(" ");
       }
       System.out.print(" ---");
       if (root.substr == null) {
           System.out.println("root");
       } else {
           System.out.println(root.substr);
       }
      
       for (TrieNode ptr=root.firstChild; ptr != null; ptr=ptr.sibling) {
           for (int i=0; i < indent-1; i++) {
               System.out.print(" ");
           }
           System.out.println(" |");
           print(ptr, indent+1, words);
       }
   }
}

Answer 1

Working code implemented in Java and comments for better understanding:

Here I am attaching these 3 files:

• Trie.java
• TrieApp.java
• TrieNode.java

Code for Trie.java:

package trie;

import java.util.ArrayList;

/**
* This class implements a Trie.
*/
public class Trie {
  
   // prevent instantiation
   private Trie() { }
  
   /**
   *
   * Builds a trie by inserting all words in the input array, one at a time,
   * in sequence FROM FIRST TO LAST. (The sequence is IMPORTANT!)
   * The words in the input array are all lower case.
   *
   * @param allWords Input array of words (lowercase) to be inserted.
   * @return Root of trie with all words inserted from the input array
   */
   public static TrieNode buildTrie(String[] allWords) {
      
       TrieNode root = new TrieNode(null, null, null);
       if(allWords.length == 0)
           return root;
      
       root.firstChild = new TrieNode(new Indexes(0,
                           (short)(0),
                           (short)(allWords[0].length() - 1)), null, null);
      
       TrieNode ptr = root.firstChild, prev = root.firstChild;
       int sierra = -1, startIdx = -1, endIdx = -1, wordIdx = -1;
      
       for(int i = 1; i < allWords.length; i++) {
           String word = allWords[i];
          
          
           while(ptr != null) {
               startIdx = ptr.substr.startIndex;
               endIdx = ptr.substr.endIndex;
               wordIdx = ptr.substr.wordIndex;
              
              
               if(startIdx > word.length()) {
                   prev = ptr;
                   ptr = ptr.sibling;
                   continue;
               }
              
               sierra = similarUntil(allWords[wordIdx].substring(startIdx, endIdx+1),
                       word.substring(startIdx));
              
               if(sierra != -1)
                   sierra += startIdx;
              
               if(sierra == -1) {
                   prev = ptr;
                   ptr = ptr.sibling;
               }
               else {
                   if(sierra == endIdx) {
                       prev = ptr;
                       ptr = ptr.firstChild;
                   }
                   else if (sierra < endIdx){
                       prev = ptr;
                       break;
                   }
               }
           }
          
           if(ptr == null) {
               Indexes alpha = new Indexes(i, (short)startIdx, (short)(word.length()-1));
               prev.sibling = new TrieNode(alpha, null, null);
           } else {
               Indexes currentIndexes = prev.substr;
               TrieNode currentFirstChild = prev.firstChild;
              
               Indexes currWordNewIndexes = new Indexes(currentIndexes.wordIndex, (short)(sierra+1), currentIndexes.endIndex);
               currentIndexes.endIndex = (short)sierra;
              
               prev.firstChild = new TrieNode(currWordNewIndexes, null, null);
               prev.firstChild.firstChild = currentFirstChild;
               prev.firstChild.sibling = new TrieNode(new Indexes((short)i,
                       (short)(sierra+1),
                       (short)(word.length()-1)),
                       null, null);
           }
          
           ptr = prev = root.firstChild;
           sierra = startIdx = endIdx = wordIdx = -1;
       }
      
       return root;
   }
  
   private static int similarUntil(String alpha, String beta){
       int ans = 0;
       while(ans<alpha.length() &&
               ans<beta.length() &&
               alpha.charAt(ans)==beta.charAt(ans)){
           ans++;
       }
       return (ans-1);
   }
  
   /**
   * Given a trie, returns the "completion list" for a prefix, i.e. all the leaf nodes in the
   * trie whose words start with this prefix.
   * For instance, if the trie had the words "bear", "bull", "stock", and "bell",
   * the completion list for prefix "b" would be the leaf nodes that hold "bear", "bull", and "bell";
   * for prefix "be", the completion would be the leaf nodes that hold "bear" and "bell",
   * and for prefix "bell", completion would be the leaf node that holds "bell".
   * (The last example shows that an input prefix can be an entire word.)
   * The order of returned leaf nodes DOES NOT MATTER. So, for prefix "be",
   * the returned list of leaf nodes can be either hold [bear,bell] or [bell,bear].
   *
   * @param root Root of Trie that stores all words to search on for completion lists
   * @param allWords Array of words that have been inserted into the trie
   * @param prefix Prefix to be completed with words in trie
   * @return List of all leaf nodes in trie that hold words that start with the prefix,
   *            order of leaf nodes does not matter.
   * If there is no word in the tree that has this prefix, null is returned.
   */
   public static ArrayList<TrieNode> completionList(TrieNode root,
                                       String[] allWords, String prefix) {
      
       if(root==null){
           return null;
       }
       ArrayList<TrieNode> answer = new ArrayList<TrieNode>();
       TrieNode ptr = root;
       while(ptr!=null){
           if(ptr.substr==null){
               ptr = ptr.firstChild;
           }
          
       String sierra = allWords[ptr.substr.wordIndex];
       String alpha = sierra.substring(0, ptr.substr.endIndex+1);
       if(sierra.startsWith(prefix) || prefix.startsWith(alpha)){
           if(ptr.firstChild!=null){
               answer.addAll(completionList(ptr.firstChild,allWords,prefix));
               ptr=ptr.sibling;
           }else{
               answer.add(ptr);
               ptr=ptr.sibling;
           }
       }else{
           ptr = ptr.sibling;
       }
       }
      
       return answer;
   }
  
   public static void print(TrieNode root, String[] allWords) {
       System.out.println("\nTRIE\n");
       print(root, 1, allWords);
   }
  
   private static void print(TrieNode root, int indent, String[] words) {
       if (root == null) {
           return;
       }
       for (int i=0; i < indent-1; i++) {
           System.out.print(" ");
       }
      
       if (root.substr != null) {
           String pre = words[root.substr.wordIndex]
                           .substring(0, root.substr.endIndex+1);
           System.out.println(" " + pre);
       }
      
       for (int i=0; i < indent-1; i++) {
           System.out.print(" ");
       }
       System.out.print(" ---");
       if (root.substr == null) {
           System.out.println("root");
       } else {
           System.out.println(root.substr);
       }
      
       for (TrieNode ptr=root.firstChild; ptr != null; ptr=ptr.sibling) {
           for (int i=0; i < indent-1; i++) {
               System.out.print(" ");
           }
           System.out.println(" |");
           print(ptr, indent+1, words);
       }
   }
}

Code for TrieApp.java:

package trie;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class TrieApp {

   static Scanner stdin = new Scanner(System.in);
  
   public static void main(String[] args)
   throws IOException {
       System.out.print("Enter words file name => ");
       String wordsFile = stdin.nextLine();
       Scanner sc = new Scanner(new File(wordsFile));
       // words appear one per line in input file
       // first line has number of words
       int numWords = Integer.parseInt(sc.nextLine());
       String[] allWords = new String[numWords];
       for (int i=0; i < allWords.length; i++) {
           allWords[i] = sc.nextLine().trim().toLowerCase();
       }
       sc.close();
      
       // build Trie
       TrieNode root = Trie.buildTrie(allWords);
       // print it for verification
       Trie.print(root, allWords);
       // do completion lists
       completionLists(root, allWords);
   }
  
   private static void completionLists(TrieNode root, String[] allWords) {
       System.out.print("\ncompletion list for (enter prefix, or 'quit'): ");
       String prefix = stdin.nextLine().trim().toLowerCase();
       while (!"quit".equals(prefix)) {
           ArrayList<TrieNode> matches = Trie.completionList(root, allWords, prefix);
           printMatches(matches, allWords);
           System.out.print("\ncompletion list for: ");
           prefix = stdin.nextLine().trim().toLowerCase();
       }
   }
  
   private static void printMatches(ArrayList<TrieNode> matches, String[] allWords) {
       if (matches == null) {
           System.out.println("No match");
           return;
       }
       System.out.print(allWords[matches.get(0).substr.wordIndex]);
       for (int i=1; i < matches.size(); i++) {
           System.out.print(","+allWords[matches.get(i).substr.wordIndex]);
       }
       System.out.println();
   }
  
}

Code for TrieNode.java:

package trie;

class Indexes {
  
   /**
   * Index into the word collection array.
   */
   int wordIndex;
  
   /**
   * Start index of substring in word.
   */
   short startIndex;
  
   /**
   * End index of substring in word.
   */
   short endIndex;
  
   /**
   * Initializes this instance with all indexes.
   *
   * @param wordIndex Index of word in array of words
   * @param startIndex Starting index of substring
   * @param endIndex Ending index of substring
   */
   public Indexes(int wordIndex, short startIndex, short endIndex) {
       this.wordIndex = wordIndex;
       this.startIndex = startIndex;
       this.endIndex = endIndex;
   }
  
   /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
   public String toString() {
       return "(" + wordIndex + "," + startIndex + "," + endIndex + ")";
   }
  
   /* (non-Javadoc)
   * @see java.lang.Object#equals(java.lang.Object)
   */
   public boolean equals(Object o) {
       if (o == null || !(o instanceof Indexes)) {
           return false;
       }
       Indexes oi = (Indexes)o;
       return wordIndex == oi.wordIndex &&
               startIndex == oi.startIndex &&
               endIndex == oi.endIndex;
   }
}

/**
* This class encapsulates a compressed trie node with fields for the following:
* - an Indexes instance, pointing to the substring that is held at that node
* - the first child node
* - the sibling node
*/
public class TrieNode {

   /**
   * Substring held at this node (could be a single character)
   */
   Indexes substr;
  
   /**
   * First child of this node
   */
   TrieNode firstChild;
  
   /**
   * Sibling of this node
   */
   TrieNode sibling;
  
   /**
   * Initializes this trie node with substring, first child, and sibling
   *
   * @param substr Substring held at this node
   * @param firstChild First child of this node
   * @param sibling Sibling of this node
   */
   public TrieNode(Indexes substr, TrieNode firstChild, TrieNode sibling) {
       this.substr = substr;
       this.firstChild = firstChild;
       this.sibling = sibling;
   }
  
   /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
   public String toString() {
       return substr.toString();
   }
  
}

Output Screenshots:

x Start Page Output x TrieApp.java Main (run) x Main (run) #4 X run: Enter words file name => words.txt TRIE ---root ---(0,0,0) bu ---(0,1,1) buz ---(0,2,2) buzz ---0,3,3) buzzwig ---(0,4,6) buzzcut ---(1,4,6) buzzing ---(2,4,6) buzzard ---(3,4,6) buzze ---(4,4,4) buzzers ---(4,5,6) buzzed ---(7,5,5) buzuki ---(10,3,5) bug ---(20,2,2)

Main (run) x Main (run) #4 X bug O ---(20,2,2) buy --- (21,2,2) bum ---(22,2,2) bub ---(23,2,2) be ---(5,1,1) bez ---(5,2,2) bezzant ---(5,3,6) bezazz ---(6,3,5) bezel ---(13,3,4) benzyl ---(11,2,5) bi ---(8,1,1) biz ---(8,2,2) bizzes ---(8,3,5) bize ---(17,3,3) bijous ---(9,2,5)

bijous ---(9,2,5) big ---(25,2,2) blitz ---(12,1,4) bo ---(14,1,1) bonze ---(14,2,4) boxy ---(18,2,3) bozo ---(19,2,3) bow --- (24,2,2) ba --- (15,1,1) baiza ---(15,2,4) bazzo ---(16,2,4) completion list for (enter prefix, or 'quit'): quit BUILD SUCCESSFUL (total time: 4 minutes 7 seconds)

Hope it helps. Thank you.