Project Overview

This project is due the week of final exams.

The programming project for CS 35.2 is to build a simple internet search engine to catalog and query documents (web pages) from the internet. Since this project requires network code whose implementation is outside the scope of the course, Java classes and methods to fetch web pages, for example, are supplied. It is your assignment to use appropriate data structures and algorithms (queues, stacks, hash tables, lists, string matching, etc.) to gather, catalog, and query a collection of pages.

The scope of this project is such that a good programmer (i.e., you) can get the engine working in a few afternoons/evenings. However, this is only possible if you spend time beforehand thinking about its overall structure and only then sitting down to implement a well-thought-out design.

You are encouraged to work in small teams (2-4) in which case you must implement a bit more (see below) than the basic mechanism. Let me know by April 16th if you are working in a team or solo. Also, if you want to be on a team but need a partner, mail me and I'll pair people (randomly).

Basic Mechanism

The basic operation of your internet search engine (ISE) might be as follows. There are two phases of operation: (1) the cataloging of web pages starting from a given URL and (2) the querying, for user keywords, of pages cataloged in the first phase. For example, the cataloging phase works as follows. From the unix prompt,
          $ java ISE "http://www.cs.swarthmore.edu/" 50
means to catalog at most 50 pages starting at the URL http://www.cs.swarthmore.edu/. After fetching the html page for http://www.cs.swarthmore.edu/, your engine will file the text of the page in a hash table indexed by URLs. Then, it will queue (or stack) the URLs found in the current page to be visited. While the queue (or stack) is not empty and the maximum number of pages has not been reached, this process repeats, adding new pages to the catalog and perhaps new URLs to the queue (or stack) of URLs to visit. Be sure never to visit a given URL more than once (to prevent looping) and to limit the number of cataloged pages (so as not to overload your network).

After the catalog is complete (text pages indexed by URLs in a hash table), prompt the user for a keyword K. Then, scan the text of all pages for K using a string-pattern-matching algorithm from lecture. If K appears in a page's text, output the corresponding URL, e.g.,

          http://www.cs.swarthmore.edu/ contains "college"
Your ISE may continue to prompt and search for further keywords.

What's Provided

Complete Java classes and methods are provided to fetch a web page from given a URL, to extract the text portion of an html web page, and to extract the URL links within a page. This code is available in ~lorenz/cs35-2/project/. Supplied code is subject to change during the course of the project; bugs will be fixed and necessary features added.

You may use the data structures and algorithms implemented by you for homework and lab, presented in lecture or lab, or from another source (e.g., the textbook) -- as always, attribute the source. You are not to use existing (compiled) Java classes such as the hash table or stack from the Java libraries.

Enhancements

If you are working in a team of size n, you must implement n-1 enhancements. Regardless of team status, you may of course implement as many enhancements as you wish; some extra credit, where needed (missed homeworks/labs, etc.), may be given pending my prior approval.

Here is a list of possible enhancements to the basic design:

Allow multiple keywords to be combined with "AND"/"OR" and negated with "NOT". For example, "college AND swarthmore" should only match pages containing both the word "college" and the word "swarthmore"; "college OR swarthmore" should match pages containing either "college" or "swarthmore". A query similar to "college AND NOT swarthmore" would list pages containing "college" but not "swarthmore".

Format the output of query results as an html file that can be loaded into a browser (so the user may click on the URL to get to the matching page).

Provide an option to visit URLs by the stack or queue discipline (instead of just by one).

Modify the supplied code to extract relative URLs in addition to the absolute URLs it now extracts.

Use hash tables to store the words of text in a fetched page instead of the arrays of strings returned from the supplied methods. (This can considerably reduce storage size and query lookup times.)

Code the project as an applet. Allow the URL to catalog as well as the keywords to be entered in a browser. Display the search results in the browser. (Counts as two enhancements.) (***This enhancement may not be possible since there are reports that Java may not allow applets to fetch pages.***)

Devise your own enhancements and have them approved by me.

Hand In

During finals week, hand in all code and documentation for your project. Also, make scripts that capture the full operation of your search engine (features and bugs).

We'll also arrange a time during finals week for a 5-10 minute demo of your project.