Stemming, Skip Pointers, Phrase Search and Tolerant Retrieval

4.1 Preprocessing Recap: Tokenization, Stop Words and Normalization

4.1.1 Why Simple Steps Are Hard

Why would splitting text into words need a full lecture? The answer is that each tiny choice changes what the index holds.

Tokenization (splitting running text into tokens) sounds simple. It is not. Punctuation, hyphens, numbers, and compounds all force decisions. A hyphen in state-of-the-art can mean one token or four. A number like 2026 can be a year, a count, or part of a code. Each decision changes the token stream that flows into the index.

Normalization (mapping variant surface forms to one canonical form) needs the same care. Upper case and lower case, accented and plain letters, and alternate number forms must map to one shape. Rules must fit the retrieval goal. A rule that helps one query set can hurt another, so there is no single safe default.

Think of preprocessing as a prep line in a kitchen. Raw text enters at one end. Tokenization chops it into pieces. Normalization washes the pieces into one shape. Stop-word handling, stemming, and lemmatization trim and sort them. Clean packs leave the line as index terms. The analogy breaks at one point: a kitchen serves one meal, while this line runs twice, once on documents at index time and once on queries at search time. Both runs must use the same chain, or matching breaks. A document indexed as State-of-art never meets a query split as state of the art.

Picture a line chart that tracks index size as each step is added. The horizontal axis lists the steps in order: raw tokens, after normalization, after stop-word removal, after stemming. The vertical axis shows term count. The curve drops steeply at stop-word removal and again at stemming. The takeaway is that early steps shrink the index a lot, so each one deserves care.

That chain leads straight to the hardest judgment call in it: which words to drop.

4.1.2 Stop Words and the To-Be-Or-Not-To-Be Problem

Stop words (very common words that mainly join other words) look easy to remove. Words such as to, the, be, on, and up seem to add little meaning. A first plan says to list every joining word and drop all of them.

Walk the line through the plan step by step. The tokens are to, be, or, not, to, be. Mark to, be, or, and to as stop words. Only not survives as a content word. A query for the full line then has one term to match on, and the phrase is gone. Bold answer: aggressive dropping empties the line. Sense-check: a title search for that line would fail, which proves the plan is too crude.

That failure sets up the real trade. Some systems keep a stop list near 300 terms. Others keep a very short list. The right size depends on the collection and on the queries. Dropping too much harms phrases and titles. Dropping too little leaves a large index with little gain. A public stop-word list was shown in class for review. The list builds a feel for which words are often dropped and which are kept when phrases matter.

4.1.3 Normalization Needs Rules

Normalization maps forms such as lower case and upper case, accented and plain letters, and number forms to one shape. Each mapping needs a stated rule. Case folding maps Apple to apple. Accent stripping maps resume with accents to a plain form. Number rules decide whether 1,000 equals 1000.

Without rules, two copies of the same word miss each other at match time. With bad rules, two different words collapse into one. A rule that folds all case helps Apple the fruit meet apple the query, but it also merges the company name with the fruit. State each rule, then test what it merges and what it splits.

4.1.4 Student Questions and Answers

That open item is where the lecture turns next: conditioned stemming rules.

4.2 Porter Stemming Rules

4.2.1 What Stemming Does

Why cut words down at all? Because am, are, and is all point at the same idea, and an index that stores all three wastes space and splits matches.

Stemming (cutting inflected words to a shorter stem) trades meaning for compact matching. A stemmer can map am, are, and is to be. Then the sentence the boys cars are different colors becomes the boy car be different color. Much of the sense stays. The forms are shorter and fewer, so the index shrinks and recall rises.

The word stem means the crude cut form. It may not be a real word. The word lemma means the dictionary base form. So comput can be a stem without being a word, while compute is the lemma a dictionary would list. That contrast matters for the next sections, where lemmatization keeps real words and stemming does not.

4.2.2 Porter Rules in Plain Words

Porter's algorithm (a rule-based stemmer for English) applies suffix rules with conditions. It runs in five phases of reductions, applied in order. Within each phase, the rule that matches the longest suffix wins. Many later rules also check a length guard before they cut.

The first-phase plural rules from class behave like this. Words ending in SSES map to SS, so caresses goes to caress. Words ending in IES map to I, so ponies goes to poni in the reference form (heard in class as pony). Words ending in SS stay as SS, so caress stays caress. A lone trailing S drops, so cats goes to cat.

Pairs such as relational going to relate and conditional going to condition show the middle phases. The ending ational reduces to ate, and the ending tional reduces to tion. A word such as cement is left alone because the stem would be too short.

The reconciled rule behind the garbled class wording is the EMENT rule. In full form, with the ending EMENT removed when the guard holds:

$$(m>1)\text{ EMENT }\to \text{ empty}$$

Here $m$ is the stem measure and EMENT is the suffix letters. Walk it on two words. For replacement, the stem before the ending is replac, whose measure clears the guard, so EMENT drops and replacement maps to replac. For cement, the stem before the ending is c, whose measure is too small, so the rule is blocked and cement stays cement. Bold answer: replacement shortens, cement is untouched. Sense-check: a one-letter stem cannot be a real base, so blocking the cut is the safe move.

Search engines use Porter-style stems to conflate plurals and verb forms before indexing. Plurals, verb endings, and common derivations collapse into shared stems, which keeps the vocabulary small.

4.2.3 Why the Rules Are English-Specific

The rules fit English spelling habits: plurals in S, past forms in ED, progressive forms in ING, and Latin-style endings such as ational and tional. An old working guess was that most web browsing used English, near 90 percent English and 10 percent other languages at that time. That share has shifted since. Still, the rules were built round English plurals and verb endings, so they do not transfer as-is to other languages. Each language needs its own suffix tables and its own guards.

4.2.4 Student Questions and Answers

On crudeness, a second question followed.

The same trade between crude cuts and careful cuts drives the next set of stemmers.

4.3 Other Stemmers: Lovins, Paice-Husk and Snowball

4.3.1 Lovins Stemmer

What if speed matters more than sense? That question leads to the oldest stemmer in this set.

The Lovins stemmer (a single-pass stemmer with about 250 rules) removes the longest matching suffix in one pass. In plain words, with $w$ for the input word and $s$ for the longest known suffix of $w$:

$$stem(w)=w\text{ with longest matching suffix }s\text{ removed}$$

Here $w$ is a string and $s$ is a string. One pass, longest match, done. The method is fast. It is less flexible and at times less accurate because many strict rules can overfit to narrow cases. A rule written for one ending keeps firing on words where that ending belongs to the stem.

4.3.2 Paice-Husk Stemmer

The Paice-Husk stemmer (an aggressive iterative stemmer) applies rules again and again over several passes. First-pass stems go back through the rules for a second and third pass. Each pass strips more letters, so the stems come out shorter than with one-pass methods. For some domains the scores are still strong, which can feel surprising given how short the forms look. Short forms conflate more variants, and on narrow vocabularies that extra conflation helps recall more than it hurts precision.

Think of sanding wood. Lovins makes one pass with coarse paper. Paice-Husk sands, checks, and sands again until the surface is smooth. The piece ends up smaller, and sometimes too small, but the finish is even. The analogy breaks where words are concerned: wood has no meaning to lose, while a stem can sand away sense.

4.3.3 Snowball Stemmer

The Snowball stemmer (a cleaner and more structured revision of Porter ideas) supports many languages, not just English. It keeps the conditioned-rule style but with tidier rule tables and language modules. Snowball is also the name of the rule-writing language behind it, so adding a language means writing a new stemmer in that language rather than patching English tables. Teams that index mixed-language collections pick Snowball because one framework covers many languages with the same conditioned-rule habit.

4.3.4 Worked Comparison on One Sample Passage

The same sample text was run through three stemmers. The passage reads: Such an analysis can reveal features that are not easily visible from the variations in the individual genes and can lead to a picture of expression that is more biologically transparent and accessible to interpretation.

Porter answers the same passage with more care.

With Paice-Husk, words were cut shortest of all: analys, rev, feat, vary, pict, transp. Forms looked heavily chopped, worse than Lovins on this passage. The lesson is practical. No stemmer wins on every text. The problem at hand decides which stemmer to pick. A Porter-style stem also shows the wider risk: stems such as oper group operate, operating, operation, operative, and operational into one form, so a query for operating system starts matching documents about operational research.

Real-world: teams building retrieval or NLP pipelines test several stemmers on their own data before they lock one in. They measure speed and match quality on their own queries, not on a demo passage.

4.3.5 Student Questions and Answers

Where stemming cuts too crudely for sense-heavy tasks, the next tool keeps real words instead.

4.4 Lemmatization: Rule-Based, Dictionary-Based, Hybrid and POS Tagging

4.4.1 What Lemmatization Does

What if the crude stem is the problem? Then stop cutting and start looking words up.

Lemmatization (mapping each word to its base dictionary form) keeps real words. The base form is called the lemma. Where stemming cuts computing and computer to one crude comput shape, lemmatization tries to keep the true base of each. That care costs more work: dictionary lookups, ending rules, and often a grammar analysis of the sentence.

A tiny contrast helps. Easy maps to easy as its own base. A chopped stem such as gen has no clear base. It could point to gene or to generation. After heavy stemming, asking for the lemma of a broken stem often has no good answer. The stem destroyed the signal the lemmatizer needs.

Think of stemming as nicknames in a big family: everyone called Jon, Jonny, and Jonathan answers to Jon. Fast, but two different Jonathans merge. Lemmatization is checking ID cards: each person keeps their legal name. Slower, but no wrong merges. The analogy breaks where cost is concerned: checking IDs scales badly to millions of documents.

4.4.2 Three Families

Rule-based lemmatization applies ending rules, much like stemming but aimed at real base forms. Dictionary-based lemmatization looks up the base form in a word list, so saw as a noun stays saw while saw as a verb maps to see. Hybrid lemmatization joins rules, dictionary lookup, and part-of-speech tagging (labeling each word as noun, verb, adjective, and so on). The tag helps pick the right base when one shape has two senses. Rules propose, the dictionary checks, and the tag breaks ties.

4.4.3 Part-of-Speech Tagging With the Bank Example

Take the word bank. In a swimming text, bank means river bank. In a finance text, bank means the place to keep money. The letters match. The sense does not.

4.4.4 Named Lemmatizers

Real-world starting points from class: the WordNet lemmatizer from the Python NLTK library is a common baseline. The spaCy lemmatizer from the Python spaCy library is widely used in pipelines. The Stanford lemmatizer and TextBlob are also used. The advice from class was to explore and test rather than pick one because a random web post suggests it. Match the tool to the data: check language coverage, speed on the collection size, and accuracy on the query types before locking one in.

4.4.5 Student Questions and Answers

With both tools on the table, the next question is when to pay for each.

4.5 Stemming Versus Lemmatization: When to Use Which

4.5.1 Speed Against Correctness

The whole choice fits in one line: pay with compute or pay with mistakes.

Stemming is light and fast. Lemmatization is heavy and careful. When exact sense matters less and many options can be shown, stemming is often enough. Web search can show ten links and let the reader pick. Then index-time speed and small indexes matter most. When sense and context matter a lot, lemmatization fits better. Sentiment analysis, chatbots, and query understanding need the river-bank against money-bank split to be right, because one wrong sense flips the answer.

A good rule of thumb from class: stemming gives cheap conflation for indexing, while lemmatization gives sound normalization for understanding. In plain words, use stemming for fast index forms and lemmatization for careful query sense when both are in play.

Pick stemming for broad indexing and lemmatization for careful understanding.

4.5.2 Hybrid Pipelines and Order Effects

Some NLP pipelines list both steps, either lemmatization then stemming or stemming then lemmatization. Blindly stacking both can harm scores. A stem step can break the forms that the lemma step needs, and the reverse can also wash out gains. One step often dominates and the other adds little. If a hybrid is tried, test with and without each step and keep only what lifts the target score.

A workable split discussed in class keeps stemming on long documents for index terms and lemmatization on short queries for sense. Both sides still meet in one shared space at match time, but each side uses the tool that suits its shape. Documents are long and many, so cheap stems help. Queries are short, so careful sense analysis pays off. The shared space still needs one common mapping, so test that the pair truly meets instead of assuming it.

4.5.3 Collection Size and Cost

When the document count runs into millions, compute cost pushes toward stemming. Each document pays the analysis cost once, but millions of documents turn a small per-word cost into a large bill. When the collection is of a size that is easy to manage and exact match matters, lemmatization is worth the cost. The pick is a trade between compute budget and need for exact sense. Query load matters too: a small collection with heavy query traffic can still favor cheap index forms.

Picture a chart with collection size on the horizontal axis and total analysis cost on the vertical axis. Two lines rise from the origin: a shallow line for stemming and a steep line for lemmatization. The gap between them is small at the left and wide at the right. The takeaway is that size multiplies the per-word cost gap, so large collections feel the choice most.

4.5.4 Student Questions and Answers

A second doubt asked for a concrete case where both appear.

A third doubt tested the size rule itself.

With terms settled, the lecture turns from words to the lists that store them.

4.6 Postings Lists, Merge Algorithm and Skip Pointers

4.6.1 Postings in Sorted Order

How does an engine find every document with a word without scanning all text? It looks the word up in a table.

A postings list (the list of document numbers holding one term) pairs each term with its document IDs. A tiny sketch is Brutus pointing to 1, 2, 4, 5. Each ID names one document holding Brutus. Document IDs stay in sorted order. Sorted order speeds merging and all later search steps, because both lists can walk forward together with no backtracking.

Think of two sorted attendance rolls. To find pupils on both rolls, two fingers walk down together. No finger ever moves back up. The analogy breaks where skips enter: fingers cannot jump pages, but postings lists can.

4.6.2 Merge for AND Queries

An AND query such as Brutus AND Caesar needs IDs present in both lists. The plain merge walks both sorted lists from the start. Call the list lengths $m$ and $n$, where $m$ and $n$ are counts of IDs. In plain words, the number of ID checks grows with the sum of the two lengths. In symbols:

$$T(m,n)=O(m+n)$$

Here $T$ is time cost, $m$ is the first list length, and $n$ is the second list length. The walk compares the two heads. Equal heads join the answer and both sides step. A smaller head steps its own side forward. Each step consumes at least one entry, so the total steps stay linear in the sum of the lengths.

4.6.3 Skip Pointers in One Paragraph

Skip pointers (forward jumps placed along a postings list) let the merge leap over blocks that cannot hold a match. The pointers are laid down at index time over the sorted lists. When one head is smaller, the code can jump that list ahead instead of stepping one by one. Jumps skip checks that are known to be useless because both lists are sorted. The guard keeps jumps safe: a jump fires only while the landing ID is still not past the other head. Skip pointers help AND queries, where both sides must agree. They do not help OR queries, where every entry from both sides is needed anyway.

4.6.4 Small Walkthrough

Take Caesar heads at 1 and Brutus heads at 2. The heads differ, so the smaller side moves. With a skip in place, the 1 jumps straight to 5. Now the compare is 5 against 2. The 2 side is smaller, so it jumps. The new compare is 5 against 16. Step by step, equal heads join the answer and smaller heads jump or step. The skipped IDs between jumps are never checked one by one. Each jump in this walk fired only because its landing still sat at or below the other head.

Picture the two lists as parallel number lines with curved arrows for skips. The horizontal axis on each line is document ID in sorted order. Each arrow starts at one ID and lands several slots ahead. The takeaway is that arrows bridge the dead bands where no match can hide, so the walk touches only a few heads.

4.6.5 Student Questions and Answers

A second question set the class list against production scale.

The small walk now grows into a full intersection with matches to count.

4.7 Skip Pointer Full Intersection

4.7.1 How Many Skips to Place

Where should the jumps sit? Too many jumps mean constant guard checks. Too few mean long dead bands with no bridge.

When the test or index gives skip positions, use them. When no positions are given, use the square-root rule. In plain words, take the length of the longer list, take its square root, and round up to set the gap. With $P$ for the longer list length and $s$ for the skip gap:

$$s=\lceil \sqrt{P}\rceil$$

Here $P$ is a count and $s$ is a count of entries between skips. The worked class list held about 16 entries, so the gap was 4. Each 4th entry carried a forward pointer. Place skips on the longer list and probe with the shorter list. When both lists share the same length, either list can carry the skips after sorting.

4.7.2 Worked Intersection With Matches 3, 5, 89, 97 and 100

The longer list held 16 IDs and the shorter list held 8 IDs. Plain merge would need up to 24 head-to-head checks, since $16+8=24$. In symbols:

$$T=O(16+8)=O(24)$$

Here $T$ is check count. Skips cut that count.

4.7.3 Skip Pseudocode Shape

The skip merge matches plain merge except for one block. When the first head is smaller and a skip landing exists, check the landing against the second head. When the landing is still not past the second head, jump. When it would pass, step to the next ID. That guard is the only change. It is the step that keeps the method safe.

The procedure runs like this. Start with both heads at the first entry. At each round, compare heads. On a match, record the ID and step both sides. On a mismatch, test the smaller side for a safe jump. Jump while landings stay at or below the other head, then step once. Repeat until one list runs out. Skips exist only on the original built lists; middle results of a longer query carry no skips.

4.7.4 Small Book Exercise

A second book exercise used 16 entries on one side and 1 entry on the other. Plain merge needs 17 checks. With a gap of 4 from the square root of 16, the target is reached in about 6 checks by hopping 4 by 4. Walk the long list in jumps of 4 while each landing stays at or below the single target ID, then step through the last short band. Readers can replay the hops to see the count drop from 17 to about 6.

4.7.5 Student Questions and Answers

On equal lengths, the next doubt followed.

On the refused jump at 75 against 89, the next doubt followed.

Past the 89 match, the walk continued into fresh doubts.

A last doubt asked what the test truly demands.

Fast ID lists now give way to word order: phrases need more than single terms.

4.8 Phrase Queries and Biword Indexes

4.8.1 Why Single Terms Fail Phrases

A phrase query needs exact order. Stanford University as one school is not the same as the two words Stanford and university spread across a sentence.

Order must enter the index. Without it, distance and sequence carry no weight, and spread-out words pose as phrases. The fix stores word pairs or word positions alongside single terms, so order becomes checkable at query time.

4.8.2 Biword Index

A biword index (an index over neighboring word pairs) stores pairs in order. For I have friends Romans countrymen, the pairs are I have, have friends, friends Romans, Romans countrymen, and so on in sequence. A query for Stanford University then looks up the pair Stanford University, not the two single words. Only texts with the words side by side score.

Longer phrases are cut into pairs and each pair is looked up on its own. The middle pairs can mislead, but the method stays cheap because no position lists are stored.

4.8.3 Extended Biwords With Word Classes

Extended biwords (class-filtered pairs) first label words as nouns, prepositions, and similar classes, then form pairs across classes. Take cost overruns on power plant. After labeling nouns and prepositions, kept pairs look like cost overruns, overruns power, and power plant in simplified bigram shape, shaped by noun and preposition slots. The cross-product across classes keeps more useful pairs and drops some noise. It can lift accuracy over raw pairs because grammatical junk pairs never enter the index.

Think of sorting mail by street before pairing houses. Raw pairs join any two neighbors. Class-filtered pairs join only neighbors from useful streets. The analogy breaks where grammar is fuzzy: wrong labels drop good pairs.

4.8.4 Limits: False Hits and Index Growth

Biwords still return false hits. A query for blue house can match the sky was blue house was dark. The words blue and house sit side by side across a sentence break, but the sense is wrong. That is a false positive from pair matching: adjacency without sentence truth.

Biwords also grow the dictionary. Single-word entries stay, and pair entries are added on top. Pairs such as the sky, sky was, was blue, blue house, house was, and was dark all need space. The index gets much larger for a gain that is only partial. Each new pair is a new key with its own postings, so vocabulary growth multiplies storage.

Picture a bar chart of vocabulary size. The horizontal axis shows index type: single terms, biwords, positional. The vertical axis shows key count. The biword bar towers over the single-term bar. The takeaway is that pairs buy phrase power with vocabulary growth.

Real-world: biwords suit short phrases and fast approximate search where some error is fine. When exact phrase match is a must, positional data is needed instead.

4.8.5 Student Questions and Answers

Exact phrase truth needs full positions, which come next.

4.9 Positional Indexes and Phrase Exercise

4.9.1 What Extra Data Is Stored

What if the index remembered every word place? Then phrase checks become number checks.

A positional index (a term map with per-document positions) stores for each term its total count, then per document the document ID, the in-document count, and the full position list. The spoken sketch for the word numbered 2 listed a total near 3427, then blocks such as 6 hits in the first document at positions 7, 18, 33, 72 and more, 5 hits in the second document at its own positions, and further blocks after. The point is that every hit knows its place: term, document, count, and slot list.

4.9.2 How Phrase Match Uses Adjacency

With positions, a phrase check is a numbers check. Take data seen in document 1 at positions 3 and 10, and science seen in document 1 at positions 4 and 11. In plain words, science sits one slot after data in both spots. In symbols, with $p$ for a position of the first word:

$$pos(science)=pos(data)+1$$

Here $pos$ is a word slot number starting at 1. Pairs 3 with 4 and 10 with 11 both pass. Document 1 is a true hit for data science. No false hit from spread-out words can pass, since spread-out words do not sit in consecutive slots.

Common phrase queries such as data science, data mining, Stanford University, and information retrieval are handled this way with no pair-sense loss. Longer phrases extend the same check: each next word must sit exactly one slot after the last.

4.9.3 Worked Exercise: Fools Rush In

The exercise asked which documents hold fools rush in as three words in a row. Position blocks were read for fools, rush, and in.

4.9.4 Worked Exercise: Angels Fear to Tread

The second phrase was angels fear to tread, a four-word run. Read the four position lists together.

The AND of the two phrase sets keeps document 4. That is the only document holding both fools rush in and angels fear to tread in exact runs.

4.9.5 Student Questions and Answers

Positions settle phrases. The next structure speeds up the dictionary itself.

4.10 Hash Table Dictionaries

4.10.1 What the Dictionary Holds

Every query starts with one question: is this term even in the collection?

A dictionary (the term table for retrieval) maps each term to its document count and its postings. A small money sketch used 20 bytes for terms, 48 bytes for document counts, and 48 bytes for postings. Those byte counts show why memory shape matters once the vocabulary grows. Small per-term costs multiply across hundreds of thousands of terms. For each query, the first job is to check whether each query term exists and then fetch its postings.

4.10.2 How Hash Lookup Works

A hash table (a one-shot address map) stores each term at an address set by a hash function (a rule from word to slot number). A simple classroom sketch takes letter codes such as ASCII codes, sums them, and takes mod 5 or mod 7 to get the slot. Apple might live at slot 005. At search time the same function runs on apple and the code goes straight to 005. Case folding first maps Apple to apple so both meet at one key.

In plain words, one computation finds the term. In symbols, with $t$ for the term, $h$ for the hash function, and $a$ for the address:

$$a=h(t)$$

Here $t$ is a string, $h$ is a function from strings to slot numbers, and $a$ is an integer slot. Until that slot is cleared, no other term takes it. Lookup cost is order one. In symbols, with $T$ for time and $M$ for vocabulary size:

$$T=O(1)$$

Here $T$ is lookup time and $M$ is the count of terms. The cost does not grow with vocabulary size. One hash plus one fetch returns the postings, whether the vocabulary holds ten thousand terms or ten million.

4.10.3 Where Hash Tables Fall Short

Hash tables need exact keys. Pairs such as judgement with and without the middle e, or color in United States spelling against colour in British spelling, live at different slots. A query for one form misses the other. Prefix search fails too. A query for comput with a star should bring compute, computer, computing, and computation, but a hash table has no prefix branch to walk. A query for auto with a star should bring automatic, automobile, autonomous, and more, yet hash slots give no help. Small typos also miss, since one wrong letter hashes far away. When the vocabulary keeps growing, the table must be rebuilt by rehashing, which costs much time and space.

Picture a wall of numbered mailboxes with no street order. Knowing the exact box number reaches a letter in one step. Asking for all boxes on one street fails because the wall keeps no street order. The takeaway is that hashes give speed by giving up order.

Real-world: hash lookup fits exact search where speed is the top goal and queries are clean.

4.10.4 Student Questions and Answers

Ordered trees recover what hashes give up, and they come next.

4.11 Tree Dictionaries: Binary Search Trees and B-Trees

4.11.1 Why Trees Help Retrieval

What if the dictionary kept alphabetical order? Then whole branches could be skipped or read at once.

Trees keep terms in sorted order down branches. That order gives two wins. Prefix and wildcard search become branch walks. Large vocabularies can be searched by skipping whole branches. A school analogy from class makes the point. With the school as root, classes one to five on the left and classes six to ten on the right, a search for tenth-grade marks can skip the full left half. Tree search skips in the same way: one branch choice drops half the vocabulary at once.

4.11.2 Binary Search Tree Walk

A binary search tree (a two-branch sorted tree) sends alphabetically smaller terms left and larger terms right. A class example sent A to M left and N to Z right from the root. Deeper nodes split again, such as A to H left and later letters to M right on one side. To find hygiene, start at the root, go left for the H range, then left again as the range narrows, and keep moving till the word is reached. To find a word on the right side, go right, then right, then left and left as the ranges direct. Each move drops many untouched branches at once. That is why even a large vocabulary can be searched fast and with correct order.

Lookup cost grows with tree height, not in one step. In plain words, cost grows with the log of vocabulary size. In symbols, with $T$ for time and $M$ for term count:

$$T=O(\log M)$$

Here $T$ is lookup time and $M$ is the count of terms. It is slower than hash order one, but it keeps order, prefix search, and wildcard search. Doubling the vocabulary adds only one level, so growth stays gentle.

4.11.3 Skew and the Move to B-Trees

Simple binary trees skew when many terms share early letters. Names starting with S can pile on one side and make that side deep. Search then slows because height grows on one side while the other side sits empty. A B-tree (a multi-branch balanced tree) lifts the two-branch limit. Each node is allowed a range of branches, such as 2 to 4 branches per node. In symbols, with $b$ for branch count of a node:

$$2\le b\le 4$$

Here $b$ is a plain count. One node can guide to several letter bands at once. Height drops, memory for the shape drops, and fewer levels mean quicker fetches. The letter B has no single agreed expansion in class. Bayer from a name, broad, and balanced were all mentioned. Balanced fits the use here, since the goal is to fix skew.

4.11.4 Prefix Search on Trees

Prefix search is a branch read. A query for hyp with a star walks to the hyp branch and reads off hyper, hypothesis, hypertext, hyperlink, and related forms. A query for auto with a star reads automatic, automobile, autonomous, and more from the auto branch. Hash tables cannot do this since they keep no lexical order. Trees keep that order, so the branch holds the answer. One walk plus one branch scan returns the full set, which then feeds the normal inverted index for document lookup.

Real-world: tree dictionaries suit large vocabularies that must be read in sorted order and that need fast prefix and wildcard paths plus richer query steps.

4.11.5 Rebalancing Cost

Trees need care when terms leave. If the only word in the H-to-M band is rare and is removed, that edge and node vanish. A binary tree must then reshape parent and child links or some terms in that band lose their path. That reshape is costly when the dictionary is large and changes often. B-trees soften the pain because the branch count is a range, not a strict two. Imbalance only bites when a node drops below the low end of the range, such as below 2 in a 2-to-4 tree, which happens rarely. Most deletions leave the shape valid with no rebuild.

4.11.6 Student Questions and Answers

On the hygiene walk itself, the next doubt followed.

On the name itself, a last doubt followed.

Trees handle trailing stars well. Leading stars need one more trick.

4.12 Wildcard Queries and Reverse Trees

4.12.1 What Tolerant Retrieval Means

Real queries are messy. That fact, not clean textbook input, drives this whole block.

Tolerant retrieval (search that bears with human slips) drops the hope that every query is typed well. Real queries hold spelling slips, variant spellings, missing parts, and foreign marks. The index must still bring the right texts. Lenses for tolerance are wildcard queries, spelling handling and sound-based fixes, plus accent and variant handling. Wildcards come first because trees already support half of them.

4.12.2 Star Queries

A wildcard query (a query with a star for any tail) uses the star learned from database search, where select all uses a star for all. A query for mon with a star should bring money, monitor, month, monkey, and more such as month forms. In plain words, keep words $w$ that start with mon and sit below moo. In symbols, with $w$ for a dictionary word:

$$mon\le w<moo$$

Here $w$ is a string and the bounds are strings in lexical order. The upper bound moo comes from stepping the last prefix letter one step forward, from n to o, which closes the mon band tightly. The wanted words money, monitor, month, and monkey pass. Motor and moon do not pass, since they sit outside the band: motor breaks at the third letter and moon breaks at the second.

Spelling pairs such as Sydney variants, color against colour, and judicial against judiciary show why stars help. When the exact stored form is unsure, a shaped star such as sydney with a star inside, judicia with a star at the end, or color variants can still pull both forms. Foreign-name queries such as a university name with an unsure middle work the same way.

4.12.3 Trailing Stars Are Easy, Leading Stars Need Help

Trailing stars fit B-trees well because the tree is already in lexical order. Walk to mon and read the branch. Leading stars do not fit. A query for words ending in mon, such as common and lemon, has no shared front branch to walk, since the shared letters sit at the tail.

The fix is a reverse B-tree (a tree over reversed spellings). Lemon is stored backwards in reversed letters, and common is stored backwards in the same reversed way. A leading-star query is then flipped to a trailing-star query on the reversed tree: reverse the pattern, walk the reversed tree, read the branch. Search becomes a normal branch read again, only backwards. Queries with a star in the middle split the work: the front part walks the normal tree, the tail part walks the reversed tree, and the two sets meet in an AND.

4.12.4 Student Questions and Answers

One star in any spot still needs many structures. The next index folds every star shape into one lookup.

4.13 Permuterm Index With Rotations

4.13.1 The End-Marker Idea

What if every star shape became a trailing star? Then one lookup shape would cover all queries.

A permuterm index (a rotation index for wildcards) adds an end-marker to each word and stores all rotations of that marked word. The marker was spoken as dollar in class and is written here in words only to keep the text plain. Start with hello with the marker at the end. Then move the first letter to the end, step by step, till the marker moves round the full circle. The rotation set reads: hello followed by the marker, ello followed by the marker plus h, llo followed by the marker plus he, lo followed by the marker plus hel, o followed by the marker plus hell, and the marker followed by hello. All six forms enter the rotation vocabulary, one per letter plus one for the marker. The count of stored forms grows with word length, so longer words cost more rows.

4.13.2 How Rotations Turn Any Star Into a Trailing Star

The rotation set lets any star query become a trailing-star query. Take a shape such as m with a star then n. Rotate the query so the star sits at the end, giving n with the marker plus m plus a trailing star. Look up that rotated prefix in the rotation vocabulary with a trailing star. The hits point back to source words whose rotation matches, such as man and moron for that shape. Leading stars, trailing stars, and middle stars all map to one trailing lookup this way. That single-shape lookup is the whole point of the rotation build. Queries with two stars need an extra filter pass: look up the first star shape, then check each candidate for the middle string, keeping hits like fishmonger and dropping misses like filibuster for a shape with mo in the middle.

The price is dictionary size. Every term contributes as many rotations as it has characters plus one, so the rotation vocabulary dwarfs the source vocabulary. The index links each rotation back to its source term, and source terms then feed the normal inverted index for document lookup.

Class closed at this point, with the next session set to start from the permuterm index and move on.

4.13.3 Student Questions and Answers

That rotation trick closes the lecture arc from word forms to tolerant lookup.

Exam Guidance Summary

Stemming questions reward the guard first and the cut second.

Skip questions start with placement and continue with a hand-counted walk.

Implementation understanding beats memorized code lines.

Phrase answers live or die on slot numbers.

Wider context rounds out the marks.

• Exam note: a discussion task asks for recent stemming and lemmatization methods and how they beat the classroom methods. Join that thread since it helps with NLP preprocessing choices. Compare on speed, match quality, and language coverage.
• Exam note: hash cost is order one for exact lookup. Tree cost is order log M for M terms. Trees add prefix and wildcard power at that extra cost. State both costs with the trade between them.

Key Industry Applications

Production search stacks combine every step of this lecture. Stop-word handling, normalization, tokenization, lowercasing, and stemming or lemmatization run in order on web scale. Accent handling folds variants such as resume forms to shared keys. Compound splitting breaks long German-style compounds into searchable parts. Number handling maps alternate digit forms together. Google-style pipelines use all of these because each step removes one class of mismatch between queries and documents.

WordNet from NLTK gives a common lemmatizer baseline in Python. Teams start there to get sense-aware base forms with little setup. SpaCy ships a lemmatizer used in many pipelines where speed and pipeline fit matter more. Stanford tools and TextBlob give more lemmatizer options to test when accuracy or language coverage needs a check.

Snowball supports many languages for stemming where Porter is English-only. Mixed-language collections pick per-language Snowball tables instead of forcing English rules everywhere.

Prefix search such as auto with a star powers type-ahead and database-style wildcard find. Each keystroke walks one level deeper and reads the branch below. The SQL-style star for all motivates the wildcard star habit that users bring from databases.

Positional indexes power exact phrase search such as data science and Stanford University without false hits. Legal, news, and academic search pay the position storage cost because a wrong phrase hit costs more than the space. Biword indexes power fast approximate phrase match where some false hits are fine, such as quick first-pass retrieval before a careful rerank.

Skip pointers speed AND merges over long sorted postings in production indexes. Long static lists carry pre-built jumps, and the merge guard keeps every jump safe at query time.