CSE 382 Algorithms and Data Structures
Barbara Nostrand, Ph.D.
Electrical Engineering and Computer Science
In this project, you will be designing and implementing a mini search engine. You are probably familiar with Google, Altavista or Yahoo, which are some of the most popular search engines that you can find on the Web. The task performed by a search engine is, as the name says, to search through a collection of documents. Given a set of texts and a query, the search engine will locate all documents that contain the keywords in the query. The problem may be therefore reduced to a search problem, which can be efficiently solved with the data structures we have studied in this course.
Your task is to design and implement an algorithm that searches a collection of documents. You will be provided with a set of 50 documents and a set of sample queries. You have the freedom to select the data structures and algorithms that you consider to be more efficient for this task. Of course, you will have to justify your decisions. First, you will process the documents and store their content (i.e. words / tokens) in the data structures that you selected (in information retrieval, this phase is called indexing). Next, for every input query, you will process the query and search its keywords in the documents, using the previously implemented data structures and an algorithm of your choice. (This phase is called retrieval.) For each such query, you will have to display the documents that satisfy the query.
The queries may contain simple Boolean operators, that is AND and OR, which act in a similar manner with the well known analogous logical operators. For instance, a query: "Keyword1 AND Keyword2" should retrieve all documents that contain both these keywords (elements). "Keyword 1 OR Keyword 2" instead will retrieve documents that contain either one of the two keywords.
Doc1: I like the class on data structures and algorithms. Doc2: I hate the class on data structures and algorithms. Doc3: Interesting statistical data may result from this survey.Here are the answers to some queries:
Query 1: data Doc1, Doc2, Doc3 Query2: data AND structures Doc1, Doc2 Query 3: like OR survey Doc1, Doc3
First, download the sample documents, and take a look at their format. You will have to parse these files. You may ignore all lines starting with "<", these SGML tags are similar to HTML tags and are useful for certain tasks, but you will probably not find them very useful in this project. The punctuation is already separated from the words, so you do not have to worry about that. You will have to read one word at a time and add it to your data structure. As data structures, you may consider using dictionaries / hashtables, trees – such as 2-4 trees, AVL trees, balanced binary search trees. Any other data structures are admissible as well – although, again, you have to be able to justify your selection. For every word, you should store a list of documents where it occurs, in order to allow for efficient searches and Boolean operators later on.
There are three main parts in this project, all of them contributing to the final project grade.