In this assignment, we will implement the part of a web search engine that ranks pages based on how well they match a search query. The best match is the web page with the highest word frequency counts for the words in a particular query.
You'll need a priority queue to manage which web pages are most
important. To get started create a class called
HeapPriorityQueue. This should be a priority queue,
implemented as a heap, with the usual methods for inserting and
removing items. Specifically, this should be a max
heap, i.e. high priority is indicated by large numbers. Test out
your priority queue on some sample data. There is priority queue code
in your textbook which you can use as a reference (make sure to cite
it if you do), but you will undoubtedly learn more and have more fun
if you try to build it yourself.
Your main class for this assignment should be called
ProcessQueries, and will be used as follows:
java ProcessQueries urlListFile ignoreFile
The urlListFile should contain a list of URLs, one per
line. These URLs should correspond to html files that are sitting in a
directory somewhere. For your convenience, I've placed an archive of
an old version of our department website for use on the department
Linux systems. An example urlListFile might contain:
/Accounts/courses/cs201/dmusican/dept-web-site/contact.html /Accounts/courses/cs201/dmusican/dept-web-site/GuidetoMath.html /Accounts/courses/cs201/dmusican/dept-web-site/guideToTheCSMajor.html /Accounts/courses/cs201/dmusican/dept-web-site/index2.html /Accounts/courses/cs201/dmusican/dept-web-site/stufflist.html /Accounts/courses/cs201/dmusican/dept-web-site/summaries.html /Accounts/courses/cs201/dmusican/dept-web-site/websearch.html
The ignoreFile should contain a list of words that you
would like to ignore when counting word frquencies (just as in the
last assignment).
When your program starts, it should process all the URLs in the
list by creating a StringCountMap for each. If you had
trouble getting your last assignment working, or if you just don't
want to be dependent on it, you can use a TreeMap
instead. (Keep all of these StringCountMap objects in an
ArrayList.) Once you have finished processing all of
these URLs, your program should enter a loop as shown below. The
program should prompt the user to enter a search query (or -1 to
quit), and then list all URLs that match the query in order of the
best match first and the worst match last. Include each result URLs
priority in parentheses after each result. URLs of web pages that do
not contain any of the words in the query should not appear in the
result list. The priority of a page is defined as the number of times
a word in the query appears on that page. Here is a sample run (not
necessarily correct):
Enter a query or -1 to quit. Search for: computer science Relevant pages: /Accounts/courses/cs127/dmusican/dept-web-site/GuidetoMath.html (priority = x) /Accounts/courses/cs127/dmusican/dept-web-site/summaries.html (priority = y) Search for: mtie Relevant pages: /Accounts/courses/cs127/dmusican/dept-web-site/GuidetoMath.html (priority = x) /Accounts/courses/cs127/dmusican/dept-web-site/summaries.html (priority = y) /Accounts/courses/cs127/dmusican/dept-web-site/contact.html (priority = z) Search for: -1
Your priority queue will be used as you loop over all of the
StringCountMaps. Every time you find a web page that has a priority
greater than 0 for your query, add that web page and its priority into
your HeapPriorityQueue. After you have processed all
URLs, use the priority queue to print out the URLs in order with the
priorities next to them. (The astute student will notice that we're
really just using the priority queue to sort the results by
priority. This technique is known as heapsort.) You should
not use any other sorting technique.
Your program should handle multiple word queries. The priority for a given URL should be determined as the sum of the number of matches for each word in the query.
Have fun, and good luck! Remember to start early and make incremental progress.
Many thanks to Tia Newhall and Lisa Meeden at Swarthmore College.