Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
· Purpose: Implement a simple automatic word-completion system.
· Task 1: Implement algorithms for DLB Trie insertion and traversal.
· Task 2: Implement an algorithm for retrieving a single word-prediction.
Background
Automatic completion (or Autocomplete) is a common feature in mobile phones, text editors, search engines, etc. As a user types letters, the system shows a list of word predictions to help the user complete the word they are typing. The core of an efficient Autocomplete system is a fast algorithm for retrieving word predictions based on the user input as it is typed in character by character. The predictions are all the words (pulled from a given dictionary) that start with what the user has typed so far (i.e., predictions are the list of words in a dictionary for which the user's input is a prefix).
In this assignment, using a DLB Trie as the underlying data structure, we will build a simple Autocomplete system that retrieves word predictions and allows the user to add a new word to the dictionary when the user selects none of the predictions.
The file AutoCompleteInterface.java defines a Java Interface for an AutoComplete dictionary that stores a set of words in a DLB Trie. The AutoComplete dictionary keeps track of a running prefix that starts with the empty string and grows as the user types in letters and deletes the most recently typed letters (by pressing backspace, for example). You will implement methods to add one character to and delete the last character of that prefix. You will also implement methods that use that prefix for various operations, such as checking if the prefix is one of the words in the dictionary, retrieving the number of words with the running prefix as a prefix, and adding the prefix to the dictionary as a new word.
Details
The DLBNode class is already defined in AutoComplete.java. It defines a doubly-linked list of siblings, a child reference, and an upward reference to the parent. The node's isWord field is true if and only if the node is at the end of a word in the dictionary. The size field inside a DLBNode keeps track of the number of nodes with isWord==true in the subtree rooted at the node, including the node itself.
//The DLB node class
private class DLBNode {
private char data;
private int size;
private boolean isWord;
private DLBNode nextSibling;
private DLBNode previousSibling;
private DLBNode child;
private DLBNode parent;
private DLBNode(char data){
this.data = data;
size = 0;
isWord = false;
nextSibling = previousSibling = child = parent = null;
}
}
A DLBNode containing the letter 'A' is shown in the figure below.
A reference to the current node in the DLB trie must also be defined and used. DLBNode currentNode is initially null when the running prefix is "" and normally points to the node corresponding to the last character in the running prefix. However, if the running prefix doesn't exist in the trie, currentNode will no longer be in sync with the current prefix. currentNode will be back in sync with the prefix after the prefix is added to the dictionary or after the prefix shrinks by deleting letters and exists in the dictionary. You must devise a way to determine if currentNode is out of sync with the prefix and when it is back in sync.
In this assignment, you will implement algorithms for the following methods.
The first method, add(String word) method of AutoCompleteInterface, inserts a StringBuilder object into the DLB Trie. You may want to define and use a private recursive helper method. When add is successful, the size field for the nodes it goes over should be incremented.
The figure below depicts a DLB Trie after adding three strings.
AutoCompleteInterface ac = new AutoComplete();
ac.add("SHE");
ac.add("SEA");
ac.add("SEAT");
It is also possible to set the parent references for E to point directly to S.
The next set of methods modifies the running prefix maintained by the AutoComplete dictionary. These methods are: advance(char c) for appending a character to the prefix, retreat() for deleting the last character, and reset() for resetting the prefix back to the empty string. More details about these methods can be found in AutoCompleteInterface.java. The reference to the current node, currentNode, should move over the sibling list of the root node upon the first call to advance, move (possibly sideways then) down the trie with each further call to advance, move (possibly sideways then) up the trie with retreat, and reset to null when the running prefix becomes empty.
The figure below depicts the DLB Trie after calling advance three times. Note the currentNode and currentPrefix instance variables.
ac.advance('S');
ac.advance('E');
ac.advance('A');
The figure below depicts the DLB Trie after calling retreat one time. Note the currentNode and currentPrefix instance variables.
ac.retreat();
The figure below depicts the DLB Trie after calling retreat a second time. Note the currentNode and currentPrefix instance variables.
ac.retreat();
The last set of methods operates on the prefix by checking whether it is a word in the dictionary (isWord()), adding it if not (add()), retrieving the number of word predictions for the prefix (getNumberOfPredictions), and retrieving one of the predictions (if any) (retrievePrediction). Retrieving the number of predictions should be as simple as returning the size field of the currentNode.