COP 2805 (Java III) Project
Building a Search Engine, Part III:  Collections

Due: by the start of class on the date shown on the syllabus

Background:

Please read the background information and full project description from Search Engine Project, Part I.

In this final part of the project, you will complete the application by implementing the index functions.  These include adding a file to the index, and removing a file from the index, and reading and writing the index from/to a file.  (Updating the index when a file has been changed, can then be done by removing and then re-adding a file.)  Other operations include searching the index for a given word, and returning a Set of pairs (document ID and position) for that word.

Finally, you will have to implement the Boolean search functions of the main user interface.  (This is complex enough, that it should have been another project!)  I suggest you start with an “OR” search, then worry about implementing the “AND” and “PHRASE” search functions.

When building the index, keep in mind you will need to define what you mean by “word”.  One possibility is to strip out any non-digits or letters, and convert the result to all lowercase, both when you build the inverted index and when you read the search terms entered by the user.  Ideally, you can use the I18N methods discussed in class to normalize the words.

Implementing Boolean Search:

The exact method depends in part on how you implement the inverted index.  In the suggested implementation (a Map with words as the keys, and a List or Set of (document ID, position) pairs as the values), you could implement the Boolean searches using algorithms similar to the following (you can come up with your own if you wish):

OR Search

This is the easiest one to implement.  The general idea is to start with an empty Set of matching files.  Then add to that Set, the files containing each search term; Just search the Map for that word, and add each document found (if any).  The result is the OR search results, the files that contain any word in the search list.  (If user inputs no search words, say “ ,.”, then no files are considered as matching.)

AND Search

This is done the opposite way from an OR search, and is only a little harder to implement.  The idea is to start with a set of all files in the index.  Then for each search term, for each file in the Set, make sure that file is contained in the index for that search term.  Remove any files from the set that don't contain that word.  The resulting final set is the documents matching all search terms.  (If user inputs no search words, say “ ,.”, then all files are considered as matching.  If that isn't the behavior you want, you need to treat that as a special case.)

PHRASE Search

This is the hardest search to implement.  Unlike the OR and the AND searches, with PHRASE searching, the position of the search terms in the files matters.  The algorithm I came up with is:

Part III Requirements:

The class must work in groups of three or four students per group.  Any student not part of a group must let the instructor know immediately.  In this case, the instructor will form the groups.

This project has been split into three parts.  Each part counts as a separate project.  In the first two parts, your group designed and implemented a (non-functional) graphic user interface for the application, and added all required file operations.

In this part, you must implement the remaining operations of your search engine application: the index operations, and the searching.

You can download a Search Engine model solution, to play with it and inspect its user interface, but please keep in mind you should not copy that user interface; instead, invent a better, nicer-looking one.

Hints:

Keep your code as simple as possible; worry about clever extras in version 2.  (You can always add features later, time permitting.)  If you start with a complex, hard-to-implement design, you may (will!) run out of time.

The inverted index is naturally a Map, from words (the keys) to a Set of objects (the values).  Each of the objects represent a document and a location within that document, where the word was found.  I called these objects Pairs, since they are a pair of numbers, but you can use any name for your classes.  Note, you will need to be able to go from a document number to a file name, when you display the search results.

How your group is organized is up to the group members.  Some suggestions include:

To Be Turned in:

A single copy of your group's Java source code files (including the file format document), your individual ratings (see below), and the answers to the following questions:

  1. In the event your search turns up multiple “hits”, how could you order the results to have the most relevant results listed first?  (You don't have to implement this, just think about how it could be done with your design.)
  2. What changes would you have to ignore the 30 most common words?  (Real search engines do this so words such as “the”, “and”, “a”, and so on don't waste memory or time.  This is called a stop list.)
  3. Suppose you wanted to scale up your search engine, so that the full index doesn't fit completely in memory.  How could that be done?

You only need to submit one time for your whole group.  Be sure the names of all group members are listed on all files.  You should use the CVS server, email, Facebook, Skype, or any means you wish, to communicate within your group.

Grading will be done for the group's results, and individuals in the group will have their grades adjusted by peer ratings.  A rating of each team member's level of participation should be sent by individually by every member, directly to the instructor.  Be sure to include yourself in the ratings!  The rating is a number from 0 (didn't participate at all), 1 (less than their fair share of the work), 2 (participated fully), or 3 (did more than their fair share of the work).

One person in your group can send as email to (preferred), with a “CC” for all the other group members.  If email is a problem for some reason, you may turn in a hard-copy.  In this case the pages should be readable, dated, and stapled together.  Your name should appear on the first page.

Please see your syllabus for more information about projects, and about submitting projects.