Text Preprocessing & Indexing: Techniques, Inverted Indexes & LSI

TAKEAWAYS:

• Text preprocessing (tokenization, stemming, stopword removal) cleans raw text into queryable terms.
• Inverted indexes map terms to documents using posting lists, enabling fast retrieval.
• Latent Semantic Indexing (LSI) via SVD uncovers hidden semantic relationships between terms.
• Shingling and Rocchio’s algorithm classify documents by comparing term vectors.
• Real-world systems (eSewa’s search, Daraz’s product indexing) rely on these techniques for efficiency.
• Evaluation metrics (precision/recall) depend on how well preprocessing and indexing align terms with queries.

Core Concepts: Text Preprocessing

Text preprocessing transforms raw, unstructured text into a structured format suitable for indexing and retrieval. This step is critical because raw text contains noise (e.g., punctuation, repeated words) and inconsistencies (e.g., "running" vs. "run") that hinder accurate search.

1. Tokenization: Splitting Text into Words

Tokenization breaks text into individual terms (tokens) while ignoring punctuation and whitespace.

• Example: The sentence "The quick brown fox jumps over the lazy dog!" becomes: ["The", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"]
• Real-world tie-in: When you search for "laptop under 20000" on Daraz, the system first tokenizes your query into ["laptop", "under", "20000"] to match product listings. Without tokenization, the search would fail to split "under 20000" into meaningful terms.

2. Text Normalization: Standardizing Terms

Normalization ensures variations of the same word are treated identically. Key techniques:

• Lowercasing: Convert all text to lowercase ("The" → "the").
• Stemming: Reduce words to their root form ("running" → "run").
• Lemmatization: Convert words to their dictionary form ("better" → "good").
• Stopword Removal: Eliminate common words (e.g., "the", "is", "and") that add little meaning.

Mermaid Diagram: Text Normalization Pipeline

flowchart TD
    A["Raw Text"] --> B["Tokenization"]
    B --> C["Lowercasing"]
    C --> D["Stemming/Lemmatization"]
    D --> E["Stopword Removal"]
    E --> F["Normalized Terms"]
    F --> G["Indexing"]

Worked Example: Normalizing a Query Input: "How to fix a broken phone screen?" Steps:

1. Tokenize: ["How", "to", "fix", "a", "broken", "phone", "screen", "?"]
2. Lowercase: ["how", "to", "fix", "a", "broken", "phone", "screen"]
3. Remove stopwords: ["fix", "broken", "phone", "screen"]
4. Stemming: ["fix", "break", "phon", "screen"] (using Porter Stemmer) Output: Normalized query for indexing.

Real-world tie-in: eSewa’s search uses stemming to match "bill payment" with "pay bill" or "payment of bill". Without stemming, these queries would be treated as unrelated, reducing search accuracy.

3. Shingling: Extracting Term Sequences

Shingling creates overlapping sequences of terms (shingles) to capture local context. Used in:

• Document classification (e.g., Rocchio’s algorithm).
• Plagiarism detection (comparing shingles between documents).

Example: For the sentence "information retrieval is fun", with a shingle size of 2: Shingles = ["information retrieval", "retrieval is", "is fun"]

Mermaid Diagram: Shingling Process

Past Exam Question Tie-in: Question: "Define the role of text shingling. Apply Rocchio’s algorithm to classify the document 'process scheduling' into 'operating system' or 'Automata'." Solution:

1. Shingling: For the document "process scheduling", with shingle size = 2: Shingles = ["process scheduling"] (single shingle if size = document length).
2. Rocchio’s Algorithm:
   • Compute centroids for each class (e.g., using TF-IDF vectors for training documents).
   • Classify the new document by calculating similarity (cosine similarity) to centroids.
   • Assign to the class with the highest similarity score.

Real-world tie-in: NEPSE’s stock reports use shingling to classify news articles into categories like "dividend", "merger", or "IPO". For example, a shingle like "dividend announcement" would be flagged under the "dividend" category.

Indexing: Mapping Terms to Documents

Indexing creates a data structure that maps terms to documents for fast retrieval. The most common structure is the inverted index.

1. Inverted Index: Structure and Creation

An inverted index is a dictionary where:

• Keys = Terms (words or shingles).
• Values = Posting lists (documents containing the term + term frequency/position).

Example:

How It Works:

1. Tokenize and normalize all documents.
2. For each term, record the documents where it appears and its frequency.
3. Store the inverted index in a compressed format (e.g., using prefix trees or bitmaps).

Past Exam Question Tie-in: Question: "How is an inverted index created? Explain with an example." Solution:

1. Input Documents:
   • Doc1: "The quick brown fox jumps over the lazy dog."
   • Doc2: "A quick brown dog outpaces a fast fox."
2. Tokenization + Normalization:
   • Doc1: ["quick", "brown", "fox", "jump", "lazy", "dog"]
   • Doc2: ["quick", "brown", "dog", "fast", "fox"]
3. Inverted Index:

   Term	Posting List
   quick	Doc1 (TF=1), Doc2 (TF=1)
   brown	Doc1 (TF=1), Doc2 (TF=1)
   fox	Doc1 (TF=1), Doc2 (TF=1)
   jump	Doc1 (TF=1)
   lazy	Doc1 (TF=1)
   dog	Doc1 (TF=1), Doc2 (TF=1)
   fast	Doc2 (TF=1)

Real-world tie-in: Google’s search index is an inverted index with trillions of terms. When you search "best smartphones under 50000", Google’s inverted index instantly retrieves documents (product pages) containing those terms, ranked by relevance.

2. Posting List Compression

Posting lists can be large (e.g., "the" appears in millions of documents). Compression techniques include:

• Delta Encoding: Store differences between document IDs (e.g., Doc1, Doc3, Doc5 → store 1, +2, +2).
• Variable-Length Encoding: Use fewer bits for frequent terms.
• Bitmaps: Represent document presence/absence as bits.

Comparison Table: Compression Techniques

Real-world tie-in: WhatsApp’s message search uses compressed inverted indexes to quickly find messages containing "meeting notes" or "project deadline" in your chat history.

Advanced Indexing: Latent Semantic Indexing (LSI) and SVD

LSI improves retrieval by capturing semantic relationships between terms using Singular Value Decomposition (SVD).

1. Term-Document Matrix

Represent documents as a matrix where:

• Rows = Terms.
• Columns = Documents.
• Values = Term frequency (TF) or TF-IDF.

Example:

2. Singular Value Decomposition (SVD)

SVD decomposes the matrix into three matrices: $$\text{Term-Document}=U\Sigma V^T$$

• U: Term-concept matrix.
• Σ: Diagonal matrix of singular values (rank).
• Vᵀ: Document-concept matrix.

Steps:

1. Compute SVD on the term-document matrix.
2. Truncate to keep only the top-k singular values (dimensionality reduction).
3. Use the reduced matrices for semantic retrieval.

Mermaid Diagram: SVD Process

flowchart TD
    A["Term-Document Matrix"] --> B["Apply SVD"]
    B --> C["U (Term-Concept)"]
    B --> D["Σ (Singular Values)"]
    B --> E["Vᵀ (Document-Concept)"]
    C & D & E --> F["Reconstruct Matrix (Truncated)"]
    F --> G["Semantic Retrieval"]

Past Exam Question Tie-in: Question: "Describe the significance of LSI and SVD." Answer:

• LSI improves retrieval by identifying latent topics (e.g., "laptop" and "phone" may relate to "electronics").
• SVD mathematically uncovers these relationships by transforming the term-document matrix into a lower-dimensional space.
• Example: A query about "gadgets" might retrieve documents containing "laptop" or "phone" even if the query doesn’t explicitly include those terms.

Real-world tie-in: YouTube’s recommendation system uses LSI to understand that videos tagged "coding" and "programming" are semantically related. If you watch "Python tutorials", YouTube may recommend "Java for beginners" even if the tags don’t overlap.

## In the Real World

1. eSewa’s Search:

   • Technique: Inverted indexing + stemming.
   • How: When you search "electricity bill payment", eSewa’s system:
     • Tokenizes and stems the query to ["electric", "bill", "pay"].
     • Matches these terms against its inverted index of service listings.
     • Ranks results by relevance (e.g., documents with high TF-IDF for "bill payment").

2. Daraz’s Product Indexing:

   • Technique: Shingling + LSI.
   • How: Daraz uses shingles to group similar products (e.g., "laptop under 50000" and "gaming laptop sale" may share shingles like "laptop" and "under").
   • LSI helps recommend related products (e.g., if you view "smartphones", Daraz may suggest "accessories" based on semantic links).

3. Ncell’s Customer Support Chatbot:

   • Technique: Text preprocessing + inverted index.
   • How: When you type "my data balance", the chatbot:
     • Normalizes the query to ["data", "balance"].
     • Searches an inverted index of FAQs to find matches like "check data balance" or "top-up data".
     • Retrieves the most relevant response instantly.

## Exam Tip

1. For definitions:

   • Inverted index: Always explain it as a term → documents mapping with posting lists.
   • LSI/SVD: Emphasize that SVD reduces dimensionality to find latent topics (semantic relationships).
   • Shingling: Highlight its use in document classification (e.g., Rocchio’s algorithm).

2. For worked examples:

   • Inverted index: Show a small table with 2–3 documents and terms. Label columns clearly.
   • Rocchio’s algorithm: Always include:
     • Shingling step (if applicable).
     • Centroid calculation for classes.
     • Similarity score (cosine similarity) for classification.
   • SVD: Draw the matrix decomposition visually (even if simplified).

3. Common pitfalls:

   • Forgetting to normalize text (lowercase, stemming) before indexing.
   • Ignoring stopword removal in examples (examiners check for this).
   • Confusing stemming (rule-based) with lemmatization (dictionary-based).
   • In LSI, don’t skip the truncation of singular values—it’s key to dimensionality reduction.

4. Diagrams that score marks:

   • Draw a text preprocessing pipeline (tokenization → normalization → indexing).
   • For inverted indexes, always show a table with terms and posting lists.
   • For LSI, sketch the SVD decomposition (even a 3x3 → 2x2 example).

Final Note: This unit is 50% of your marks in past exams. Focus on:

• Hands-on examples (e.g., building an inverted index for 3 documents).
• Real-world ties (eSewa, Daraz, YouTube—examiners love these).
• Mathematical steps (SVD, Rocchio’s similarity formula).