5.4. Homework

This section explains the homework assignment regarding Autocomplete.

Auto-Complete

Most virtual keyboards provide the option of auto-complete, which gives a list of candidate words that you wish to type given a prefix you enter. For instance, when you type "sh", it gives a list of candidate words such as "she", "shell", "ship", etc.

"sh" -> ["she", "ship", "shell, ...]

If you select a word from the candidates, it should learn your selection as the top candidate for that prefix. For instance, if you select "ship" from the example above, the next time you enter the same prefix "sh", it should give a list of candidates where the first item is "ship" instead of "she".

"sh" -> ["ship", "she", "shell, ...]

Your task is to write a program that gives a list of candidate words for any prefix and learns the selected candidates.

Tasks

• Create a class called AutocompleteHW under the autocomplete package:

  • This class extends the abstract class Autocomplete, which extends Trie.

  • The value type of the generic T can be a collection of strings (e.g., List<String>).

  • You must create a constructor that takes two parameters, dict_file and max, and calls its super constructor, which reads all words in the dictionary file (e.g., dict.txt).

• Override the getCandidates() method that takes a prefix and returns a list of candidate words matching the prefix:

  • The max-number of candidates in the list must be the return value of the getMax() method.

  • The most recently selected candidate should appear as the 1st item, the 2nd most recently selected candidate should appear as the 2nd item, and so on.

  • The rest of the candidate list should be filled with the shortest words matching the prefix.

  • If there are more than one candidate with the same lengths, they should be sorted alphabetically.

  • Make sure the same candidate does not appear more than once.

• Override the pickCandidate() method that takes a prefix and a selected candidate, and saves the information:

  • This is the most recently selected candidate for that particular prefix. It must appear as the first item in the candidate list when the same prefix is entered next time.

• Submit AutocompleteHW.java to Canvas.

Extra credit

• Create a class called AutocompleteHWExtra under the autocomplete package.

• Feel free to change the generic type, representing the value type of each TrieNode, to anything other than List<String> (List<something else>).

• The getCandidates() method:

  • Must show the most frequently picked candidate first, the 2nd-most frequently picked candidate next, and so on.

  • If there are more than one candidate with the same frequency, sort them by recency.

  • The rest of candidates should be filled as in the original task.

• You must submit both AutocompleteHW and AutocompleteHWExtra to earn the extra credit.

Notes

• Do not change the dictionary file. If you find anything peculiar about the dictionary file, please let me know so everyone works on the same copy of the dictionary file.

• Please test your program yourself. We will evaluate your program using our unit tests and measure the performance (both speed and accuracy).

• Take a look at Map if you are not familiar with methods in the standard library.

• If you are having trouble with implementing getCandidates(), think about how to traverse the trie given any node.

• If you are having trouble with implementing pickCandidate(), take a look at Trie#put.

• You are not allowed to use any type of Map to store candidates for this homework.

• Your program should be able to handle prefixes or candidates that do not exist in the dictionary.

• All picked candidates should be introduced as real words to the trie.

• Whitespaces are not allowed as input; thus, you should trim all input strings.