CSE 373 Programming Project 1

The Problem

Of course, the retrieval system should not have to search through millions of papers every time someone enters a key word. So they usually use data structures to make the retrievals efficient. The most common structure is the inverted index. The key words are all kept in this index, and each one points to a list of all the articles that have that key word. The index itself can have various structures, but we will just use an array in which the key words appear in alphabetical order (and we'll use key words that have no spaces in them).

Our structure will be an array of keyword objects. Each element will have a keyword and a list pointer. They array is kept in ascending order according to the keywords. e.g.

• database
• EM-algorithm
• image-retrieval
• matching
• recognition

Your Job

1. The first part reads in the IDs, titles, authors, and keywords for a set of articles and creates the inverted index. You should use the binary search algorithm given in Chapter 2 of your text to find the right position in the array for a given keyword. Then if the keyword is already in the array, you merely add a new element for the new article to its list (at the beginning, since it's O(1) time). If, however, the keyword is not already in the index, you have to insert it. Since the list is in an array, you will have to move down all the elements below it by one position. (When we get to more advanced structures, insertion will be more efficient.)

2. The second part reads a given list of keywords and for each one, finds all the articles with that key word and prints the information about each one in the format we give you (so we can grade them easily). Since you will again use binary search to find the keywords, the search part will be O(log N) if there are N keywords in the index. The printing part for one such keyword will be O(K) if there are K articles with that keyword, because you must go through the entire list to print the elements.

Details

The index is an array Keywords, each element of which is an object of type KeyWord. The array has some number MAX_KEYWORD_COUNT of elements (use 500). The variable currentCount gives the current number of elements, which is 3 in the picture ('data', 'image', and 'search'). Each KeyWord object has two fields: keyword and records. The keyword field contains the keyword and the records field contains a pointer to (eventually) all articles having that keyword. In the picture, the keyword 'data' has an associated pointer to a list of 2 articles. The information about an article is kept in a Record object, which has four parts: id, title, author, and next.

We will give you a class called FileData that allows you to open a file, read the information for each article (its id, title, author and keywords), and close the file. You will develop the class Index with the methods to create and populate the index and the class AnswerQueries with the methods to query the index with a given keyword and print the keyword plus the information for each associated article.

Index

1. Read the information for the next article from the file. (If the end of file is reached, this part is done.)

2. Create a Record for the article.

3. For each keyword associated with that article:
   • Search for the keyword (by binary search) in Keywords.
   • If it is there, add this Record to the associated list of articles.
   • If it is not there, add the keyword to the array Keywords and make its records pointer point to the new Record.

Here are two examples of articles:

46359
A Content-Based Retrieval System for Medical Images
John Anderson
4
database
image-retrieval
content-based
medical

37503
The Virage Search Engine
James Bach
3
image-retrieval
search
image-management

AnswerQueries

Code Download

Turnin