This machine problem is concerned with the very first stages of IR processing: transforming raw text into indexible tokens.
Most of this description will be in terms of the ''Artificial Intelligence Thesis'' (AIT) corpus we will use throughout the course, but you are encouraged to perform analogous processing on your own, personal Email files, too (for extra credit).
You are to work on this assignment in pairs. Immediately identify a partner with whom you will work on this assignment, and send Email to our TA (cs133s1) with both names and logins. Note that since each of you will be working with others on subsequent assignments, you must each identify and process your own Email corpus.
Write a basic parsing routine that reads through the textual corpora, identifies record and field breaks and extracts indexed fields for further processing.
In the case of the AIT corpus, will be treating each thesis abstract as a ``document''; in the case of Email, each message will be a document. Here are a couple of sample AIT records:
THESIS# 00001
AUTHOR: SHINN, HONG SHIK
YEAR: 1989
TITLE: A UNIFIED APPROACH TO ANALOGICAL REASONING
CLASSIF: MACHINE LEARNING
UNIVERSITY: GEORGIA INSTITUTE OF TECHNOLOGY (0078)
ADVISOR: JANET L. KOLODNER
ABSTRACT:
Experiential reasoning is the most basic form of intelligent activity,
consequently, in artificial intelligence, numerous computational models of
analogical or case-based reasoning have been attempted. As Winston points
out, however, there are no satisfying theories about the role of
abstraction in analogical reasoning. In this thesis, we present a ...
EOABSTRACT
THESIS# 00002
AUTHOR: SIMARI, GUILLERMO RICARDO
YEAR: 1989
...
For this assignment we will only be indexing TITLE and ABSTRACT fields. You are to write a parser that walks through all of the records found in ../public/mp/ait1 and ait2 and ait3 , identifies each record, and produces two files which will be used for subsequent processing.
The first file will be called files.d. This is a simple numbered list of all files to be indexed. Since there are only two files for the AIT corpus, files.d, wll look something like:
;;FileNo Path Date Size NBlock NMsg Out? 1 ''../public/mp/ait1'' ''1991/06/24 14:28:03'' 5709 1 2 0 2 ''../public/mp/ait2'' ''1991/08/19 15:15:41'' 47051 2 17 0
(where the first line is a label for each file's attributes). The pathname strings should be in a form that fopen(1) can use directly. In this example, other information about each file (its modification date, size, etc.) has also been maintained.
For your Email corpora, it is likely that there will be many more files containing them, and that routines (e.g., dirent) might be helpful for navigating through a directory in which they are all contained and collecting information about each file One useful Boolean attribute you may choose to keep about each Email file is whether it is Outgoing (i.e., whether it is a copy of mail you have sent, vs. mail that others have sent you.)
The second file, documents.d, contains a line for each document in each file mentoned in files.d. It should look something like:
;;FileNo MsgNo BPos TxtPos EPos NLines Proxy Date From (To) (Cc) 1 1 0 720 1619 50 '''' ''1995/06/12 10:02:10'' 1 (2 ) () 1 2 1620 2285 5708 97 ''AI Geneology'' ''1995/06/21 15:05:51'' 3 (2 ) (4 )
FileNo corresponds to an index into files.d; MsgNo is a document index within that file. The next three fields are character positions, as identified by ftell(1) and used by fseek(1). BPos is the beginning position of the document in the file; TxtPos points to the beginning of text to be indexed; and EndPos points to the end of the document.. In the case of the AIT corpus, TxtPos should point just after the ''Abstract'' delimiter. NLines tells the number of lines of text,. Proxy is a text string which is to be indexed as part of the document, and is also useful for characterizing it as part of retrieval hitlists. Again, the example shows additional attributes that might be useful for Email: who the message is from, to, carbon-copied-to, etc.
After you are successfully able to parse a document, the next task is to identify tokens that may function as potential indices. For this assignment, assume tokens may contain hyphens (-), underbars (_) and periods (.). Tokens may also include the digits 0-9 but not be entirely numeric (e.g., X123 is a valid token while 123 is not).
The next step is to remove very common, ``noise'' words. The technique we will use is to work from an extensional list of these words, sometimes called a ``negative dictionary.'' The list we will use is in /home/solaris/ieng9/cs133s/public/stop.wrd.
Write a routine stop_word() which returns TRUE if a token in any of the indexed fields is in this list, and FALSE otherwise. You should do your best to optimize the retrieval performance of this routine over stupid, linear searches of a list. For example, you might consider using binary trees like those provided by tsearch(3) or comparable data structures of your own. Some example code showing how to use tsearch is available for inspection in ../public/tsearch-example.c
If a user is interested in documents about CARS, they are likely to be interested in documents where the singular form of this word, CAR , is used as well. The morphological process of normalizing word tokens down to their essential roots is known in IR as stemming.
There is no way to do this task perfectly. Removing trailing S's is simple enough, but not every word that ends in S is a plural. Conversely, the ``number'' of some nouns is marked differently, e.g. WOMAN / WOMEN. Given the IR goal of merging tokens of similar ``meaning,'' there are many other suffices that should also be considered: -ING, -ED, etc. There are almost as many prefices that might also be removed. And, just as with trailing S's, any rule for making (token 1#1 stem) transformations will make mistakes.
For this assignment you are to begin the first portion of this task. You are to modify the Porter-style stemmer found in /home/solaris/ieng9/cs133s/public/mp/lib/stem/stem.c, augmenting the ``rules'' it incorporates with additional ones that you believe will make the stemmer more effective for this collection.
Create a directory morph in your home directory, and place all files named below in it.
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 morph directory, the appropriate sequence is:
tar cvf - morph | compress > morph.tar.Z turnin -c cs133w morph.tar.Z
Turning in after the first time overwrites your previously turned-in version.
This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 ../MP2Spec.tex.
The translation was initiated by Kevin Munroe on 1999-04-06