Autocomplete

Autocomplete - Overview

Welcome to the Autocomplete assignment. In this assignment, you will be implementing the autocomplete algorithm, which is discussed at length here, using binary search and trie traversal. In doing so, you will see some of the advantages of using tries (or more generally, trees/graphs) and sorted arrays over general arrays.

As always, before starting be sure to snarf the assignment via Ambient so you can read along. You can alternatively download the .jar file here.

You can also view/download the individual classes:

AutocompleteGUI.java

AutocompleteMain.java

Autocompletor.java

AutocompletorBenchmark.java

BinarySearchAutocomplete.java

BruteAutocomplete.java

Node.java

Term.java

TrieAutocomplete.java

Here is a printer friendly version of this assignment.

###Introduction

In this assignment, you will implement autocomplete for a given set of N terms, where a term is a query string and an associated nonnegative weight. That is, given a prefix, find all queries that start with the given prefix, in descending order of weight.w

For example, if I am given the query “com” I might suggest terms like “computer”, “communication” or “combine”. For this assignment, our terms have predetermined fixed weights assigned to them, and we will return the highest-weighted terms among those terms that share have the query as their prefix.

In this assignment, you will:

  1. Complete a datatype Term that represents an autocomplete term: a query string and an associated real weight.
  2. Write a class, BinarySearchAutocomplete that impletements autocomplete functionality by using binary search to find the all query strings that start with a given prefix; and sort the matching terms in descending order by weight.
  3. Write a class, TrieAutocomplete to implement Autcocomplete functionality using a Trie data structure. </ol> When you snarf this project, you will receive the following already completed classes:
    • Autocompletor – the interface which you will be writing implementations of.
    • AutocompleteMain – the class to launch the GUI from. When testing your implementations of autocomplete, you will need to change the String AUTOCOMPLETOR_CLASS_NAME’s value.
    • AutocompletorBenchmark – once you have written an implementation of Autocompletor, this class will tell you how quickly it runs.
    • BruteAutocomplete - A completed (albeit slow) implementation of Autocompletor.
    • Node – a node class for use in TrieAutocomplete. Nothing needs to be modified here, but definitely read through this class before starting TrieAutocomplete.
    • AutocompleteGUI – the GUI for this project. You can ignore this class.
    You are responsible for completing the following classes:
    • Term – a class used to encapsulate individual search terms and their weights, which includes several methods of comparing terms. You need to complete these class in order for BruteAutocomplete to be usable with AutocompleteMain.
    • BinarySearchAutocomplete – an implementation of Autocompletor which performs the autocomplete algorithm using binary search.
    • TrieAutocomplete – an implementation of Autocompletor which performs the autocomplete algorithm using trie exploration.
    </ul> In addition, after completing these classes, you will use following methods on your Autocompletor implementations: The incomplete methods come with headers detailing what the inputs and expected output are, as well as implementation details such as edge cases and exceptions to be throw. You could probably complete the assignment using only these headers, but you should still read through this writeup. It will make completing the assignment easier, and you might avoid some simple mistakes in doing so.