Information Retrieval

Search Engine Indexing From Raw Text to Normalized Terms

Published: 2026-09-14

Level: undergraduate

Audience: Undergraduate students studying Information Retrieval

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Term-document incidence matrix and Boolean evaluation — covered in Lecture 2 (The Term-Document Incidence Matrix and Boolean Evaluation)
Inverted index with dictionary, postings and frequencies — covered in Lecture 2 (The Inverted Index: From Words to Documents)
Merge algorithm and smallest-set-first query ordering — covered in Lecture 2 (The Merge Algorithm: Answering AND With One Forward Pass)
Indexing pipeline with stemming and lemmatization — covered in Lecture 1 (From Raw Document to Ranked Output)

This lecture traces the full path from raw text to a searchable index. It starts with the term-document incidence matrix and the inverted index, shows how Boolean queries are ordered for speed, defines precision and recall for judging results, and then works through the text pipeline itself: what counts as a document, how tokens become types and terms, why tokenization needs language rules, and how stop words, normalization, case handling, stemming and lemmatization shape the final vocabulary.

3.1 Term-Document Incidence Matrix and Inverted Index

Why start with a giant table of zeros and ones when we could just scan documents? Because scanning a million documents for every query is far too slow. The question that opens this section is simple: how do we record once, in advance, which term appears where, so that every later AND, OR and NOT query becomes a fast set operation?

A term-document incidence matrix (a table that records which terms appear in which documents, written $M$ ) sits at the start of Boolean retrieval. We build it so that a later step can answer AND, OR and NOT queries by set operations on rows. A term (a normalized index unit ready for the dictionary, for example approach or drug) is the row label. A document (the basic retrieval unit, labelled here as $D_{1}$ , $D_{2}$ , $D_{3}$ and $D_{4}$ , where each $D_{i}$ is one document identifier and $i$ ranges over document numbers 1 to 4) is the column label.

Think of the matrix as a library attendance sheet. Each row is one student name, each column is one day, and a tick means present. The funnel analogy used in class fits the next step: the full sheet is wide and mostly empty, and the inverted index is the narrow funnel neck that keeps only the ticks. Where the analogy breaks: students choose to attend, while terms occur because of what the author wrote, so the pattern of ticks is fixed by the collection, not by choice.

Rows will be the terms and columns will be the document identifiers, with rows in ascending order so we do not miss any terms. Ascending alphabetical order matters because it stops us from skipping a term by accident when the vocabulary grows to hundreds of thousands of entries. Each cell holds $1$ when the row term occurs in the column document and $0$ when it does not, where $1$ means present and $0$ means absent.

That matrix is sparse and humongous in any real collection. Most cells are $0$ because any single document uses only a tiny slice of the full vocabulary. A collection with $M = 500000$ distinct terms and $N = 1000000$ documents has $500$ billion cells, yet each document of about $1000$ words contributes at most $1000$ ones. Storing all those zeros wastes space and slows down merging. That is why we move to an inverted index (a flipped structure that maps each term to the list of documents where it appears, written $P (t)$ for term $t$ ). The idea is that we map terms to documents to remove the zeros, because the matrix is very sparse and very large. In symbols, for each term $t$ , we store a sorted postings list $P (t) = [d_{1}, d_{2}, \dots, d_{k}]$ , where each $d_{j}$ is a document identifier that contains $t$ and the list is kept in increasing order. Sorted order is an optimization we must remember: it lets later merges walk two lists with two pointers in linear time.

3.1.1 Mathematical Formulation

An incidence entry (one cell of the matrix, written $M_{t, d}$ ) records presence or absence. Let $t$ range over terms and $d$ range over documents. Then:

$M_{t, d} = 1 if term t occurs in document d, else M_{t, d} = 0$

Here $t$ is a term string such as approach, $d$ is a document identifier such as $D_{3}$ , $1$ means present and $0$ means absent. Each row of $M$ is the characteristic vector of one term across documents. Each column of $M$ is the set of terms in one document.

The inverted form drops the zeros and keeps only positions of ones, sorted for merging:

$P (t) = [d ∣ M_{t, d} = 1] in increasing order$

Here $P (t)$ is the postings list for $t$ , each $d$ is a document identifier with $M_{t, d} = 1$ , and increasing order means $d_{1} < d_{2} < \dots < d_{k}$ . The dictionary stores each $t$ plus its document frequency $∣ P (t) ∣$ , where $∣ P (t) ∣$ is the number of identifiers in the list. That count is later reused to order query processing from the rarest term upward.

In plain words: read one row of the matrix from left to right, write down only the column numbers where you see a $1$ , and keep them sorted. That short list replaces the whole long row. Nothing about which documents contain the term is lost. Only the zeros are gone.

3.1.2 Worked Examples

Worked example 1 — approach as a single-document inverted list. Setup: four documents $D_{1}$ to $D_{4}$ . Given: approach occurs only in document three. Matrix row across $D_{1}$ to $D_{4}$ :

$M_{approach} = [0, 0, 1, 0]$

Step 1: scan the four cells and note the positions of ones. Only column 3 holds $1$ . Step 2: drop the three zeros. Step 3: keep the survivor sorted. Result:

$P (approach) = [3]$

where $3$ means $D_{3}$ . Sense-check: a singleton list with one entry matches a term seen in exactly one document.

Worked example 2 — breakthrough as a second singleton. Setup: same four documents. Given: breakthrough occurs in only one document. Matrix row again has a single $1$ and three $0$ values, for instance $[0, 1, 0, 0]$ if the hit is in $D_{2}$ . Inverted entry is a single-element list with that one document identifier, for instance $P (breakthrough) = [2]$ . The point is that singletons are common in real text and the inverted form stores each with almost no cost, while the matrix would spend four cells on each.

Worked example 3 — drug seen in two documents with a sorted postings list. Setup: same four documents. Given: drug is seen in document one and document two. Matrix row:

$M_{drug} = [1, 1, 0, 0]$

Step 1: positions of ones are columns 1 and 2. Step 2: drop the two zeros. Step 3: confirm increasing order $1 < 2$ . Result:

$P (drug) = [1, 2]$

where $1$ means $D_{1}$ and $2$ means $D_{2}$ . Sense-check: list length $∣ P (drug) ∣ = 2$ matches the count of ones in the row. Sorted order was flagged as an optimization we must remember, because ordered lists make intersection and union merges fast with a two-pointer walk.

Picture the matrix as a grid with terms down the left and $D_{1}$ to $D_{4}$ across the top. Most squares are empty. The inverted index keeps one horizontal strip per term and writes only the shaded column numbers in order. The takeaway in one sentence: the same information, minus the empty squares, plus an order that makes merging fast.

Scope: The incidence matrix records presence or absence only. It does not record how many times a term occurs in a document, where it occurs, or how important it is. Assumption: Terms are already normalized index units and documents already have stable identifiers. If tokenization or normalization changes later, the rows change and the matrix must be rebuilt.

Common traps: flipping rows and columns, so documents become rows and terms become columns; forgetting ascending order and then missing a term during hand checking; writing postings in document encounter order instead of sorted order, which breaks the linear merge; and storing the full row including zeros in the inverted form, which defeats the whole saving.

3.1.3 Student Questions and Answers

Q: What should be the rows and columns of the incidence matrix?

A: Columns are document identifiers $D_{1}$ to $D_{4}$ and rows are terms in ascending alphabetical order, starting with a word such as approach. Ascending order keeps the vocabulary complete and stops us from missing a term. Incidence rows and columns in ascending order are the exam-safe layout: terms down, documents across, ones and zeros inside.

The next doubt follows at once: if the matrix already answers queries, why build anything else.

Q: Why do we move from a term-document matrix to an inverted index?

A: The matrix is very sparse and grows very large, so storing zeros wastes space. With half a trillion cells mostly zero, memory cannot hold it. The inverted index removes the zeros by mapping each term directly to its documents, and it keeps each postings list sorted so later merges stay fast. In short: inverted and sparse with zeros removed and sorted lists is what makes large collections searchable.

Exam note: Work this kind of tiny matrix and inverted list by hand with pen and paper. Draw rows as terms in ascending order, columns as $D_{1}$ to $D_{4}$ , cells as $1$ or $0$ , and postings lists sorted. That practice makes exam problems on incidence matrices and inverted lists much safer and helps secure full marks on that question.

That habit closes this concept. The matrix tells us what to store, the sorted inverted lists tell us how to store it, and the next section uses those sorted lists to order Boolean operations from the cheapest first.

One-line recap: a sparse incidence matrix with terms as ascending rows and documents as columns becomes a set of sorted postings lists with zeros removed. Handoff: with $P (t)$ and $∣ P (t) ∣$ defined, we can now judge which union or intersection to run first when a query brings several lists together.

3.2 Query Processing Order and Postings Size

A query with three bracketed OR pairs can be answered in any order and still give the same documents. So why does order matter at all? Because one order may compare hundreds of thousands of identifiers while another compares only a few thousand first. How do we pick the cheapest order without changing what the query asks?

Boolean queries combine postings lists with AND as intersection and OR as union. An intersection (the set of documents present in both lists, written $A \cap B$ ) implements AND. A union (the set of documents present in either list, written $A \cup B$ ) implements OR. A postings size (the number of document identifiers stored for a term, written $∣ P (t) ∣$ and often close to its collection frequency) tells us how expensive that list is to process. The core efficiency idea is to start with the smallest set. For OR we still must respect the query brackets, but we choose the cheapest union order inside them. For AND we intersect with the smallest list first so intermediate results stay small.

Think of it like pouring water through funnels. A narrow funnel first limits how much flows onward. Starting with a rare term narrows the candidate set early. Starting with a frequent term floods the merge with identifiers that later steps must discard. Where the picture breaks: water volume only shrinks, while a union can grow the set, so smallest-first for OR means smallest combined pair first, not smallest single term first.

3.2.1 Mathematical Formulation

A query processing order (the sequence in which postings lists and intermediate sets are merged) is chosen by size. Let $∣ P (t) ∣$ be the length of the postings list for term $t$ . Then the working rule is:

$process lists in order of increasing ∣ P (t) ∣$

Here $∣ P (t) ∣$ is also called postings size or document frequency. For an OR of two terms $a$ and $b$ , the two-pointer merge touches on the order of $∣ P (a) ∣ + ∣ P (b) ∣$ identifiers:

$cost (P (a) \cup P (b)) = O (∣ P (a) ∣ + ∣ P (b) ∣)$

For an AND chain over terms $t_{1}, \dots, t_{n}$ , sort so that $∣ P (t_{1}) ∣ \leq ∣ P (t_{2}) ∣ \leq \dots \leq ∣ P (t_{n}) ∣$ , load $P (t_{1})$ first, and intersect step by step. The same rule was restated as we always intersect with the smallest inverted index set first, because every intermediate result is then no larger than the smallest list seen so far. For OR-heavy queries such as $(madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)$ , estimate each bracketed OR by the sum of its parts and run the smallest estimated set first. The cost idea from class was take the sum of the two postings sizes and pick whichever gives the smallest, because OR is all about taking union and AND is all about intersection.

In plain words: look up the size of each list from the dictionary, add the two sizes inside each bracketed OR, do the smallest union first, then feed the resulting sets into the AND chain starting from the smallest.

3.2.2 Worked Examples

Worked example 1 — ordering unions with three candidate pairs, kaleidoscope eyes smallest union first. Setup: the query is $(tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)$ . Given sizes from the dictionary: $∣ P (eyes) ∣ = 213312$ , $∣ P (kaleidoscope) ∣ = 87009$ , $∣ P (marmalade) ∣ = 107913$ , $∣ P (skies) ∣ = 271658$ , $∣ P (tangerine) ∣ = 46653$ , $∣ P (trees) ∣ = 316812$ . These include the large frequency where eyes was seen about 213000 times in the collection and the small competing values such as 46, 6, 5 and 3 discussed for tiny sets in class.

Method: estimate each bracketed OR by its sum.

$S_{1} = ∣ P (tangerine) ∣ + ∣ P (trees) ∣ = 46653 + 316812 = 363465$

$S_{2} = ∣ P (marmalade) ∣ + ∣ P (skies) ∣ = 107913 + 271658 = 379571$

$S_{3} = ∣ P (kaleidoscope) ∣ + ∣ P (eyes) ∣ = 87009 + 213312 = 300321$

Result: $S_{3} < S_{1} < S_{2}$ , so kaleidoscope OR eyes is the first operation, then the tangerine pair as the second, and the marmalade pair after that. This is the most optimal way to perform the operation for the given query, with union cost driving the choice. Sense-check: the pair with the smallest sum runs first even though eyes alone is very frequent, because the sum is what matters, not one side alone.

Worked example 2 — respecting query brackets with fixed sets. Setup: the query asks for a specific bracketed OR, for instance kaleidoscope OR eyes inside brackets, to be combined with other sets by AND. Call the three bracketed results set one, set two and set three. A natural doubt is whether we could drop one side or pair kaleidoscope with tangerine because that sum looks smaller.

Answer: no. The OR inside the brackets is fixed by what the query asks. We cannot discard the bracketed partner and we cannot re-pair across brackets. Optimization chooses which pre-defined set, set one, set two or set three, goes first in the intersection order, but it does not rewrite the query logic. Sense-check: changing partners would answer a different question, so the saving would be fake.

Worked example 3 — AND as intersection from the smallest intermediate set. Setup: after the unions are done we hold three intermediate sets. Method: sort those three sets by size and intersect the smallest two first, then intersect the result with the largest. Result: the running candidate set stays small through each step. The repeated refrain holds: if it is an OR operation it is all about union, and if it is an AND operation it is all about intersection. Sense-check: the final document set is the same whatever the order, but the number of comparisons is lowest when small sets lead.

Picture a bar chart with one bar per term, height equal to postings size. Eyes towers high near 213312, trees higher still near 316812, while tangerine sits low near 46653. Bracketed pairs become stacked bars. The shortest stack runs first. The one-sentence takeaway: height predicts work, so short stacks lead.

Scope: Size-ordering assumes postings are sorted and dictionary frequencies are fresh. Assumption: Union cost grows with the sum of sizes and intersection cost shrinks when the running set is small. If lists carry positions or weights, or if NOT appears, the simple sum estimate needs extra care and the NOT side is handled last.

Common traps: re-pairing terms across brackets because the cross sum looks smaller; judging an OR pair by one side only, for instance calling kaleidoscope OR eyes cheap just because kaleidoscope is rare while eyes is huge; forgetting that AND wants the smallest intermediate first, not the original smallest single term; and treating postings size as exact union size when overlap can make the true union smaller than the sum.

3.2.3 Student Questions and Answers

Q: What is postings size and how was the eyes frequency obtained?

A: Postings size is the frequency-linked length of a term postings list, stored as document frequency in the dictionary. The eyes example meant that eyes had been seen in the collection about 213000 times (213312 in the table), so its list is very long and therefore expensive to process early. Small values such as 46, 6, 5 and 3 in the discussion belong to tiny competing sets used to show how sums are compared.

Q: Which union should we take first among tangerine, trees, marmalade, skies, kaleidoscope and eyes?

A: Compute each bracketed union size and take the smallest first. For the discussed query that meant kaleidoscope OR eyes first, then the tangerine pair, then the third pair, because that order gives the lowest comparison cost. Union smallest first and intersection smallest first is the full rule in one line.

The last doubt is the most instructive because it tests whether optimization may rewrite logic.

Q: Is kaleidoscope AND tangerine not smaller than kaleidoscope OR eyes? Why not pair those?

A: The OR pairs are fixed by the query brackets. The query asks for union between those two partners only, so we cannot discard one side or re-pair across brackets even if kaleidoscope AND tangerine looks smaller. We optimize the order of the pre-defined sets, called set one, set two and set three, when we intersect them. Bracketed OR fixed and cannot discard or re-pair is the point to carry into the exam.

Exam note: Expect to compare union sizes and pick the smallest first. Show the size sums for each candidate pair and name the first operation, for instance kaleidoscope OR eyes. Respect query brackets and label set one, set two and set three. That ordered working earns marks even if later arithmetic slips.

The order is now set, the logic untouched. Small unions first, then small intersections, same answer with less work.

One-line recap: estimate each bracketed OR by summed postings sizes, run the smallest union first, then intersect intermediate sets from the smallest. Handoff: with fast Boolean merging in hand, the next question is whether the returned set is any good, which needs precision and recall.

3.3 Precision, Recall and Retrieval Quality

A system returns ten documents and seven look right. Is that good? It depends on two hidden numbers: how many good documents exist in total, and how many of the ten are truly good. Without both, a single score can mislead badly.

An information retrieval process (a method that returns documents for a query, for example a Boolean search or a ranked search) can be judged only by comparing what we want with what the system gives. Relevant documents (the documents we actually want for the query, judged against the information need) are ground truth. Retrieved documents (the documents the system returns for the query) are system output. From those two sets we define three counts. Let $a$ be the total number of relevant documents in the collection, where $a$ counts ground truth. Let $c$ be the total number of retrieved documents returned for the query, where $c$ counts system output. Let $b$ be the number of relevant documents that were retrieved, where $b$ counts the overlap. The verbal description was $a$ is total relevant, $c$ is total retrieved, and $b$ is relevant retrieved.

Precision (how accurate the returned set is, written $P$ ) looks through the lens of prediction. It asks, of what the system returned, how much was actually wanted. Recall (did we find everything important, written $R$ ) looks through the lens of actual values. It asks, of what was wanted, how much did the system find. Picture a fishing net: precision asks how many fish in the net are keepers, recall asks how many keepers in the lake ended up in the net. Where the picture breaks: fish stay put while relevance depends on a human need, so the lake total $a$ needs a judgment, not just a count.

A system that returns only relevant documents is the best case. A system that returns irrelevant documents is the bad case we want to detect. Real use lives by these two numbers. A shop search for car service station that returns automobile repair shops when synonyms are handled can lift recall without flooding results with unrelated pages.

3.3.1 Mathematical Formulation

Precision (fraction of returned documents that are relevant) is relevant retrieved divided by total retrieved, because precision is seen from the model point of view:

$Precision = \frac{b}{c}$

where $b$ is relevant retrieved and $c$ is total retrieved. Recall (fraction of relevant documents that were found) is relevant retrieved divided by total relevant, because recall is seen from the data point of view:

$Recall = \frac{b}{a}$

where $b$ is relevant retrieved and $a$ is total relevant. The class explicitly corrected an early mix-up and settled on precision as $b$ divided by $c$ and recall as $b$ divided by $a$ .

In true positive language, with true positives as relevant retrieved, false positives as retrieved but not relevant, and false negatives as relevant but missed, the same ideas become:

$Precision = \frac{true positives}{true positives + false positives}$

$Recall = \frac{true positives}{true positives + false negatives}$

where true positives plus false positives equals $c$ and true positives plus false negatives equals $a$ . So $b = true positives$ , $c - b = false positives$ , and $a - b = false negatives$ .

There is a tradeoff between precision and recall. Pushing hard for precision alone can give an overfitted model that returns very little and misses much. The working advice was we cannot chase precision so hard that recall suffers badly, because that path leads to an overfitted model. Retrieving everything gives recall $1$ but poor precision. Retrieving one sure hit gives precision $1$ but poor recall.

3.3.2 Worked Examples

Worked example 1 — precision with seven out of ten returned documents. Setup: query is information retrieval. System returns $c = 10$ documents. Ground truth check shows $b = 7$ of those ten are about information retrieval, while three are only about information or only about retrieval. Those three extras were described as falsely marked as positive. Substitution:

$Precision = \frac{7}{10} = 0.7$

where $7$ is relevant retrieved and $10$ is total retrieved. Precision is 0.7, or 70 percent. Sense-check: most of what came back is good, so precision near three quarters feels right.

Worked example 2 — recall with seven out of twenty relevant documents. Setup: collection holds $a = 20$ relevant documents. System retrieved only $b = 7$ of them. Substitution:

$Recall = \frac{7}{20} = 0.35$

where $7$ is relevant retrieved and $20$ is total relevant. Recall is 0.35, or 35 percent. Sense-check: finding about one third of the good material matches the low recall number.

Worked example 3 — larger numbers separating the two lenses. Setup: collection holds 50 relevant documents, so $a = 50$ . System retrieved 20 documents, so $c = 20$ . If all 20 retrieved are relevant, then $b = 20$ . Then:

$Precision = \frac{20}{20} = 1.0$

$Recall = \frac{20}{50} = 0.4$

where the numerators and denominators follow the same $a$ , $b$ , $c$ meanings. Precision from the prediction lens is perfect, recall from the actual lens is 0.4. The example was used to separate the lens of prediction from the lens of actual values: perfect accuracy on what came back can still leave most good documents unfound.

Picture a two-circle Venn diagram. The left circle holds the $a$ relevant documents, the right circle holds the $c$ retrieved documents, and the overlap holds the $b$ shared ones. Precision is the overlap share of the right circle. Recall is the overlap share of the left circle. The one-sentence takeaway: same overlap, different denominator, different question.

Scope: Precision and recall judge sets, not ranks. Assumption: Relevance is binary and ground truth $a$ is known or judged on a fixed test set. If relevance is graded or the collection grows without fresh judgments, $a$ is uncertain and the numbers need rank-aware extensions.

Common traps: swapping denominators so precision divides by $a$ and recall by $c$ ; reading $c$ as relevant count instead of returned count; calling a system good from precision alone while recall is very low; and letting the system define its own truth instead of checking against ground truth.

3.3.3 Student Questions and Answers

Q: In my numbers, ten refers to $c$ , right? And for precision should the denominator be total retrieved or total relevant?

A: Ten is $c$ , total retrieved, because the system returned ten documents. Precision uses total retrieved, so it is $b$ divided by $c$ , here $7/10$ . Recall uses total relevant, so it is $b$ divided by $a$ , here $7/20$ . The early board writing mixed these denominators and was then corrected to $b$ divided by $c$ for precision and $b$ divided by $a$ for recall. Precision denominator corrected to total retrieved is the fix to remember.

Q: When we run a query and get $c$ documents back, do we then compare which of them are relevant to get $b$ ?

A: Yes. The query returns $c$ documents. We then check ground truth to find $b$ , how many of those $c$ are relevant. Precision looks from the prediction side at what the model returned, while recall looks from the actual side at what was wanted. The model only predicts, it does not state ground truth by itself.

Q: Is the true positive and false positive view the same as $a$ , $b$ , $c$ ?

A: Yes. True positives are $b$ . False positives are retrieved but not relevant, so true positives plus false positives equals $c$ . Missed relevant documents were falsely seen as negatives, so true positives plus false negatives equals $a$ . That is why precision is true positives divided by all predicted positives and recall is true positives divided by all actual positives.

Exam note: Write all assumptions with $a$ , $b$ and $c$ defined before substituting numbers. Define $a$ as total relevant, $c$ as total retrieved and $b$ as relevant retrieved. Then write precision as $b / c$ from the prediction lens and recall as $b / a$ from the actual lens. Practice $7/10$ for precision and $7/20$ for recall until the denominator choice is automatic. Write true positives, false positives and false negatives alongside $a$ , $b$ and $c$ so graders can follow even if a later division slips.

Two lenses, one overlap. Keep denominators straight and the rest follows.

One-line recap: precision $b / c$ judges the returned set, recall $b / a$ judges coverage of the wanted set, and chasing one without the other risks an overfitted model. Handoff: knowing how to score output, we now ask how raw text becomes indexable input, starting with the pipeline and the document unit.

3.4 Indexing Pipeline and What Counts as a Document

Search feels instant, but behind it messy files must become tidy lists. What are the few steps that turn a pile of pages, mails and posts into structured postings a merge algorithm can use?

A document (the basic unit of retrieval, for example one mail, one chapter, or one post) is where all indexing starts. There is no retrieval without something to retrieve. The pipeline turns messy unstructured text into structured data that a search engine can store and merge. Unstructured here means text without neat fields, while structured means dictionary terms plus postings lists with identifiers. The four major steps named in class are collect the documents to be indexed, tokenize the text, do linguistic preprocessing of the tokens, and index the documents in which each term occurs. In short, collect, then tokenize, then normalize linguistically, then build term to postings mappings. The point of the chain is transforming messy unstructured data to structured data through these steps.

A token (a raw surface piece straight from the splitter, for example Friends with a capital F) at this stage is still unnormalized. Later steps turn tokens into terms. The order can loop a little in practice, but tokenization comes first because later decisions need token boundaries. To spot stop words we must first know the candidate tokens. To find a base form we must first know the term candidate. That is why the pipeline lists tokenization before normalization even though real code may revisit steps.

3.4.1 Procedural Steps

Purpose: turn varied source text into one uniform index that supports fast Boolean and ranked search. Inputs: raw files in many formats and languages, plus choices for document unit, tokenizer, stop list and normalizer. Outputs: a dictionary of terms with document frequencies and postings lists keyed by document identifier.

The procedure runs as a numbered sequence with a reason for each step. Step 1: collect the documents to be indexed, because coverage starts with the source set. Gather web pages, PDFs, mails and posts, decode bytes to characters, and fix the document unit. Step 2: tokenize the text, because we need units to work on. Cut the character stream into tokens and throw away pure punctuation. Step 3: do linguistic preprocessing such as lowercasing, stop word handling, stemming or lemmatization, because surface variants must be reconciled. Map Friends to friend and Romans to roman so one idea has one entry. Step 4: index the documents in which each term occurs, because retrieval needs term to postings maps. Sort term and identifier pairs, group by term, and split into dictionary plus postings. Each step feeds the next, and the whole chain changes unstructured text into structured postings.

A tiny trace makes it stick. Input document: Friends, Romans, countrymen. After tokenizing: [Friends, Romans, countrymen]. After preprocessing: [friend, roman, countryman]. After indexing: friend points to this document, roman points to this document, countryman points to this document. One line, three stages, same idea carried forward.

3.4.2 Document Sources and Granularity

Documents arrive from many sources. The class named web pages, PDF files, single emails, email threads, emails with attachments, short posts such as tweets, book chapters, paragraphs, professional posts such as LinkedIn posts, and markup sources such as LaTeX, HTML and XML. Any file counts when we can pull text from it. An mbox mail folder may hold many mails, one mail plus a zip attachment may become several documents, and several HTML slides may join into one document. Language also varies, so a document can be in any language, not only English.

Granularity matters. A large book with ten chapters can be treated as one document or as ten chapter documents. A query about Chinese toys needs toy chapters, not cuisine chapters or travel-spot chapters from the same book. If the whole book is one unit, a cuisine-heavy book may still match a toys query through a small section, which hurts precision and buries the useful passage. If each chapter is a unit, the match is tighter and the user jumps straight to the right passage, but a query whose evidence spreads across chapters may miss, which hurts recall. The right unit depends on the application and on what users expect to get back. Document granularity for the Chinese toys case is the textbook example of this tradeoff.

Picture two bars for one book. As one whole document the book is a single tall bar that matches too easily. As ten chapter bars the toys chapter stands out while cuisine and travel chapters stay flat. The one-sentence takeaway: smaller units raise precision, larger units protect recall, and the deployer must pick with users in mind.

Scope: The four-step order is a guide, not a strict one-pass rule. Assumption: A suitable document unit and encoding have been fixed before tokenizing. If files mix languages or units mid-stream, per-paragraph language detection and multi-level indexing are needed.

Common traps: treating each file as one document without thinking, so a whole book or a whole mail folder becomes one giant unit; skipping character decoding so bytes from PDFs or zip files never become text; and judging stop status before tokens exist, which is impossible because both stop checks and base-form rules need the token first.

3.4.3 Preprocessing Order

After tokenization we bring text to lowercase, remove selected stop words, and reduce words toward friend, roman and continuous style base forms discussed in class, where friend, roman and continuous stand for the final normalized tokens in that example. The class noted this order can be described in more than one way. Some teams call the first split tokenization and then normalize. Others interleave lowercasing and stop handling. The stable point is that finding token boundaries comes before judging stop status or base forms, because both judgments need the token first.

In cost terms the pipeline is linear in collection size plus a sort of term and identifier pairs. It runs once at build time so queries stay fast. When crawling never stops, rebuilt segments merge in the background and postings use structures that allow cheap inserts.

One-line recap: collect sources, fix the document unit with granularity in mind, tokenize first, then normalize, then sort and group into structured postings. Handoff: with units fixed, the next step is to count precisely what those units hold, which needs tokens, types and terms kept strictly apart.

3.5 Tokens, Types and Terms

Five words on the page, but how many entries should the index hold? Count wrong and the dictionary either stores junk or drops meaning. What three-way split keeps the count honest?

A token (every occurrence of a word in running text, for example the second to in a sentence) counts repeats separately. A type (each unique word shape, for example to counted once no matter how often it appears) counts repeats once. A term (a normalized type ready for the index, for example sleep after lowercasing and stop handling) counts only after normalization such as lowercasing, stop word removal and base-form reduction. The rule set in class was token is about occurrences, type is about unique words, and term is about normalized types for the index. Newer books and speakers sometimes use token and term interchangeably in casual talk. In this course we fix the usage to term for normalized index units to avoid confusion.

Picture a fruit stall. Each apple on display is a token occurrence. Each distinct variety, say Fuji versus Gala, is a type. The cleaned label that goes into the stock book, say apple with size and grade folded together, is the term. Where the picture breaks: apples stay distinct while words have case, plurals and stop status, so two identical-looking tokens may still map to one term or to none.

An occurrence (each slot in the text, numbered 1, 2, 3 from the left) means each position. A unique word (each distinct shape after grouping identical slots) means each spelling group. A normalized word (the dictionary-ready form after stop handling and base-form steps) means the final index entry. That three-way split is what lets us reduce redundancy before indexing.

3.5.1 Worked Examples With Counts

Worked example 1 — sleep, perchance and rest with tokens, types and terms counts. Setup: start with the sentence to sleep, perchance to sleep. Number the slots: to(1) sleep(2) perchance(3) to(4) sleep(5). Raw count gives five tokens, because each occurrence counts, including the two copies of to and the two copies of sleep.

Grouping identical shapes was first reported as four types, because one repeated shape was removed, and then three terms, because to is a stop word and is removed for the index. A question then pointed out that sleep is also repeated, so both to and sleep repeat. That would leave only three distinct shapes, namely to, sleep and perchance, not four. The response accepted the catch and repaired the sentence to to sleep, perchance to rest and also to perchance to dream. Take the repaired five-token form to sleep perchance to rest: slots to(1) sleep(2) perchance(3) to(4) rest(5). Tokens are five. Types are four, namely to, sleep, perchance, rest. Terms are three, because to drops as a stop word and the rest stay. The repair shows how a dummy example must be consistent: tokens count slots, types drop duplicates, terms also drop stop words. Sleep repeated catch repaired to perchance rest dream is the correction to remember.

Worked example 2 — she was young the way an actual young person is younger. Setup: eleven running words. Count them as She(1) was(2) young(3) the(4) way(5) an(6) actual(7) young(8) person(9) is(10) younger(11). Tokens are eleven. Types are nine, because young repeats and grouping removes the extra copies, with younger kept apart until base-form folding. The class reported young as repeated three times in the running discussion and settled on nine types. Terms are five, because stop words and inflections are normalized away. The surviving content words discussed were young, way, actual, person and a fifth survivor from the stop filtering, with younger folding toward young. The exact fifth survivor was debated in class between she and neighboring function words, which shows why a fixed stop list and a fixed base-form rule must be stated before counts can be final. Sense-check for both sentences: tokens >= types >= terms always holds, with equality only when nothing repeats and nothing stops out.

Picture a three-column table. Column one lists numbered slots. Column two crosses out duplicate spellings. Column three crosses out stop words and folds younger into young. The one-sentence takeaway: each column can only shrink the count, never grow it.

Scope: Counts depend on stated rules. Assumption: The tokenizer, the stop list and the base-form rule are fixed before counting. Change any of them and the same sentence gives different types or terms without any error in arithmetic.

Common traps: dropping stop words when counting types, but types vanish only by duplicate removal, not by stop removal; counting younger and young as one type before folding, but they are distinct shapes until normalization; and quoting term counts without naming the stop list, which makes five terms uncheckable.

Exam note: Practice both sentences by hand. List tokens with numbers, cross out duplicates for types, then cross out stop words and fold inflections for terms. Showing that table-like working makes grading easy. Rehearse to sleep, perchance to rest with five tokens, four types and three terms, and the young sentence with eleven tokens, nine types and five terms.

3.5.2 Student Questions and Answers

Q: If sleep also repeats, should types not be three rather than four? And which words vanish for types?

A: Yes, that catch is correct for the original wording to sleep, perchance to sleep. Both to and sleep repeat, leaving to, sleep and perchance, so three types, not four. Types vanish only by duplicate removal, not by stop removal. The fix is to change the sentence to to sleep, perchance to rest or to perchance to dream, which then has five tokens, four types and three terms.

Q: In the young sentence with eleven tokens and nine types, what are the five terms and is there any rule for which words we drop?

A: Tokens count all eleven slots. Types drop duplicate shapes to nine. Terms keep only normalized content words, about five survivors such as young, way, actual and person plus one more function-word decision, with younger folding toward young. The rule is token is occurrences, type is unique words, and term is normalized words after stop handling and base-form reduction. Only words that keep sentence meaning for matching stay as terms.

Q: Any rule for term selection beyond dropping unimportant words?

A: A term is a normalized word that keeps matching meaning intact. If dropping a word breaks matching for the intended queries, keep it or down-weight it instead of deleting it. That is why term counts depend on the stated stop list and base-form rules. Token occurrences and types unique is the counting base, normalization is the judgment on top.

Slots, shapes, then stock-book labels. Keep the three levels apart and every later count stays checkable.

One-line recap: tokens count slots, types count distinct shapes, terms count normalized survivors. Handoff: counting is easy once boundaries are fixed, but finding those boundaries is the hard part, because tokenization is not just splitting text.

3.6 Tokenization Is Not Simple Splitting

If tokenization were just cutting on spaces, every search engine would agree. Yet one engine returns the city and another returns church parts for the same query. What hidden choices make the same characters succeed or fail?

Tokenization (cutting running text into indexable units, for example deciding whether San Francisco is one token or two) looks like splitting on spaces but actually needs language decisions. Those decisions change search accuracy directly. A splitter that only cuts on whitespace will both over-split units that must stay together and under-split units that must be separated. The class summary was tokenization is not just splitting text, it involves linguistic decisions, and these decisions directly affect search accuracy.

Think of the machine as a diligent helper with no common sense about spelling variation. A person reads full text with or without a hyphen as the same idea and moves on. A machine treats full, full-text and fulltext as different strings unless told how to normalize them. We must tell it. The class image was a machine poor thing that cannot understand hyphen use the way a human can. Where the image breaks: the helper never tires and never guesses, so once we give a clear rule it applies the rule to billions of words without drift.

3.6.1 Apostrophes, Hyphens and Accents

Cooper possessives and plurals show the apostrophe problem. Consider the string Coopers in the sentence about Cooper concordance of Wordsworth published in 1911. Candidate terms include Cooper with an apostrophe and s for possession, Cooper without apostrophe and without s for the base name, and Coopers as a plural. All three can be right in different contexts. Possession as in Cooper property needs the possessive reading. One topper named Cooper needs the singular base. Many accounts across banks with Coopers needs the plural reading. Only surrounding context tells which reading holds. Cutting blindly loses that signal. The same care applies to forms such as O Neil with an apostrophe and boys with a contraction-like ending, where the normalized word for each surface form is not known without language-specific rules.

Hyphenation and compound words show the same tension. Full-text can appear with a hyphen, without a hyphen with a space, or joined without a space. All three occur in real writing. A reader maps them to one idea without effort. A system without a rule does not. The co-education family behaves the same way. Writers produce co-education with a hyphen, co space education with a space, and co without space education joined. All three mean boys and girls studying together in one classroom, with no other meaning in that context. Without context and an explicit rule, the system will not give the same preference to all three for a query about co-education schools. A practical fix used by some Boolean systems is to expand a hyphenated query into all three forms joined by OR, so over-eager also searches over eager and over eager as a phrase.

Accents and diacritics add a third wrinkle. French items such as ne with a mark on the letter, plus les and un and similar function words, carry marks that English keyboards often drop. Should the index fold everything to unaccented English and treat English as the universal language. The class answer was no, that is not accurate and not right. Folding must respect the collection language and the user population, not assume all searchers use English. Spanish pena versus peña shows the risk: one accent changes sorrow into cliff.

Real use shows the payoff. Product search that merges hyphen variants of co-education retrieves the same schools for all spellings, while a naive splitter returns different sets for each spelling.

3.6.2 Distinctive Tokens and Meaning-Preserving Splits

A distinctive token (a string with its own shape that must stay whole, for example jblack@mail.yahoo.com or 142.32.48.231) needs its own pattern. Email identifiers should stay as one unit rather than splitting on dots and the at sign. Web addresses should stay whole for the same reason. Phone numbers, zip codes, social security numbers and Aadhar numbers are distinctive and must be treated separately with their own patterns. Splitting them destroys the identifier. Dates, package tracking numbers and code symbols such as C++ and B-52 belong in the same group.

Other splits destroy meaning. San Francisco split into San and Francisco is no longer the city name. The two pieces point elsewhere, and a search for York University that returns New York University shows how bad the drift can get. Grammar, contractions and semantic equivalence must guide the cut. French ensemble cases make the same point. Forms such as un ensemble and the ensemble-like counterpart with a leading article look different after hyphen and space splitting, yet a French query should still bring back all ensemble documents. Splitting on hyphen and whitespace alone makes them different and recall falls.

Many language-processing systems prefer splitting because it is simple. Better semantic understanding needs tokenization rules that keep distinctive units whole and split only where grammar and meaning allow, so the final token examples stay correct. The rule of thumb: tokenize documents and queries with the same tokenizer, or identical strings will never meet.

Picture a fork in a pipe. One branch keeps San Francisco whole and the city query flows through. The other branch cuts it in two and the same query leaks away. The one-sentence takeaway: keep what names one thing as one token.

Scope: Whitespace and punctuation rules are language-specific. Assumption: Document language is known or detected before tokenizing. English heuristics for apostrophes and hyphens do not transfer to French clitics or German compounds without change.

Common traps: splitting emails and URLs on dots; folding all accents to English and merging distinct words; cutting hyphen variants three ways without an equivalence rule; and using different tokenizers for documents and queries so matching spellings never match.

3.6.3 Student Questions and Answers

Q: With all these apostrophe, hyphen and accent issues, can we still count terms or tokens for such sentences?

A: Yes, we can. Tokenization is possible, but it must respect language understanding and distinctive writing types such as emails, URLs, numbers and hyphen rules. Once language-specific precautions are in place, counts and lists become stable. That is why many search engines feel accurate today even though the raw text is messy. Apostrophe, hyphen and accent handling plus stable counts is the point to keep.

One-line recap: apostrophes mark possession or contraction, hyphens join or split ideas, accents mark distinct sounds, and distinctive strings must stay whole. Handoff: English already needs judgment, and other languages remove the space cue entirely, so segmentation rules must go per language.

3.7 Languages, Segmentation and No Single Tokenization

English gives us spaces between words. What if the text has no spaces at all, runs right to left, or glues a whole sentence into one long word? One fixed splitter cannot survive that range.

Tokenization rules differ a lot from language to language. Space helps in English to separate words and their meanings. The same cue fails elsewhere. There is no single correct tokenization across languages, applications and user expectations. The right token depends on language, on the task such as search, language processing, question answering or a simple website, and on what users expect.

Picture road markings. In one town white lines mark lanes, in the next town there are no lines and drivers judge gaps by feel. An English-only splitter is a driver who trusts lines everywhere and then panics where lines do not exist. Where the picture breaks: roads still share cars and rules, while languages differ in script, direction and word shape, so the splitter itself must change, not just the driver.

3.7.1 Cross-Language Segmentation

English uses spaces between words, which helps a lot. Chinese does not use spaces in the same way. The running text is a group of symbols where one syllable-like chunk may be several symbols together. A picture example in class showed a Chinese string where we cannot tell whether a small gap is a word gap or a letter gap. That brings fresh complexity from the language itself. Options are dictionary longest-match segmentation, sequence models such as hidden Markov models or conditional random fields trained on hand-cut text, or character k-grams that skip words entirely. Each can fail because different cuts can each be correct.

German builds very long single words where English would use several words. The string has no spaces. Translated into English it becomes several tokens such as life insurance company employees for one example and computational linguistic for another long item discussed as computer linguistic. Splitting those compounds is a must for German, because leaving them whole blocks matches against English-style queries. Yet splitting is not free. The monk-style example in class showed two small units that mean and and still alone but mean monk together. Splitting there creates the wrong meaning. Together-meaning versus alone-meaning must be decided by a language rule, not by spaces. A nearby German item for competitive index style wording raised the same pronunciation and segmentation doubt in class, which shows even a careful reader can be unsure where to cut. The standard fix is a compound-splitter that checks whether parts appear in a vocabulary, while also keeping the full form when the joined sense differs.

Japanese adds more layers. Words can appear without spaces as one large compound that a person can read but a machine cannot segment reliably. Segmentation is not unique because different cuts can each be correct. Japanese also uses multiple writing styles, with Chinese characters mixed with hiragana, katakana and Latin letters, and the class example showed only one style, so a model trained only on symbols for one style still misses other styles. Direction adds another axis. Text is not always left to right. Arabic runs right to left with mixed-order numbers, so a tokenizer fixed to one direction fails there.

Some patterns are unique and must be preserved across languages. Email identifiers, web addresses, phone numbers, zip codes and national identifiers keep their shape. Hyphen behavior, white space behavior and contraction behavior must be decided per language, not copied from English.

Real-world progress is visible. Translation quality and mother-tongue website search improved a lot over about seven to eight years once language-specific handling at the basic level was done well. Earlier many sites were English-only. Now many sites support the reader mother tongue because tokenization and normalization respect each language, including Japanese styles and mother tongue expectations.

3.7.2 Worked Mini-Examples

Worked example 1 — San Francisco city token versus split pieces. Setup: surface has two space-separated pieces. Naive split gives $[San, Francisco]$ . Correct handling keeps $[San Francisco]$ as one token for the city reading. In symbols, the city reading needs:

$T (San Francisco) = [San Francisco]$

where $T$ maps surface text to tokens and the single entry names the city. Splitting gives some other thing, never the city. Lesson: splitting on whitespace is not correct here, and phrase handling must back up the tokenizer.

Worked example 2 — German compound to English phrase. Setup: one long German token with no spaces, for instance Lebensversicherungsgesellschaftsangestellter. English translation needs several tokens, for instance life insurance company employees. Method: split the compound into stems for the index, but keep the full form as well when the joined meaning differs from the parts. Lesson: compound splitting is required, yet blind splitting can invent false matches such as computer versus computational for the computational linguistic case. German compound splitting with full-form retention is the safe pattern.

Worked example 3 — monk-type joining. Setup: two Chinese characters mean and and still alone. Together they mean monk. Method: keep the joined token for the monk reading and avoid indexing only the parts for that span. A splitter that outputs only [and, still] loses the monk sense and adds two false content hits. Lesson: together-meaning versus alone-meaning must be decided by a language rule, not by spaces. Monk together meaning versus and still alone is the warning to carry forward.

Picture three strips. An English strip with clear gaps, a German strip as one long bar that must be sawn into planks but with the whole plank kept aside, and a Chinese strip of tiles where one cut gives monk and another gives and plus still. The one-sentence takeaway: the same gap can be a word edge in one language and mere tile grout in another.

Scope: Segmentation choices are per language and per task. Assumption: Language is detected at a sensible span such as document or paragraph, with mixed spans handled by quoting or tagging. Character k-grams help when word edges are truly unclear, at the cost of larger indexes.

Common traps: copying English space rules to Chinese or Japanese; splitting German compounds and throwing away the full form; training a Japanese model on one script and missing the others; and hard-coding left-to-right order so Arabic order breaks.

3.7.3 Student Questions and Answers

Q: If tokenization depends on language and application, how do we ever finish tokenization for a search engine?

A: We finish it per language and per task. We state the language, the application such as search or question answering, and user expectations, then we apply that tokenization. Language-specific precautions make the result stable enough for accurate search. There is no single tokenization, but there is a finished one for each setting.

One-line recap: Chinese needs segmentation, German needs compound splitting with full-form backup, Japanese needs multi-script handling, and Arabic needs direction handling. Handoff: once boundaries respect language, the next choice is which tokens deserve to stay, which brings stop words and normalization.

3.8 Stop Words, Normalization and Case Decisions

Most words on a page add little meaning by themselves, yet deleting them all can erase a song title or merge two different phrases into one. How do we shrink the index without losing the phrases users actually type?

Stop words (very frequent words that give very low meaning to a document, for example a, is, and, to, on and up) are mostly joining words. They join actual expressions but add little context by themselves. Normalization (bringing variant surface forms to one consistent form, for example USA and U.S.A. to one entry) ensures matching between queries and documents. It brings consistency among tokens the way score standardization brings consistency among numbers. For discrete and continuous data we use z-score or min-max forms. For text we use lowercasing, punctuation handling, accent folding and synonym grouping. The shared goal is one nomenclature through the whole pipeline.

Think of normalization as agreeing on one spelling for the team roster. USA and U.S.A. must point to one entry. Color and colour must point to one entry. Without that agreement, the same idea filed under two names never meets its query. Where the roster picture breaks: players have one true name while words have accents, cases and synonyms, so the agreed form must be chosen per collection language, not once for all teams.

3.8.1 Stop Words

We remove stop words to keep the index small and to keep important words in focus. An inverted index stores dictionary terms plus postings lists. Without removal, a term such as a would carry a very long postings list while important terms such as systematic, computer or machine learning carry shorter lists. Frequent joiners would then sit in front while content words sit backstage because their frequencies are lower. Removal cuts index size and improves efficiency.

Removal can hurt quality, and two classroom cases prove it.

Worked example 1 — song title to be or not to be removal loss. Setup: title holds six words, all on a broad stop list. Method: delete every stop word. Result: nothing remains, an empty term list. The song can never be retrieved by its title because no term points to it. Sense-check: if the whole query vanishes, recall for that query drops to zero.

Worked example 2 — car, automobile, service and repair equivalence retrieval. Setup: a repair shop page uses automobile repair while the user types car service station. Without synonym handling the two word sets share nothing and the nearby shop never surfaces. Method: build an equivalence class with car = automobile and service = repair, then map both sides to shared terms. Result: the automobile repair page appears among retrieved documents for the car query because token relationships are maintained. Sense-check: recall rises for true synonyms while unrelated pages stay out.

Phrase collapse is the second cost. The song title case shows loss by emptying. King of Denmark without of becomes King Denmark, which no longer signals the royal reading cleanly. President of United States and President United States both become President United States after removal. The two indexed forms look the same, yet one source text is about politics and the other is about designations. Retrieval then returns dissimilar documents as if they matched equally.

The key design choice is how many stop words to remove. Traditional systems used about 200 to 300 terms, driven by hardware limits and the need to save space. Modern systems keep only about 7 to 12 words for full removal, because removing too many words hurts retrieval quality. Modern storage uses cloud capacity with good space and good list handling, plus compression and weighting that tame long lists, so full deletion is no longer needed for every frequent word. The current practice is to build a small custom stop list of words that surely give no information for the task, and to retain the rest with low weight. Down-weighting keeps document context and keeps query and retrieved documents semantically close, while low weights stop frequent words from dominating the ranking. The class line was we do not blindly remove everything, we group and weight only when it improves retrieval.

Real use follows that line. Web engines down-weight joiners instead of deleting them, so a phrase query with of still ranks the politics page above the designations page.

Exam note: Be ready to argue both sides. State space saving and efficiency for removal, then state title loss with to be or not to be, phrase collapse with King of Denmark and President of United States, and the traditional 200 to 300 versus modern 7 to 12 guidance. Recommend a small task-specific removal list plus down-weighting.

3.8.2 Normalization and Equivalence Classes

Normalization maps many surface forms to one common word so the same idea follows one nomenclature. USA and U.S.A. normalize to one of USA or United States of America. The system must be told beforehand that they are not two different words. Color and colour normalize to one spelling, either British or American, for the whole collection. Resume with an accent in French and resume without it in English normalize toward the collection language. If the engine is English, the common form follows English. If the engine is French, the common form follows French. Anti-discriminatory with a hyphen and without it must also normalize to one form. After that decision, hyphen handling stays consistent, for instance always keeping the hyphenated shape as a complete word when that is the chosen rule.

Synonym handling creates an equivalence class (a set of different surface terms treated as one index term, for example car and automobile in one class). Car equals automobile and service equals repair in the running example. A query for car service and a document about automobile repair must meet. The story used was an automobile repair shop right next to home that never surfaced for a car service station query. After normalization, car, automobile and related synonyms for car all map to car, while service and repair map to one of service or repair. Then document one about automobile repair appears among retrieved documents for the car query, because token relationships are maintained.

That grouping is not always symmetric. Normalization is about smart matching decisions based on context and meaning, not blind grouping. The Windows case shows why. Small-w windows as a common noun can mean house windows or the plural of window. To avoid missing results, its normalization expands to include window, windows and capital-W Windows for the operating system reading. Capital-W Windows as a noun means Microsoft Windows only. House windows are never written with capital W in that position, so capital-W Windows normalizes only to Windows without expansion. Small-w includes the capital form to be safe. Capital-W does not include the small forms because that would add noise. The rule for small-w windows is see windows then include window, windows and capital-W Windows. That rule is context-aware, not pure rule matching for every case. Windows small capital asymmetric smart matching is the intuition to keep: expand the vague form, keep the precise form narrow.

Picture three buckets. One bucket holds USA, U.S.A. and United States of America under one label. One holds color and colour under one label. One holds car and automobile under one label, with an arrow that runs one way for windows: small-w flows to all three forms, capital-W stays put. The one-sentence takeaway: group what users mean as one, but let precision flow only where it is safe.

Scope: Equivalence classes help when variants truly share meaning for the task. Assumption: Query and documents get the same normalization, or identical ideas will still miss. Over-grouping such as folding C.A.T. to cat shows what happens when the rule ignores context.

Common traps: deleting 200 plus words and then wondering why titles vanish; merging President of United States with President United States and calling them equal; folding case before using the capital-W clue; and expanding synonyms both ways when only one direction is safe.

3.8.3 Case Folding and Truecasing

Case folding (reducing all letters to lowercase, for example Apple to apple and Data to data) is one of the simplest normalization steps. Capital A Apple becomes apple. Mixed-case Data becomes data. The definition is simply reducing all letters to lowercase.

Order matters. Do context-sensitive normalization first, then fold case. Otherwise the capital-W versus small-w difference for Windows disappears before we can use it. Titles and sentence-initial words are safe to fold. Introduction to a subject as a title can go to lowercase without worry. Mid-sentence capitals often carry meaning and should not be folded. Acronyms such as UAE and USC in mid-sentence carry meaning. Windows in I use Windows in mid-sentence with capital W is a proper noun for the operating system, not house windows. Blind lowercasing of that sentence would map the operating system reading to the house-window reading. The guiding line was normalization reduces superficial differences but must preserve semantic meaning, and not all differences should be removed. Truecasing (restoring correct case with a sequence model before deciding what to fold) is the careful alternative when users mix cases freely.

3.8.4 Student Questions and Answers

Q: Should stop words not just get low weight through the inverse document frequency factor instead of being deleted?

A: Yes, that is the modern view. Common terms get reduced weight, most likely through the inverse document frequency effect, so frequent joiners score low without being erased. Keep a tiny removal list for words with no signal, then retain the rest with low weight so context stays intact and ranking stays stable.

Q: In the terms example with nine survivors, why did we drop even content-looking words from tokens?

A: Terms are normalized words. Normalization drops stop words and duplicate shapes and folds variants, so only matching-meaning words stay. Survivors such as young, way, actual and person remain because they carry matching meaning. That is what lets us claim the text is normalized well. Otherwise we cannot claim it.

Q: Where do published English stop lists come from, and does the NLTK toolkit use that repository?

A: The class pointed to a long-standing public repository with English stop words and noted that lists exist for all other languages too. We pick the most irrelevant words for our task and remove only those. The NLTK source question was left open for the next meeting, with a note to check the NLTK handling and answer then.

Small lists, shared rules, case last. That order keeps titles findable and phrases distinct.

One-line recap: drop only sure stop words, group true variants into equivalence classes with asymmetric Windows handling, and fold case after context checks. Handoff: with surface forms unified, the last squeeze on variation comes from stemming and lemmatization.

3.9 Stemming, Lemmatization and Porter Rules

Compress, compressed, compression: three spellings, one idea. Should the index store three entries or one? Storing three wastes space and splits matches. Merging them wrongly merges unrelated words. How do we pick the merge that helps search?

Stemming (chopping affixes by rule without regard to meaning, for example compressed to compress by cutting ed) produces a computationally efficient form. Lemmatization (mapping to a linguistically valid base form, for example are to be with a dictionary check) produces a linguistically normalized form. Both reduce word variation further after case and accent steps. The answer to how we reduce variation further is stemming and lemmatization.

Picture two kitchen tools. A stemmer is a fast chopper that cuts ends off every vegetable the same way. A lemmatizer is a careful cook who knows each vegetable and cuts only what each one needs. The chopper is quick and mostly right. The cook is slower and more exact. Where the picture breaks: vegetables stay edible either way, while chopped words may stop being real words at all, yet still work fine as index keys if the same chop applies to queries and documents.

A stem (the chopped remainder, for example oper from operate, which may not be a real word) may not be a real word. A lemma (the real dictionary base, for example see for saw used as a verb) is a real dictionary base. That single contrast drives the choice. If chopping still gives decent results, stemming is attractive because it is light. If the task needs high precision on meaning, lemmatization is attractive even though vocabulary size and cost grow. When unsure, try both and keep the one where the model learns better. Both can also be combined as a hybrid for some pipelines.

Real use splits by goal. Sentiment analysis, language understanding tasks and chatbots often prefer lemmatization for precision, while large web search often prefers stemming for speed and smaller load on machines.

3.9.1 Stemming Versus Lemmatization

Worked example 1 — compressed, compression and equivalent with chopped forms. Setup: test words are compressed, compression, example and equivalent. By meaning, compressed and compression are both accepted as equivalent to compress, while example should not be chopped.

Stemming drops the final e in example because a rule says endings such as le and t-like tails chop off regardless of meaning. Compress from compressed is fine. Compression to compress is fine. Equivalent to equivalent gets chopped even though no change was expected, because the rule fires on the letters, not on the meaning. That is stemming: fast, letter-driven, sometimes surprising.

Lemmatization keeps meaning. Compressed and compression both map to compress, which feels fair for this case, while example stays whole because the dictionary knows it is already a base. The class stressed that this single example was staged to make lemmatization look better, but neither method is good over the other in general. Sense-check: stemming trades some precision for speed and recall, lemmatization trades speed and index size for precision.

In short, lemmatization is the linguistically normalized form and stemming is the computationally efficient form. Use stemming when the goal is a lightweight model without burden on machines. Use lemmatization when the goal is high-precision models such as sentiment analysis, language understanding and chatbots. Use stemming for web-scale search where cost dominates. Judge by where the pipeline needs precision and what the budget allows. Exact stemmed forms do not matter, only the equivalence classes they form: as long as queries and documents chop the same way, oper can stand for a whole family.

Exam note: Be ready to contrast the two on example, equivalent, compressed and compression. State which forms change, why stemming changes example by letter rules, and when to pick each method: stemming for light search, lemmatization for precise meaning tasks.

3.9.2 Porter Five-Phase Reductions and Measure Condition

Porter stemming (a widely used rule-based stemmer from the textbook, applied in five sequential phases) applies five phases in order. The phases are sequential and do not overlap. One phase finishes, then the next applies. Early phases handle plurals and past participles. Later phases use a measure of the word that loosely checks syllable-like length through vowel-consonant sequences, to decide whether the word is long enough to chop a suffix safely.

Phase one rules handle s-endings with longest-suffix priority. The SSES to SS rule says if the ending is SSES then it becomes SS. The example was caresses to caress, where caresses is a plural-like form and caress is the kept stem. The IES to I rule says endings with IES go to I. The example was ponies to pony in class, written as ponies to poni at the intermediate rule stage in the reference, where ponies is plural and pony or poni is the kept stem; both forms conflate the same plural class and the final y handling leaves them equivalent for retrieval. The SS to SS rule keeps forms such as caress as caress with no change, which stops the single-S rule from firing wrongly. The single-S rule drops the final s for plurals such as dogs to dog. The class summary was all first plurals and past participles are treated in this phase.

Later rules add a length condition that stops blind chopping. Define $m$ as the Porter measure that counts vowel-consonant sequences in the stem, where $m$ loosely checks the number of syllables to see whether a word is long enough that the matching part is truly a suffix rather than part of the stem. Let the stem be the word with the candidate ending removed. Then the EMENT rule is:

$(m > 1) EMENT \to empty$

Here $m$ is the measure of the stem, EMENT is the ending letters E-M-E-N-T, and empty means delete the ending. In words: if $m$ on the stem is greater than one, remove EMENT, else leave the word alone. The verbal gloss from class matches: the rule checks whether the stem before EMENT is long enough in vowel-consonant shape, and only then takes off the last sequence.

Worked example 2 — caresses, ponies and dogs reductions plus replacement versus cement. Phase one trace: caresses ends in SSES, so caresses maps to caress. Ponies ends in IES, so ponies maps to pony, written poni at the rule-group stage. Dogs ends in single S with a valid stem, so dogs maps to dog. Caress ends in SS, so the identity rule keeps caress as caress.

Length-gated trace: replacement minus EMENT leaves replac. The stem replac has measure $m > 1$ , so the rule fires and replacement maps toward replac. Cement minus EMENT leaves only c. The stem c has measure $m = 0$ and c is not a usable base apart from single-letter words such as I, so the rule is blocked and cement stays cement. The contrast shows Porter stemming is not blind chopping. It uses conditions to control errors as well. Other named stemmers mentioned were Lovins and Paice or Husk stemmer forms. They were listed as additional options beyond Porter, with more detail left for the next meeting.

Picture a gate before a blade. Short words such as cement face a locked gate and keep their ending. Long words such as replacement pass the $m > 1$ gate and meet the blade. The one-sentence takeaway: length first, cut second.

Scope: Porter rules are English-specific and order-dependent. Assumption: Each phase runs to completion before the next begins, with longest-suffix priority inside a phase. Running phases out of order or skipping the measure check reintroduces the very errors the gates were built to stop.

Common traps: running EMENT removal on cement and keeping c; treating ponies to pony as pure meaning work instead of letter rules plus gates; expecting stems to be real words when only equivalence matters; and picking stemming for a precision-critical chatbot or lemmatization for web-scale search without testing both.

3.9.3 Student Questions and Answers

Q: For the cement case, what does long enough mean? Is there a threshold for dropping EMENT?

A: Long enough means the stem measure $m$ passes the stated limit $m > 1$ , where $m$ counts vowel-consonant sequences in the stem before EMENT. Replacement passes because the stem replac stays long enough for the stemmer purpose. Cement fails because stripping EMENT leaves only c, with $m = 0$ , which is not a lemma word and not a usable base. The follow-up check asks whether the remaining form is a valid base before allowing the cut.

Q: If we had cements with an S, would the same logic apply?

A: Yes, in two steps. First the plural rule maps cements to cement, like dogs to dog, where the single-S ending behavior reduces the plural to singular. Then the $m$ greater than one rule for EMENT comes into the picture again on cement. It still blocks because cement is not long enough to leave a valid base after removing EMENT.

Q: Is Porter stemming or lemmatization, and where should each be used?

A: Porter is stemming, not lemmatization. Use stemming for lightweight search pipelines and use lemmatization for high-precision sentiment, language understanding and chatbot pipelines. Both can be used interchangeably in some setups or as a hybrid, and the final pick should follow which process lets the model learn better. More stemming variants such as Lovins and Paice were promised for the next meeting after the session ended early for technical reasons.

Chop fast or cook carefully. Test both, then keep the one where the model learns better.

One-line recap: stemming chops by letters with $m$ -gated Porter phases, lemmatization maps to true bases, and replacement to replac with cement blocked proves the gate works. Handoff: the full chain from matrix to stemmed terms is now in place and ready for exam review.

Exam Guidance Summary

Use this section as a final checklist. Each note below maps to one concept and names the working to show.

Exam note: do incidence matrix and inverted index problems with pen and paper. Rows are terms in ascending order, columns are $D_{1}$ to $D_{4}$ , cells are $1$ or $0$ , and postings lists are sorted. Draw the full grid first, then write each $P (t)$ in increasing order. That habit prevents missed terms and lost marks.

Exam note: for Boolean optimization, compute each bracketed union size and do the smallest union first, then intersect with the smallest set first. Name set one, set two and set three as given and respect query brackets. Show size sums such as the 46, 6, 5 and 3 comparisons and the large 213000-scale list with 213312, 87009 and related sizes to justify the order. Never re-pair across brackets.

Exam note: define $a$ as total relevant, $c$ as total retrieved and $b$ as relevant retrieved before any division. Precision is $\frac{b}{c}$ from the prediction lens. Recall is $\frac{b}{a}$ from the actual lens. Practice $\frac{7}{10}$ for precision and $\frac{7}{20}$ for recall until the denominator choice is automatic. Write true positives, false positives and false negatives alongside $a$ , $b$ and $c$ .

Exam note: for tokens, types and terms, show numbered slots for tokens, cross out duplicates for types, then apply the stated stop list and base-form rules for terms. Rehearse to sleep, perchance to rest with five tokens, four types and three terms, and the young sentence with eleven tokens, nine types and five terms. State tokens as occurrences, types as unique words and terms as normalized words.

Exam note: for stop words and normalization, argue both directions. List space saving and efficiency for removal, then title loss with to be or not to be, phrase collapse with King of Denmark and President of United States, and the traditional 200 to 300 versus modern 7 to 12 guidance. Recommend a small task-specific removal list plus down-weighting through inverse document frequency effects.

Exam note: for case and stemming, state order as context-sensitive normalization before case folding, with titles and sentence-initial words safe to fold and mid-sentence UAE, USC and Windows preserved. Contrast stemming and lemmatization on compressed, compression, example and equivalent, then state Porter phase-one endings SSES, IES, SS and S with the $m > 1$ guard where replacement maps to replac while cement stays cement, plus cements to cement in two steps.

Key Industry Applications

Real-world: Boolean postings with sorted lists power web and mail search over large sparse collections without storing zeros. Dictionary frequencies live in memory while postings stream from disk, so billions of words stay searchable.

Real-world: smallest-first union and intersection ordering keeps large-scale merging fast when some terms have tiny lists and others have lists above 200000 entries, such as eyes near 213312. Short stacks lead in every production merge.

Real-world: precision from the prediction lens and recall from the actual lens guide search quality, shop search tuning, and detection of overfitted models that chase precision while recall falls. Teams track both on judged sets before shipping rank changes.

Real-world: email, web address, phone, zip code and Aadhar handling plus compound splitting for German and segmentation for Chinese and Japanese keep multilingual search and mother-tongue websites usable. Per-language tokenizers made that broad coverage possible over recent years.

Real-world: small custom stop lists with down-weighting preserve phrase meaning for titles such as to be or not to be while keeping index size and ranking efficiency under control. Phrase queries with of keep their signal instead of collapsing.

Real-world: equivalence classes for car and automobile plus context-aware Windows handling lift recall for car service station queries without merging unrelated senses. Asymmetric expansion keeps the vague form broad and the precise form narrow.

Real-world: stemming for web-scale search and lemmatization for sentiment analysis, language understanding and chatbots match the method to the cost and precision goal, with hybrid use when testing shows better learning. Porter, Lovins and Paice stemmers cover the classic rule-based options, with NLTK as a common toolkit for trying them.

IR Lecture 3 notes · Search Engine Indexing From Raw Text to Normalized Terms

Information Retrieval· undergraduate· 2026-09-14

Sections Breakdown

1Term-Document Incidence Matrix and Inverted Index

Builds the binary term grid and flips it into sorted postings lists with zeros dropped.

2Query Processing Order and Postings Size

Orders bracketed unions and intersections from the smallest postings size first.

3Precision, Recall and Retrieval Quality

Scores returned sets with precision from the prediction lens and recall from the actual lens.

4Indexing Pipeline and What Counts as a Document

Collects sources, fixes document granularity, tokenizes, normalizes, then builds postings.

5Tokens, Types and Terms

Separates raw occurrences from unique shapes and normalized index terms with hand counts.

6Tokenization Is Not Simple Splitting

Handles apostrophes, hyphens and accents while keeping emails, URLs and names whole.

7Languages, Segmentation and No Single Tokenization

Segments Chinese, splits German compounds, and handles Japanese scripts and Arabic direction.

8Stop Words, Normalization and Case Decisions

Trims a tiny stop list, groups equivalence classes, and folds case after context checks.

9Stemming, Lemmatization and Porter Rules

Chops endings by Porter rules behind the length gate or maps to true dictionary bases.

Undergraduate students studying Information Retrieval

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Term-Document Incidence Matrix and Inverted Index

Must-know: Terms are ascending rows, documents are columns, inverted index drops zeros and keeps sorted postings

$M_{t, d} = 1 if term t occurs in document d, else M_{t, d} = 0$

Top pitfall: Flipping rows and columns or leaving postings unsorted

Self-check: Given row [1,1,0,0] across D1-D4, what is P(drug)?

Connects to: 3.2

Query Processing Order and Postings Size

Must-know: Smallest bracketed union first, then smallest intersection first, never rewrite brackets

$cost (P (a) \cup P (b)) = O (∣ P (a) ∣ + ∣ P (b) ∣)$

Top pitfall: Re-pairing across brackets or judging OR by one side only

Self-check: With sums 363465, 379571, 300321 which union runs first?

Connects to: 3.1, 3.3

Precision, Recall and Retrieval Quality

Must-know: Precision b/c from prediction lens, recall b/a from actual lens

$Precision = \frac{b}{c}$

Top pitfall: Swapping denominators so precision divides by a

Self-check: With a=20, c=10, b=7 what are precision and recall?

Connects to: 3.2, 3.4

Indexing Pipeline and What Counts as a Document

Must-know: Collect, tokenize, preprocess, index; granularity trades precision against recall

Top pitfall: Treating each file as one document without thinking about granularity

Self-check: Why must tokenization come before stop word checks?

Connects to: 3.3, 3.5

Tokens, Types and Terms

Must-know: Tokens slots, types shapes, terms normalized survivors with tokens>=types>=terms

Top pitfall: Dropping stop words when counting types

Self-check: Why does to sleep perchance to rest give 5 tokens 4 types 3 terms?

Connects to: 3.4, 3.6

Tokenization Is Not Simple Splitting

Must-know: Tokenization needs language decisions; keep distinctive units whole

Top pitfall: Splitting emails and URLs or using different tokenizers for docs and queries

Self-check: Why do full-text, full text and fulltext need one rule?

Connects to: 3.5, 3.7

Languages, Segmentation and No Single Tokenization

Must-know: No single tokenization; segment Chinese, split German, handle Japanese scripts and Arabic direction

$T (San Francisco) = [San Francisco]$

Top pitfall: Copying English space rules to Chinese or dropping German full forms

Self-check: Why must monk stay joined while life-insurance compounds split?

Connects to: 3.6, 3.8

Stop Words, Normalization and Case Decisions

Must-know: Small custom stop list plus down-weighting; equivalence classes with asymmetric Windows rule; case fold last

Top pitfall: Deleting broad stop lists so titles vanish or folding case before Windows check

Self-check: Why do 200-300 stop words hurt titles like to be or not to be?

Connects to: 3.7, 3.9

Stemming, Lemmatization and Porter Rules

Must-know: Stemming chops by letters, lemmatization maps to true base; Porter EMENT needs m>1 so replacement passes and cement blocked

$(m > 1) EMENT \to empty$

Top pitfall: Running EMENT removal on cement or expecting stems to be real words

Self-check: Why does replacement map to replac while cement stays cement?

Connects to: 3.8

Previous LectureLecture 02 · IR Models: Boolean, Vector, and Probabilistic Retrieval

Next LectureLecture 04 · Stemming, Skip Pointers, Phrase Search and Tolerant Retrieval

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

3.1 Term-Document Incidence Matrix and Inverted Index

3.1.1 Mathematical Formulation

3.1.2 Worked Examples

3.1.3 Student Questions and Answers

3.2 Query Processing Order and Postings Size

3.2.1 Mathematical Formulation

3.2.2 Worked Examples

3.2.3 Student Questions and Answers

3.3 Precision, Recall and Retrieval Quality

3.3.1 Mathematical Formulation

3.3.2 Worked Examples

3.3.3 Student Questions and Answers

3.4 Indexing Pipeline and What Counts as a Document

3.4.1 Procedural Steps

3.4.2 Document Sources and Granularity

3.4.3 Preprocessing Order

3.5 Tokens, Types and Terms

3.5.1 Worked Examples With Counts

3.5.2 Student Questions and Answers

3.6 Tokenization Is Not Simple Splitting

3.6.1 Apostrophes, Hyphens and Accents

3.6.2 Distinctive Tokens and Meaning-Preserving Splits

3.6.3 Student Questions and Answers

3.7 Languages, Segmentation and No Single Tokenization

3.7.1 Cross-Language Segmentation

3.7.2 Worked Mini-Examples

3.7.3 Student Questions and Answers

3.8 Stop Words, Normalization and Case Decisions

3.8.1 Stop Words

3.8.2 Normalization and Equivalence Classes

3.8.3 Case Folding and Truecasing

3.8.4 Student Questions and Answers

3.9 Stemming, Lemmatization and Porter Rules

3.9.1 Stemming Versus Lemmatization

3.9.2 Porter Five-Phase Reductions and Measure Condition

3.9.3 Student Questions and Answers

Exam Guidance Summary

Key Industry Applications

IR Lecture 3 notes · Search Engine Indexing From Raw Text to Normalized Terms

Sections Breakdown

Exam Revision Notes

Term-Document Incidence Matrix and Inverted Index

Query Processing Order and Postings Size

Precision, Recall and Retrieval Quality

Indexing Pipeline and What Counts as a Document

Tokens, Types and Terms

Tokenization Is Not Simple Splitting

Languages, Segmentation and No Single Tokenization

Stop Words, Normalization and Case Decisions

Stemming, Lemmatization and Porter Rules

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat