I need help in completeing this assignment. This needs to be implemented in Java

Question

I need help in completeing this assignment. This needs to be implemented in Java.

Programming Assignment: Autocomplete Me

Write a program to implement autocomplete for a given set of N strings and positive weights. That is, given a prefix, find all strings in the set that start with the prefix, in descending order of weight.

Autocomplete is an important feature of many modern applications. As the user types, the program predicts the complete query (typically a word or phrase) that the user intends to type. Autocomplete is most effective when there are a limited number of likely queries. For example, the Internet Movie Database uses it to display the names of movies as the user types; search engines use it to display suggestions as the user enters web search queries; cell phones use it to speed up text input.

In these examples, the application predicts how likely it is that the user is typing each query and presents to the user a list of the top-matching queries, in descending order of weight. These weights are determined by historical data, such as box office revenue for movies, frequencies of search queries from other Google users, or the typing history of a cell phone user. For the purposes of this assignment, you will have access to a set of all possible queries and associated weights (and these queries and weights will not change).

The performance of autocomplete functionality is critical in many systems. For example, consider a search engine which runs an autocomplete application on a server farm. According to one study, the application has only about 50ms to return a list of suggestions for it to be useful to the user. Moreover, in principle, it must perform this computation for every keystroke typed into the search bar and for every user!

In this assignment, you will implement autocomplete by sorting the queries in lexicographic order; using binary search to find the set of queries that start with a given prefix; and sorting the matching queries in descending order by weight.

Part 1: autocomplete term. Write an immutable data type Term.java that represents an autocomplete term: a string query and an associated real-valued weight. You must implement the following API, which supports comparing terms by three different orders: lexicographic order by query string (the natural order); in descending order by weight (an alternate order); and lexicographic order by query string but using only the first r characters (a family of alternate orderings). The last order may seem a bit odd, but you will use it in Part 3 to find all terms that start with a given prefix (of length r).

The constructor should throw a java.lang.NullPointerException if query is null and a java.lang.IllegalArgumentException unless weight is nonnegative. The byPrefixOrder() method should throw ajava.lang.IllegalArgumentException if r is negative.

Part 2: binary search. When binary searching a sorted array that contains more than one key equal to the search key, the client may want to know the index of either the first or the last such key. Accordingly, implement the following API:

public class BinarySearchDeluxe { // Return the index of the first key in a[] that equals the search key, or -1 if no such key. public static int firstIndexOf(Key[] a, Key key, Comparator comparator) // Return the index of the last key in a[] that equals the search key, or -1 if no such key. public static int lastIndexOf(Key[] a, Key key, Comparator comparator) }

Corner cases. Each static method should throw a java.lang.NullPointerException if any of its arguments is null. You should assume that the argument array is in sorted order (with respect to the supplied comparator).

Performance requirements. The firstIndexOf() and lastIndexOf() methods should make at most 1 + log2N compares in the worst case,

Part 3: autocomplete. In this part, you will implement an immutable data type that provides autocomplete functionality for a given set of string and weights, using Term and BinarySearchDeluxe. To do so, sort the terms in lexicographic order; use binary search to find the set of terms that start with a given prefix; and sort the matching terms in descending order by weight. Organize your program by creating an immutable data type Autocomplete with the following API:

public class Autocomplete { // Initialize the data structure from the given array of terms. public Autocomplete(Term[] terms) // Return all terms that start with the given prefix, in descending order of weight. public Term[] allMatches(String prefix) // Return the number of terms that start with the given prefix. public int numberOfMatches(String prefix) }

Corner cases. The constructor and each method should throw a java.lang.NullPointerException its argument is null.

Performance requirements. The constructor should make proportional to N log N compares (or better) in the worst case, where N is the number of terms. The allMatches() method should make proportional to log N + M log M compares (or better) in the worst case, where M is the number of matching terms. The numberOfMatches() method should make proportional to log N compares (or better) in the worst case. In this context, a compare is one call to any of the compare() or compareTo() methods defined in Term.

Input format. We provide a number of sample input files for testing. Each file consists of an integer N followed by N pairs of query strings and positive weights. There is one pair per line, with the weight and string separated by a tab. A query string can be an arbitrary sequence of Unicode characters, including spaces (but not newlines).

The file wiktionary.txt contains the 10,000 most common words in Project Gutenberg, with weights equal to their frequencies.

The file cities.txt contains over 90,000 cities, with weights equal to their populations.

Below is a sample client that takes the name of an input file and an integer k as command-line arguments. It reads the data from the file; then it repeatedly reads autocomplete queries from standard input, and prints out the top k matching terms in descending order of weight.

Here are a few sample executions:

Interactive GUI (optional, but fun and no extra work). Download and compile AutocompleteGUI.java. The program takes the name of a file and an integer k as command-line arguments and provides a GUI for the user to enter queries. It presents the top k matching terms in real time. When the user selects a term, the GUI opens up the results from a Google search for that term in a browser.

Extra credit 1. This is an opportunity to earn extra credit and contribute to future offerings of this assignment. Create a real-world data (preferably large or huge) for which autocomplete would be appropriate and document it in your readme file (including a reference to the original data source). Below are a few possibilities. Note that some of the datasets are massive and you will need to filter them down to appropriate sizes and put them into our file format.

Wikipedia: term = Wikipedia page, weight = number of hits per year.

Google books Ngram Viewer: term = n-gram, weight = frequency of occurrence in corpus of books.

Wiktionary: term = word, weight = frequency of occurrence in corpus. Pick a language with a non-Latin alphabet such as Hebrew, Arabic, Russian, Greek, or Japanese.

The Internet Movie Database: term = movie, weight = number of reviews or average rating.

Be sure that your file is in the prescribed format (tab-separated and UTF-8 encoded). If your file is less than 50MB, submit it as usual; if it is larger, please contact your preceptor for submission instructions.

Extra credit 2. Improve AutcompleteGUI.java in the following (or other) ways:

Improve the graphical layout (e.g., align search bar and suggestion box, allow search bar and suggestion box to expand to width of window).

Fix some of the known bugs, which are documented in the file.

Deliverables. Submit Autocomplete.java, BinarySearchDeluxe.java, and Term.java. Your may not call any library functions other than those in java.lang, java.util, stdlib.jar, and algs4.jar. Finally, submit a readme.txt file and answer the questions.

This assignment was developed by Matthew Drabick and Kevin Wayne.
Copyright © 2014.

  % more wiktionary.txt       10000     56271872.00  the     33950064.00  of     29944184.00  and     25956096.00  to     17420636.00  in     11764797.00  i     11073318.00  that     10078245.00  was      8799755.00  his                  ...         3923.23  calves  

  % more cities.txt  93827        14608512  Shanghai, China        13076300  Buenos Aires, Argentina        12691836  Mumbai, India        12294193  Mexico City, Distrito Federal, Mexico        11624219  Karachi, Pakistan        11174257  stanbul, Turkey        10927986  Delhi, India        10444527  Manila, Philippines        10381222  Moscow, Russia                  ...               2  Al Khniq, Yemen  

IMDb a beautif Harris Beautiful Soul (2012 Deitrick Lesley Ann Brandt AMER HUS results for "a auauyr" NAME Breaking MACHE Google how to how to tie a tie how to take a screenshot on a mac how to get rid of ants how to hard boil eggs Press Enter to search New message The conversation will appear here. projects a s d f g h j k

Explanation / Answer

import java.lang.*;

//import BinarySearchDeluxe;

//import Term;

import java.util.Comparator;

import java.util.Arrays;

public class Autocomplete {

public Term[] quries;

}

// Initialize the data structure from the given array of terms.

public Autocomplete(Term[] terms){

if(terms == NULL){

throw new java.lang.NullPointerException();

}

this.quries = terms;

Arrays.sort(quries);

}

// Return all terms that start with the given prefix, in descending order fo weight.

public Term[] allMatches(String prefix){

if(prefix == NULL)

throw new java.lang.NullPointerException();

}

Term temp = new Term(prefix, 0);

// for(int j = 0; j<50000; j+= 2000){

// StdOut.println(quries[j].query);

//}

//StdOut.println("Binarysearch try");

//StdOut.println(Term.byPrefixOrder(3).compare(new Term("sadf",0), new Term("sadf" , 0)));

}

int i = BinarySearchDeluxe.firstIndexOf(quries, temp, Term.byPrefixOrder(prefix.length()));

int j = BinarySearchDeluxe.lastIndexOf(quries, temp, Term.byPrefixOrder(prefix.length()));

if(i == -1 || j == -1){

throw new java.lang.NullPointerException();

}

Term[] matches = new Term[j-i+1];

matches = Arrays.copyOfRange(quries,i,j);

Arrays.sort(matches, Term.byReverseWeightOrder());

return matches;

}

// Return the number of terms that start with the given prefix.

public int numberOfMatches(String prefix){

if(prefix == NULL){

throw new java.lang.NullPointerException();

}

Term temp = new Term(prefix, 0);

int i = BinarySearchDeluxe.firstIndexOf(quries, temp, Term.byPrefixOrder(prefix.length()));   

int j = BinarySearchDeluxe.lastIndexOf(quries, temp, Term.byPrefixOrder(prefix.length()));

return j - i + 1;   

}

public static void main(String[] args){

//read in the terms from a file

String filename = args[0];

In in = new In(filename);

int N = in.readInt();

Terms[] terms = new Term[N];

for(int i=0; i<N; i++){

double weight = in.readDouble(); //read the next weight

in.readChar(); //scan paste the tab

String query = in.readLine(); //read the next query

terms[i] = new Term(query, weight); // construct the term

}

// read in queries from standard input and print out the top k matching terms

int k = Integer.parseInt(args[1]);

Autocomplete autocomplete = new Autocomplete(terms);

while(StdIn.hasNextLine()){

String prefix = StdIn.readLine();

Term[] results = autocomplete.allMatches(prefix);

for(int i = 0; i<Math.min(k, results.length); i++)

StdOut.println(results[i]);

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.