In Homework 3, you will be implementing ranked retrieval described in Lectures 7 and 8.
The indexing and query commands will use an identical input format to Homework 2, so that you need not modify any of your code to deal with command line processing. To recap:
$ python index.py -i directory-of-documents
-d dictionary-file -p
$ python search.py -d dictionary-file -p
file-of-queries -o output-file-of-results
We will also again use the Reuters training data set provided by
NLTK. Depending on where you specified the directory for NLTK data
whenyou first installed the NLTK data (recall that the installation is
triggered by nltk.download()), this data set is located under a path
As in Homework 2, your search process must not keep the postings file in memory in answering queries, but instead use a file cursor to randomly access parts of the postings file. However, there is no such restriction for the indexer (you are not asked to implement BSBI or SPIMI). Also, you should continue to employ Porter stemming in your submission, both for document indexing as well as query processing.
To implement the VSM, you may choose to implement (you can
can do it differently) your dictionary and postings lists in the
following format. The only difference between this format and that in
Figure 1.4 in the textbook, is that you encode term frequencies in the
postings for the purpose of computing tf×idf. The tuple in each
posting represents (doc ID, term freq).
|term||doc freq (df)||→
|ambitious||5||→||(1, 5)→ (7,2) → (21, 7) → ...|
In addition to the standard dictionary and postings file, you will
need to store information at indexing time about the document length,
in order to do document normalization. In the lecture notes and
textbook this is referred to as
Length[N]. You may store
this information with the postings, dictionary or as a separate file.
In the searching step, you will need to rank documents by cosine
similarity based on tf×idf. In terms of SMART notation of
ddd.qqq, you will need to implement the lnc.ltc ranking
scheme (i.e., log tf and idf with cosine normalization for queries
and log tf, cosine normalization but no
idf for documents. Compute cosine similarity between the query
and each document, with the weights follow the tf×idf
calculation, where term freq = 1 + log(tf) and inverse document
frequency idf = log(N/df) (for queries). That is,
tf-idf = (1 + log(tf)) * log(N/df).
It's suggested that you use log base 10 for your logarithm
math.log(x, 10), but be careful of
math.log(0, 10)). The queries we provide are
now free text queries, i.e., you don't need to use query operators
like AND, OR, NOT and parentheses, and there will be no phrasal
queries. These free text queries are similar to those you type in a
web search engine's search bar.
Your searcher should output a list of up to 10 most relevant (less if there are fewer than ten documents that have matching stems to the query) docIDs in response to the query. These documents need to be ordered by relevance, with the first document being most relevant. For those with marked with the same relevance, further sort them by the increasing order of the docIDs. Output these documents as a space delimited list as in Homework #2. Be sure not to include extra whitespace before and after any document IDs. For example, if document IDs 2, 1024 and 512 are only 3 relevant documents, in that order your searcher should output these document IDs one one line for the corresponding query:
2 1024 512
postings.txt. Please do not include the Reuters data.
You are also asked to answer the following essay questions. These are to test your understanding of the lecture materials. Note that these are open-ended questions and do not have gold standard answers. A paragraph or two are usually sufficient for each question. You may receive a small amount of extra credit if you can support your answers with experimental results.
You are allowed to do this assignment individually or as a team of two. There will be no difference in grading criteria if you do the assignment as a team or individually. For the submission information below, simply replace any mention of a matric number with the two matric numbers concatenated with a separating dash (e.g., A000000X-A000001Y).
For us to grade this assignment in a timely manner, we need you to adhere strictly to the following submission guidelines. They will help me grade the assignment in an appropriate manner. You will be penalized if you do not follow these instructions. Your matric number in all of the following statements should not have any spaces and any letters should be in CAPITALS. You are to turn in the following files:
README.txt: this is a text only file that describes any information you want me to know about your submission. You should not include any identifiable information about your assignment (your name, phone number, etc.) except your matric number and email (we need the email to contact you about your grade, please use your A*******@(nus.edu.sg|u.nus.edu) address, not your email alias). This is to help you get an objective grade in your assignment, as we won't associate matric numbers with student names.
ESSAY.txtthat contains your answers to the essay questions.
These files will need to be suitably zipped in a single file called
<matric number>.zip. Please use a zip archive and
not tar.gz, bzip, rar or cab files. Make sure when the archive unzips
that all of the necessary files are found in a directory called
<matric number>. Upload the resulting zip file to the IVLE
workbin by the due date: 17 March 2017,
11:59:59 pm SGT. There will absolutely be no extensions to the
deadline of this assignment. Read the late policy if you're not sure
about grade penalties for
The grading criteria for the assignment is tentatively:
Disclaimer: percentage weights may vary without prior notice.
read(). Another Python module to look at is
linecache. Please look through the documentation or web pages for these.
-i) are correctly interpreted (add trailing slash if needed). Check that your output is in the correct format (docIDs separated by single spaces, no quotations, no tabs).
<) but you can safely ignore them; you do not have to process these in any special way for this assignment.