Description
Introduction
In this assignment, you will build indexes for a corpus and implement several information
retrieval algorithms with the Lemur Toolkit (http://www.lemurproject.org/) in C/C++.
Both the text document collection and the incomplete implementation of a retrieval system can
be found in a light version of the Lemur toolkit (see Instructions below). The light version only
runs on Unix/Linux. You should remotely Login to the Engineering Computing Center’s Linux
machine (ftp.engr.scu.edu) by using ssh or putty to complete this assignment.
Instructions
Follow the procedures below to install the light Lemur toolkit:
1. Login to the Linux machine (ftp.engr.scu.edu). Use the following command
wget http://www.cse.scu.edu/~yfang/lemur.tar.gz
to get the toolkit.
1. Use “gzip -d lemur.tar.gz” and “tar -xvf lemur.tar” to uncompress and unpack the package.
2. Enter the lemur root directory and use “./configure” to configure the Lemur toolkit
3. Use “gmake” in the lemur root directory to compile the package
4. Every time you change the code go to the lemur root directory to rebuild the code by “gmake”
There are two directories under the lemur root directory that are particular useful. The
“eval_data/” directory contains the text document collection (i.e., database.sgml) to analyze and
several parameter files to run the retrieval system. The “app/src/” directory contains the code of
the applications. “BuildIndex.cpp” is the application for building indexes (complete).
“RetrievalEval.cpp” is incomplete, which you will work on.
Implementation of several retrieval algorithms
In this task, you are going to use lemur toolkit for retrieval and implement several retrieval
algorithms by yourself. First, please build the inverted index files. Enter the directory of
“eval_data” under the light Lemur root directory. Use the command “../app/obj/BuildIndex
build_param database.sgml” to build the index files with raw text data. Use the command
“../app/obj/BuildIndex build_stemmed_nostopw_param database.sgml” to build the index files
with text data processed by stemming and removing stop words.
The source file “RetrievalEval.cpp” under “app/src/” contains several retrieval algorithms.
Please read through the annotated code to understand the framework. Different retrieval
algorithms have different implementation of functions as computeMETHODWeight and/or
computeMETHODAdjustedScore (METHOD should be replaced by the names of different
retrieval method like RawTF). The retrieval score of a document (D) with respect to a query (Q)
is calculated as follows:
S(Q, D) = scoreAdjust(Weight(q1
,d1
,Q,D) + … + Weight(qN
,dN
,Q,D), Q, D)
Where computeMETHODWeight calculates the value of the Weight function for a
matched term of a document and a query; computeMETHODAdjustedScore is used to
calculate the value of scoreAdjust function (e.g., for score normalization).
One simple retrieval algorithm “RawTF” has been implemented. You can refer to the
code for implementing other retrieval algorithms.
To play with Lemur toolkit and implement your retrieval algorithm, please complete the
following experiments:
1. Test the performance of retrieval algorithm “RawTF” with two types of text data
(i.e., raw text data and text data by stemming and removing stopwords). (20 points)
Enter the directory of “eval_data” under the light Lemur root directory. Use the command
“../app/obj/RetrievalEval eval_param query” to generate the result file (i.e., result_rawtf)
of the RawTF retrieval algorithm for the raw text data. Use the command
“../app/obj/RetrievalEval eval_stemmed_nostopw_param query_stemmed_nostopw”
(before this please set the weight scheme parameter in param file to RawTF and set
corresponding name of result file by the result parameter) to generate the result file (i.e.,
result_rawtf_stemmed_nostopw) of the RawTF retrieval algorithm for the text data by
stemming and removing stopwords.
2. Evaluate the results by using “../trec_eval qrel result_rawtf” and “../trec_eval qrel
result_rawtf_stemmed_nostopw”. Please include the results in your report. Can you
tell which result is better? If one is better than the other, please provide a short
analysis. Please answer what stemmer is used in the index. Can you also use another
stemmer and compare the results? The instruction of how to defining the BuildIndex
parameter file can be found at
http://www.cs.cmu.edu/~lemur/3.1/indexing.html#BuildIndex
3. Evaluate the results by NOT removing the stopwords. A stopword list is contained in
eval_data/stopwordlist. You need to modify the parameter file (e.g., remove
stopwordlist in build_stemmed_nostopw_param) when
apply BuildIndex.
Please provide a short analysis on whether removing stopwords helps or not.
2. Implement three different retrieval algorithms and evaluate their performance.
(80 points)
You only need to change the computeMETHODWeight functions of the three algorithms.
The weight functions of the three algorithms and the RawTF method (implemented) are:
In order to obtain statistics like the average document length, please check the reference
of Lemur::api::index class. More general information about Lemur classes can be found here.
Please check the parameters of weightingScheme and resultFile within
“eval_stemmed_nostopw_param” for different retrieval algorithms. Follow the step in task 1 to
generate the evaluation results.
In summary, you need to generate the results (Average Precision) with different combinations of
retrieval models and preprocessing steps and fill in the table as below
RawTF weight(q , d , Q, D) erm_freq eight(q )
t t = t (d )
t * w t
RawTFI
DF
weight(q , d , Q, D) erm_freq og eight(q )
t t = t (d )
t * log l (
totalNumDocs
numDocsContain(term_t) ) * w t
LogTFI
DF
weight(q , d , Q, D) log(term_freq og eight(q )
t t = ( (d )) )
t + 1 * log l (
totalNumDocs
numDocsContain(term_t)) * w t
Okapi weight(q , d , Q, D) og t t =
term_freq(d )t
term_freq(dt)+0.5+1.5
len(D)
avgDocLen
* log l ( numDocsContain(term_t)+0.5
totalNumDocs−numDocsContain(term_t)+0.5
) * 7+weight(q )
t
8+weight(q )t
Please compare the results and provide a short discussion about the advantage/disadvantage of
the algorithms.
What to turn in
1. Please write a report of your experiments.
2. Please attach the hardcopy of your code (RetrievalEval.cpp) with the report.
Remove
Stopwords &
Stemming
Remove
Stopwords & No
Stemming
No Removing
Stopwords &
Stemming
No Removing
Stopwords & No
Stemming
RawTF
RawTFIDF
LogTFIDF
Okapi
