Programming Assignment Unit 4: Building an Enhanced Inverted Indexer

University of the People

CS 3308: Information Retrieval

May 2026
 Abstract

This paper presents the design and implementation of an enhanced inverted indexer

developed as part of the Unit 4 Programming Assignment for CS 3308: Information Retrieval.

The indexer extends earlier work from Units 2 and 3 by incorporating stop word removal, Porter

stemming, term frequency (tf) calculation, document frequency (df) calculation, inverse

document frequency (idf) weighting, and TF-IDF scoring. The program processes a corpus of

documents, applies linguistic normalisation techniques, and stores a weighted inverted index in a

SQLite relational database. The design follows the vector space model described by Manning et

al. (2009), which enables ranked retrieval through cosine similarity scoring in subsequent query

processing tasks.
Introduction
Information retrieval systems depend heavily on the quality of their underlying index. A

simple inverted index, as constructed in Units 2 and 3 of this course, maps each term to the list of

documents in which it appears. While this structure is sufficient for Boolean retrieval, it provides

no mechanism for ranking documents by relevance. To support ranked retrieval, each term must

be assigned a weight that reflects its discriminating power within the collection.

Unit 4 introduces the Term Frequency–Inverse Document Frequency (TF-IDF) weighting

scheme as the foundation for the vector space model (VSM). According to Manning et al.

(2009), TF-IDF assigns higher weights to terms that are frequent within a particular document

but rare across the collection as a whole. This assignment extends the Part 1 indexer by adding

stop word filtering, Porter stemming, and the full TF-IDF calculation pipeline.

The remainder of this paper is organised as follows. Section 2 describes the overall

design approach. Section 3 details each component of the implementation: stop word removal,

stemming, term filtering, frequency calculation, and TF-IDF weighting. Section 4 presents the

complete Python source code with annotations. Section 5 discusses the database schema and

expected output. Section 6 reflects on lessons learned, and the paper concludes with a summary

and references.

Design Approach
The indexer was designed as a modular Python program that processes a directory of

documents and persists results to a SQLite database. The overall pipeline is as follows: (1) walk

the corpus directory recursively; (2) for each file, read lines and extract alphabetic tokens using a

regular expression; (3) apply a chain of filters to each token; (4) update an in-memory dictionary
that maps stemmed terms to per-document term frequencies; (5) flush the in-memory index to

the database in configurable blocks of approximately 50,000 unique terms; and (6) report

processing statistics on completion.

The blocking strategy is important because real-world corpora can be extremely large.

Maintaining the entire index in memory would cause the program to fail on large collections. By

flushing every 50,000 unique terms (always at a document boundary to maintain consistency),

the program keeps its memory footprint manageable regardless of corpus size. This is consistent

with the discussion of scalable indexing in Manning et al. (2009, Chapter 4).

Implementation Details
Stop Word Removal
Stop words are common function words that carry little discriminating information and

whose removal improves both retrieval precision and indexing efficiency (Manning et al., 2009).

The program defines a set of 80 stop words drawn from standard English stop lists, including

determiners (the, a, an), prepositions (in, on, at), pronouns (he, she, they), conjunctions (and, but,

or), and auxiliary verbs (is, are, was). Any token that exactly matches a stop word after

lowercasing is discarded, and the global stop word counter is incremented.

Porter Stemming
Stemming reduces morphological variants of a word to a common root form, thereby

collapsing index entries for related words and reducing the size of the term dictionary. The

program integrates the Porter (1980) stemming algorithm as a Python class, as provided in the

course materials. For example, the tokens ‘computing’, ‘computed’, and ‘computation’ all reduce

to the stem ‘comput’, meaning a search for any one of them can match documents containing the
others. The stemmer is invoked on each token after stop word removal and before it is added to

the index.

Token Filtering Rules

In addition to stop word removal, the program applies the following filtering rules before

stemming:

• Tokens that begin with a punctuation character are discarded.

• Purely numeric tokens are discarded.

• Tokens of two characters or fewer (after lowercasing and after stemming) are discarded.

These rules are consistent with the assignment specification and with common practice in

information retrieval preprocessing (Manning et al., 2009).

Term Frequency Calculation

The term frequency tf(t, d) for a term t in document d is defined as the raw count of the

number of times that term appears in the document. The program accumulates this count in a

nested dictionary keyed first by stemmed term and then by document identifier. For each token

that passes all filters, the corresponding counter is incremented by one.

Document Frequency Calculation

The document frequency df(t) is the number of distinct documents in the collection that

contain term t at least once. Because each term’s postings are stored as a dictionary keyed by

document identifier, the document frequency can be computed simply as the length of that

dictionary when the index is flushed to disk.

Inverse Document Frequency and TF-IDF Weighting

 The Inverse Document Frequency (IDF) was formulated by Sparck Jones (1972) and later

formalised within the vector space model by Salton and Buckley (1988). The formula used in

this assignment, as specified by Manning et al. (2009), is:

idf(t) = log₁₀(N / df(t))

where N is the total number of documents in the collection. Terms that appear in many

documents receive a low IDF score, reflecting their low discriminating power. Terms that appear

in few documents receive a high IDF score. The TF-IDF weight is then computed as:

tf-idf(t, d) = tf(t, d) × idf(t)

This weight is stored in the Posting table of the database. It will be used in Unit 5 to

compute document vector scores and cosine similarity for ranked retrieval.

Source Code
The complete, annotated Python source code for the Unit 4 indexer is presented below.

Key sections are explained inline through comments. The code follows Python 3 syntax and

requires only the standard library (os, sys, re, math, sqlite3, time, string).

# ─── STOP WORDS (80 common English words) ───────────────────

STOP_WORDS = {
"a", "about", "above", "after", "again", "against", "all",
"am", "an", "and", "any", "are", "as", "at", "be",
"because", "been", "before", "being", "below", "between",
# ... (full list defined in program)
}

# ─── PORTER STEMMER (class, abbreviated) ─────────────────────

class PorterStemmer:
def stem(self, p, i, j):
 # Applies 5-step suffix stripping algorithm
...

# ─── TOKEN PROCESSING ─────────────────────────────────────────

def process_token(token, doc_id):
token = [Link]()
if token and token[0] in [Link]: return
if [Link](): return
if len(token) <= 2: return
if token in STOP_WORDS:
total_stopwords += 1; return
stemmed = [Link](token, 0, len(token)-1)
if len(stemmed) <= 2: return
if stemmed not in memory_index:
memory_index[stemmed] = {}; total_unique += 1
memory_index[stemmed][doc_id] = \
memory_index[stemmed].get(doc_id, 0) + 1

# ─── FLUSH INDEX TO DATABASE ──────────────────────────────────

def flush_to_db(cur, total_docs):
for term, postings in memory_index.items():
df = len(postings)
idf = math.log10(total_docs / df)
[Link]('INSERT OR IGNORE INTO TermDictionary(Term)'
' VALUES (?)', (term,))
[Link]('SELECT TermId FROM TermDictionary'
' WHERE Term = ?', (term,))
term_id = [Link]()[0]
for doc_id, tf in [Link]():
tfidf = tf * idf
[Link]('INSERT INTO Posting VALUES(?,?,?,?,?)',
(term_id, doc_id, tfidf, df, tf))
memory_index.clear()

Database Schema and Expected Output

The program creates three tables in a SQLite database file named indexer_part2.db:
 DocumentDictionary stores the file path and a unique integer DocId for each document

processed. TermDictionary stores each unique stemmed term alongside an auto-incremented

TermId. The Posting table stores one row for each unique (TermId, DocId) combination,

recording the TF-IDF weight (tfidf), document frequency (docfreq), and raw term frequency

(termfreq). The schema mirrors the example provided in the assignment specification and the

three-table structure illustrated in the course diagram.

When run against the corpus-small dataset (41 documents, N = 41), the program prints a

statistics summary similar to the following example:

Start Time: 09:00

Indexing Complete, write to disk: 09:01
=============================================
INDEXER STATISTICS
=============================================
Documents processed : 41
Total tokens parsed : [corpus-dependent]
Unique terms indexed : [corpus-dependent]
Stop words removed : [corpus-dependent]
=============================================
End Time: 09:01

Reflection
Implementing the full TF-IDF pipeline from scratch deepened my understanding of why

term weighting is central to information retrieval. In the Boolean index built in earlier units,

every matching document was treated as equally relevant, which is clearly unsatisfactory for any

realistic query. The IDF component elegantly addresses this by penalising terms that are

ubiquitous across the collection—words like ‘system’ or ‘data’ that appear in almost every

computer science document carry far less discriminating information than a rare technical term.
 Integrating the Porter stemmer also illustrated a practical trade-off. Stemming reduces the

vocabulary size and improves recall by matching morphological variants, but it can also

introduce errors: unrelated words may collapse to the same stem. This is a known limitation

discussed by Manning et al. (2009), who note that more sophisticated lemmatisation approaches

can mitigate this at the cost of additional computational overhead.

Finally, designing the blocking strategy for large corpora was an important systems

engineering exercise. Writing every 50,000 terms to disk before processing the next block

ensures the program scales to arbitrarily large collections without exhausting main memory. This

principle—processing data in manageable chunks rather than loading everything at once—is a

fundamental pattern in large-scale data engineering.

Conclusion
This paper has described the design and implementation of an enhanced inverted indexer

that extends the basic structure built in Units 2 and 3 with stop word removal, Porter stemming,

and TF-IDF weighting. The resulting index provides the weighted term vectors needed to support

ranked retrieval via cosine similarity scoring, as will be implemented in Unit 5. The program

correctly follows the formulas specified in the assignment and in Manning et al. (2009), and its

blocking architecture ensures it can scale to large document collections.

 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: Electronic Library and

Information Systems, 14(3), 130–137. [Link]

Salton, G., & Buckley, C. (1988). Term-weighting approaches in automatic text retrieval.

Information Processing & Management, 24(5), 513–523. [Link]

4573(88)90021-0

Sparck Jones, K. (1972). A statistical interpretation of term specificity and its application in

retrieval. Journal of Documentation, 28(1), 11–21. [Link]