Search engines are, at their heart, remarkably simple programs. In this project, you'll be building a search engine for files in a UNIX file system. There are two essential components to every search engine, including yours:
- The crawler. this is the part of the program that
"crawls" through the set of documents, building up an
"index" of the content in those documents. The crawler
component of your program will sift through the files in a subtree
of a Unix file system, looking for text files: files that end in
.txt, which we assume contain a set of whitespace and
punctuation separated ASCII words. Your crawler will read in all of
these files, parse them to extract all of the words in the document,
and then add the words to an index.
- The index. this is the part of the program that keeps track of which words were found in which documents in the file system. You will be building a hashtable-based "inverted index". An inverted index is simply a table that maps a word to the set of documents that contain that word.
The Crawler
When launching your program, you will give it a command-line argument: the "root" of the directory subtree to crawl. For example, you may invoke your program like:
[fiji.cs]$ ./textcrawler foo/bar/baz
if you want it to start crawling at the foo/bar/baz directory. The crawler needs to crawl through the directory tree rooted at the specified directory, by recursively looking at all files and subdirectories, starting at the specified root. You will be relying on various system calls to do your crawling, including:
- man 3 opendir
- man 3 readdir
- man 2 stat
- man 3 ctime
- man 3 fopen
- man 3 fgetc
You should watch out for the directories "." and "..", and not follow them, because they point to the "current" directory and the "parent" directory, respectively, and thus will break recursion. Symbolic links of both directories and files should be ignored as well; not doing so will result in files being read in multiple times or infinite recursion if the link is to an ancestor directory. For all files that end in ".txt", the crawler should read through the file and read in all words, converting all characters to lower case, and making sure that the "words" do not contain any punctuation.
The Inverted Index
An inverted index is a hash table with the words pulled from the .txt files used as the keys and information about the files that contained them as the stored value. The hash table need not be fancy. If you use a chained hash table, you can handle any number of words without resizing (though not efficiently). A possible way to hold the file information is in a vector, where the hash table simply holds the index of the appropriate file in the "File List" vector.
Putting it all together
Once the crawler has built the inverted index, you need to be able to search for any words that were found and indexed. The file information that should be returned by the search needs to include the document name, its size, # times the word occurred in the file, when it was last modified, and the first few words from the file. The following is an example session for the textcrawler:
fiji:~$ ./textcrawler ./txtfiles
... crawling ...
... done ...
Search term: fox
(1) ./txtfiles/singleton.txt
Size: 246 bytes
Occurrences: 1
Last modified: Fri Mar 28 10:56:32 2003
"such the fox jumped memphis..."
(3) ./txtfiles/gutenburg/hamlet.txt
Size: 193043 bytes
Occurrences: 1
Last modified: Sat Mar 29 07:08:53 2003
"Project Gutenberg Etext of Hamlet..."
Search term: foo
"foo" not found.