Unit 4 Assignment
Course: Information Retrieval / CS 3308
2025-09-29
1. Introduction
This assignment extends the inverted index built in previous units by adding token editing (stop
words removal, punctuation filtering, and stemming) and calculating term weights needed for
scoring in the vector space model. The indexer writes three SQLite tables (DocumentDictionary,
TermDictionary, Posting). The document below describes methods, statistics, and worked
examples using the actual index output.
2. Methods
Tokenisation and cleaning steps applied to each document:
• Tokenisation: Split on non-alphanumeric characters.
• Cleaning rules: Removed tokens that begin with punctuation; ignored numeric tokens; ignored
tokens of length ≤ 2; removed stop words (about 100 common words).
• Stemming: Applied the Porter stemmer to reduce words to their root form (example:
computing → comput).
• Indexing and weighting: For each stemmer token, the indexer records term frequency (tf) per
document, computes document frequency (df) per term, then computes idf = ln(N/df) and tf-idf
= tf × idf.
3. Corpus Statistics
Start Time: 15:28
Indexing Complete, computing idf & writing to DB: 15:28
Documents 570
Unique stems (terms) 2472
Tokens 37470
Stop words skipped 1766
End Time: 15:30
4. Index Structure
The index is stored in an SQLite database with three tables:
• DocumentDictionary(DocumentName, DocId), maps each file to DocId.
• TermDictionary(Term, TermId), maps each stem to TermId.
• Posting(TermId, DocId, tfidf, docfreq, termfreq), contains term frequency per document,
document frequency and tf-idf weight.
5. Worked examples: TF, DF, IDF, TF-IDF
Below are three example terms from the index with calculations. N = 570
1. Term: algorithm (TermId: 162)
• Document frequency (df): 217
• Inverse document frequency (idf): ln(N/df) = ln(570/217) = 0.9657390073
• Total term frequency in corpus: 228
DocId tf tfidf (from postings)
284 4 3.862956
371 3 2.897217
124 2 1.931478
199 2 1.931478
409 2 1.931478
2. Term: comput (TermId: 19)
• Document frequency (df): 113
• Inverse document frequency (idf): ln(N/df) = ln(570/113) = 1.6182485421
• Total term frequency in corpus: 154
DocId tf tfidf (from postings)
417 5 8.091243
322 4 6.472994
252 4 6.472994
68 4 6.472994
103 3 4.854746
3. Term: program (TermId: 25)
• Document frequency (df): 70
• Inverse document frequency (idf): ln(N/df) = ln(570/70) = 2.0971411188
• Total term frequency in corpus: 115
DocId tf tfidf (from postings)
71 11 23.068552
46 7 14.679988
396 6 12.582847
278 5 10.485706
252 4 8.388564
6. Document vector example
Example document chosen: DocId 71
Sample high-weight terms (from postings for this document):
Term tf idf tfidf
program 11 2.0971411188 23.068552
construct 3 4.2661948191 12.798584
comput 3 1.6182485421 4.854746
facil 3 5.6524891803 16.957468
html 2 0.0000000000 0.000000
Document vector length ||d|| (L2 norm) = 54.717585
Calculation (partial): sum of squares of tf-idf for selected terms = (23.068552)^2 + (12.798584)^2
+ (4.854746)^2 = then sqrt = 54.717585
7. Sample query ranking
Query used: "algorithm comput" (two terms). Steps:
1) Compute query weights: w_t = tf_in_query × idf_t.
2) Compute normalized document weights and dot product with query.
3) Cosine similarity = dot / (||q|| × ||d||).
Top 5 documents returned by the index for the query 'algorithm comput':
DocId Cosine score
93 0.225689
80 0.171105
57 0.165634
357 0.165482
252 0.158132
8. Conclusion
This indexer meets the Unit 4 requirements: it removes stop words and short or punctuation-
leading tokens, applies Porter stemming, computes tf and df, and builds tf-idf weights stored in
a Posting table. The tf-idf weights can be used to compute cosine similarity between queries and
documents, which allows ranked retrieval of the most relevant documents.
References
Manning, C. D., Raghavan, P., & Schütze, H. (2009). An Introduction to Information Retrieval
(online ed.). Cambridge University Press. [Link]
[Link]
Porter, M. F. (1980). An algorithm for suffix stripping. Program, 14(3), 130–137.
[Link]