NLP Lab Assignment
Desktop Search Engine using Inverted Index (50,000+ Files)
1. Overview
In this lab, you will build a desktop keyword search engine capable of indexing more than
50,000 local files and retrieving relevant documents using an inverted index.
You must implement the following vector variants:
• • Boolean / Binary Vectors
• • Count / Frequency Vectors
• • TF–IDF Vectors
You must implement the following similarity measures:
• • Inner Product (Dot Product)
• • Cosine Similarity
Bonus Features:
• • Phrase Queries (e.g., "Punjab University")
• • Proximity Queries (e.g., Pakistan Cricket ^5)
2. Learning Outcomes
By completing this lab, you will:
• • Build and store a scalable inverted index.
• • Implement tokenization and normalization.
• • Construct Boolean, Count, and TF–IDF vectors.
• • Implement ranking using dot product and cosine similarity.
• • Support phrase and proximity queries (bonus).
3. System Requirements
A. Dataset Requirements
• • Index at least 50,000 files.
• • Support at minimum .txt files.
• • Maintain docID to file path mapping.
B. Preprocessing Pipeline
• • Recursive file discovery.
• • Text extraction.
• • Tokenization and lowercasing.
• • Punctuation removal.
• • Optional: Stopword removal.
• • Optional: Stemming or Lemmatization.
C. Inverted Index Structure
Your inverted index must store:
• • Term → Postings List
• • Postings entries: (docID, term frequency)
• • Document frequency (df)
• • Document vector norms (for cosine similarity)
The index must be saved to disk and reloadable without rebuilding.
4. Vector Variants
1. Boolean / Binary
Weight is 1 if term appears in document, otherwise 0.
2. Count / Frequency
Weight equals raw term frequency in the document.
3. TF–IDF
Use a clearly defined TF–IDF formula. Example:
1. idf(t) = log((N + 1) / (df(t) + 1)) + 1
2. w(t,d) = tf(t,d) × idf(t)
5. Similarity Measures
1. Inner Product
score(d,q) = Σ w(t,d) × w(t,q)
2. Cosine Similarity
score(d,q) = (Σ w(t,d) × w(t,q)) / (||d|| × ||q||)
6. Query Engine Requirements
• • Support keyword-based queries.
• • Return top-k ranked documents (default k = 10).
• • Display rank, file path, and similarity score.
• • Allow switching between weighting and similarity modes.
7. Bonus Features
• Phrase Queries: Return documents containing the exact phrase.
• Proximity Queries: Return documents where terms occur within k words.
8. Deliverables
3. 1. Source Code with README.
4. 2. Index files or proof of indexing 50k+ files.
5. 3. Report (3–5 pages) including experiments and comparisons.
6. 4. Demo (in-lab or recorded).
9. Grading Rubric (100 Marks)
Data Processing & Preprocessing 15
Inverted Index Construction & Persistence 20
Vector Variants Implementation 15
Similarity Measures Implementation 15
Top-k Retrieval & Interface 10
Code Quality & Documentation 5
Report & Experimental Evaluation 20
Bonus (Phrase & Proximity Queries) +20