Due: 4 May 1999
Now that you have identified the individual documents in your corpus, the next step is to identifiy the lexical items you will index, and build an inverted list of them. But rather than treating stemming and noise words as two separate tasks, this time these lexical tasks will be combined. The major features of this process are discussed in Chapter 2, (esp. Section 2.2).
Begin with the files.d and docs.d provided in the AIT data directory. You should perform the same processing on (each of your) personal Email corpora as well.
You are to write a routine we will call postdoc that inverts all the documents in a corpora. More specifically, this routine will invert these documents creating,, for each keyword, a list of postings for all document containing that keyword. A template for the primary routine will be something like:
void postDoc (int docno, FILE *docf, long int bpos, long int epos, char *proxy){
...
GetTermString(&proxyPos, Noise, MaxTermSize,newterm);
...
GetTerm(docf, Noise, MaxTermSize,newterm);
...
InstallTerm( newterm, docno, Terms);
...
}
GetTerm is a routine corresponding to a lexical analyzer.and noise-word remover. The default, recommended routine for this purpose is one developed by Chris Fox; this can be found in the /home/solaris/ieng9/cs133s/public/mp/lib/stopper directory. GetTermString is a modified version of this routine designed to work on strings (like the documents proxy) rather than streams.
Each term returned, must be stored in an efficient data structure, and splay trees are recommended for that purpose. An implemetation due to David Brower can be found in /home/solaris/ieng9/cs133s/public/mp/lib/splay. The key piece of information retained is each documents unique docno and the number of times the term occurs in that document; this is known as a posting .
You should incorporate several (command line) options controlling these basic functions:
After all documents postings have been collected in this fashion, you are to write them all out in a the file inv-kw.d. For the AIT corpus, the beginning of the file will look something like:
;;token \t docfreq \t totfreq \t freq1 doclist1 \t ... aa 4 17 7 -1 1635 511 -2 2 -1 58 -2 1 -1 2004 -2 aashto 3 5 2 -1 953 3966 -2 1 -1 3287 -2 abandon 9 9 1 -1 621 1146 1147 1148 1510 1746 3032 4092 237 -2 abbrevi 6 7 2 -1 2529 -2 1 -1 482 772 1044 428 294 -2
docfreq and totfreq are the number of documents containing the keyword,, and the total number of times it occurs across all of them, resp. Following these data is a series of frequencies and lists of documents in which the keyword occurred with that frequency,, ordered in decreasing frequency order. (The document lists are delimited by two negative numbers, -1 and -2.) Please use the optimized data structure described in Figure 2.7 (page 46 of the textbook).
Then, write a simple utility to sort this file to produce a simple list skw.d of the resulting keyword vocabulary in descending total frequency order. For the AIT corpus, the beginning of the file will look something like:
system 21488 de 11923 model 11065 network 10306 base 9840 la 7678 knowledg 7411
In addition to the keyword files, you must also produce a second file, doclen.d, which lists the number of index terms associated with each document:
;; docno \t len 1 161 2 74 3 137 4 177
After completing this basic task,, you are to experiment with several modifications to the constituent routines.
Analyze the results of some changes you make to the default ( CFox) lexical analyzer on the AIT. corpus. Identify some of its worst errors and develop some modifications to its character classes or state transitions. In particular, perform these modifications:
For each of these, determine:
Create a subdirectory postdoc. in your home directory, and place all files named below in it. In all cases, use StemP=TRUE, MinDocFreq=3, EmphProxy=3.
To turn these in, you should make a compressed tar file of the directory and then run turnin to submit it for grading, before the due date for the assignment. Assuming you're in your home directory, which should contain your parse directory, the appropriate sequence is:
tar cvf - postdoc | compress > postdoc.tar.Z turnin -c cs133w postdoc.tar.Z
Turning in after the first time overwrites your previously turned-in version.
To make grading easier for the TA, please also print out hardcopies of:
This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -dir /cse/grad/mpetropo/ -split 0 /cse/grad/mpetropo/mp3.tex.
The translation was initiated by Michail PETROPOULOS on 4/21/1999