Information Retrieval

Tolerant Retrieval: Wildcard Queries and Spelling Correction

Published: 2026-09-14

Level: postgraduate

Audience: Postgraduate students in Information Retrieval

This lecture builds tolerant lookup step by step: wildcard trees for edge stars, permuterm rotation and k-gram slices for middle stars and rough typing, phrase indexes for exact order, edit grids with weights for spelling, Jaccard screens for speed, Soundex buckets for sound, and gene strings as a living use case. Each method pairs a fast first net with a strict second check.

5.1 Trailing and Leading Wildcard Search with Trees

5.1.1 Why wildcard search matters

A wildcard query is a search pattern where one symbol stands for unknown letters. We write that symbol as a star. A star can stand for no letter, one letter, or many letters. The need arises when spelling is unsure or word forms vary. One typical case is a user who remembers the start of a word but not the end. Another case is a set of word forms that share a stem. The same idea powers fast lookup in database filters and search boxes. The goal is to return every vocabulary term that fits the pattern without scanning the whole vocabulary one by one.

Think of a reader who wants every book about automatons but cannot recall if the catalog uses automatic, automation, or automated. A single pattern automat followed by a star asks for all three at once. That is the hook for this whole lecture: one short pattern stands in for a whole family of words.

Think of it like a shelf of sorted cards. When the start of the word is known, we can skip whole groups of cards at once. That skipping is where trees help. A tree groups words by shared prefixes. We walk down one path and ignore other paths entirely. That pruning keeps search fast even when the vocabulary is large.

A shelf of sorted cards shows skipping whole groups at once. Picture index cards sorted from A to Z in a long drawer. If you want every card starting with MON, you flip straight to MO, then to MON, and you lift out that whole block. You never look at cards under A, B, or Z. A search tree is that drawer with a map: each branch tells you which block to open next, so most of the vocabulary is never touched. The analogy breaks at one point: cards sit in one flat order, while a tree shares prefix paths, so words like money, monitor, and month share the MON trunk and split only at the fourth letter.

A vocabulary term, written $t$ , is one distinct word stored in the dictionary. A wildcard pattern, written $P$ , is a string of known letters plus one star. A match means every known letter of $P$ lines up with $t$ in order, while the star absorbs zero or more letters. The task is to list the set $W = {t : t fits P}$ without testing each $t$ one by one.

Picture the tree as a road map. The horizontal axis is depth, meaning how many letters have been fixed. The vertical spread is the fan of branches at each depth. The MON path is one narrow road from the root through M, then MO, then MON. All matching words sit in the subtree below that point, like houses past one junction. The takeaway is direct: fixing three letters prunes away nearly the whole map, leaving one small block to list.

5.1.2 Trailing star with BST and B-tree

A BST, or binary search tree, is a tree where each node has up to two child branches, left and right. The rule for going left or right depends on sort order. A B-tree, or balanced tree, is a wider tree where each node can hold a range of children, for example 2 to 24 or any set range. The wider range keeps the tree balanced for longer.

When the star is at the end, search is direct. Take a pattern such as $M O N$ followed by a star. The verbal form in class was MON star. The fixed part is $M$ , $O$ , $N$ in order. We start at the tree root and follow $M$ , then $M O$ , then $M O N$ . Every term under that branch matches. We do not visit branches that start with other letters. That single-sided walk is the source of speed.

A trailing wildcard query has the form $P = X$ followed by a star, where $X$ is a fixed prefix such as $M O N$ . Lookup walks the path for $X$ and then enumerates the full subtree $W (X)$ . If $M$ is the count of stored terms, the walk costs about $lo g M$ steps to reach $X$ , plus time to list $W (X)$ . Scanning the whole vocabulary would cost about $M$ steps, so the saving is large when $W (X)$ is small.

Worked trailing lookup for MON star. Fixed part is $X = M O N$ . Step 1: at the root, take the branch for $M$ and drop A through L and O through Z. Step 2: under M, take $O$ and drop MA through MN and MP through MZ. Step 3: under MO, take $N$ and drop MOA through MOM and MOO through MOZ. The subtree holds money, monitor, month, monkey, and monsoon. Each starts with $M O N$ in order, so each fits MON star. A word like moon does not sit under MON, since its third letter is $O$ , not $N$ , so it is never visited. Final answer is the listed MON block, found with three branch choices. Sense-check: three letters fixed means only words with those three first letters can match, so the collected block is both complete and tight.

A BST can become slow when it turns lopsided. If one branch is removed or if inserts arrive in sorted order, one side grows long and thin. The tree then behaves like a list. Repair means rebuilding large parts of the tree from scratch. That rebuild costs time and effort. A B-tree softens this problem. Because each node allows a range of children, small changes stay inside the allowed range. We keep the current shape as long as counts stay within bounds. Rebuilds happen far less often. That tolerance is the main gain of a B-tree over a BST for this task.

The contrast is worth pinning down. A BST node holds one key and two children, so balance is brittle: one bad run of inserts makes a chain. A B-tree node holds many keys and a range of children, say between $a$ and $b$ children with $2 \leq a \leq b$ , so small inserts and deletes fit inside a node without reshaping the tree. On disk this matters even more, since each B-tree node maps to one block read, and fewer levels mean fewer reads.

Scope: Trailing-star tree search fits when the star is last and the fixed prefix has at least one letter. Assumption: Terms share a sort order, so prefix grouping is sound. When the pattern is only a star with no fixed letters, the tree gives no pruning, since every term matches. When inserts and deletes are heavy, a plain BST degrades toward list scan, so a B-tree is the safer pick.

Pitfall: New readers often treat the star as one letter only. Here it absorbs any run, including the empty run, so MON star also fits MON itself. A second trap is listing only the first few hits under MON and stopping early. The task asks for the full subtree, so every term below the MON node must be collected.

Real-world: the same trailing-star idea appears in SQL-style filters such as select with a star for all columns, and in type-ahead search where each new letter narrows one tree path. Type-ahead is the daily face of this method: each keystroke extends $X$ by one letter and shrinks $W (X)$ at once.

5.1.3 Leading star with a reversed tree

A leading star puts the unknown part first, for example a star followed by $M O N$ . The verbal form was star MON. A plain prefix tree cannot help here because the known part sits at the end. The fix keeps the rule that the star must end up at the end. We change the index, not the intent of the query.

Ask how to find every word ending in MON when the tree only groups by starting letters. The answer is to flip the problem: store every word backwards, so endings become beginnings. That flip turns a hard suffix hunt into the easy prefix walk already solved above.

We build a second tree where every word is stored reversed. The word $M O N$ becomes $N O M$ in that reversed tree. The query is reversed in the same way. A leading-star query for words ending in $M O N$ becomes a trailing-star query for words starting with $N O M$ in the reversed tree. We then walk the reversed tree exactly as in the trailing-star case and collect all words under the $N$ , $O$ , $M$ path. Each hit is flipped back to normal spelling before display.

Worked leading lookup for star MON. Normal words lemon, demon, and salmon all end in $M O N$ . Step 1: reverse each stored word, so lemon is stored as $N O M E L$ , demon as $N O M E D$ , salmon as $N O M L A S$ . Step 2: reverse the known part $M O N$ to $N O M$ and treat the query as $N O M$ star on the reversed tree. Step 3: walk $N$ , then $N O$ , then $N O M$ and list the subtree. It holds the three reversed forms. Step 4: flip each hit back, giving lemon, demon, and salmon. A word like money starts with MON but ends with $N E Y$ , so its reversed form starts with $Y E N$ and never enters the NOM block. Sense-check: reversing twice returns the start word, so no spelling is lost in the round trip.

The key habit to keep: wherever the star starts, move work so the star ends up last. Trailing search uses the normal tree. Leading search uses the reversed tree. Middle patterns need stronger tools, which come next.

Recap: Trailing star walks one prefix path and lists its subtree; leading star does the same walk on a reversed tree with reversed spellings like $N O M$ . Bridge: Both handle only a star at one edge. A star in the middle, such as $m$ star $n$ , needs the rotated index of 5.2, which generalizes the flip trick used here.

5.2 Permuterm Index for General Wildcard Queries

5.2.1 The two-pass idea with a Boolean superset

A permuterm index is a rotated index that turns any star position into a trailing-star lookup. The method handles stars in the middle, which plain trees cannot. The core idea runs in two passes.

How do you answer $m$ star $n$ when no prefix tree groups by both a start and an end at once? The trick is to spin each word so the unknown middle moves to the end, then use the trailing-star walk from 5.1. That spin-then-search pair is the whole permuterm idea.

First we express the wildcard query $Q W$ as a simpler Boolean query $Q$ . The verbal form was: express the given wildcard query as a Boolean query. The Boolean query uses $A N D$ between small parts. The merge of posting lists for those parts returns a superset. A superset here means a larger set that holds every true answer plus some extra terms. Then we test each term in that superset against the true pattern $Q W$ and drop the ones that do not fit. What remains is the exact answer set.

In symbols, let $Q W$ be the wildcard pattern and let $q_{1}, q_{2}, q_{3}$ be its parts. For the MON star case we build $Q = (q_{1} \land q_{2} \land q_{3})$ where each $q_{i}$ is one part, $\land$ means Boolean AND, and $q_{1}$ marks word start with a dollar sign. Here the dollar sign, written as $$$ , is a special end marker, not money. The verbal description stays with the formula so the source of each part stays audit-ready. The superset returned by $Q$ might hold $m o n ey$ , $m o ni t or$ , $m o n t h$ , and also $m oo n$ . The second pass keeps $m o n ey$ , $m o ni t or$ , and $m o n t h$ and drops $m oo n$ because $m oo n$ does not match MON star. That check-then-drop step is mandatory. Without it, extra terms linger as false hits.

A Boolean superset query $Q$ is the AND of rotated parts derived from $Q W$ . Let posting list $L (q_{i})$ hold stored rotations starting with part $q_{i}$ . Then the round-one set is $C = L (q_{1}) \cap L (q_{2}) \cap L (q_{3})$ , where $\cap$ is set intersect. Every true fit of $Q W$ lies in $C$ , but $C$ may hold extras. Round two tests each $t \in C$ letter by letter against $Q W$ and keeps only exact fits. Star must end up last, so the index changes instead of query intent: we rotate the stored words and the query rather than bending what the star means.

Worked superset for MON star. Parts are start marker plus $M$ , plus $M O$ , plus $M O N$ . Round one pulls posting lists for each part and ANDs them. The merged set holds money, monitor, month, and moon, since each shares some MON slices. Round two tests each word against MON star letter by letter. Money starts with $M$ , $O$ , $N$ in order, so it stays. Monitor and month pass the same test. Moon has $M$ , $O$ , $O$ at the start, so its third letter breaks the demand and it is dropped. Final answer is money, monitor, and month. Sense-check: round one is wide by design and round two only removes, so the final set cannot miss a true MON word.

Picture the flow as a funnel. The wide top is the full vocabulary. The middle is the superset $C$ , much smaller but still loose. The narrow spout is the filtered answer, exact but no larger than $C$ . The takeaway is that speed comes from the funnel shape: the costly letter-by-letter test runs only on $C$ , never on the whole vocabulary.

5.2.2 How rotation with a dollar marker works

A rotation here means cycling letters of a word so each position takes a turn at the front. We first add $$$ , the dollar marker, at the end of each word. Then we rotate step by step until $$$ reaches the front. For the word $h e l l o$ , the verbal walk was: add dollar at the end, then rotate H to the end, then E, and so on. The full set is $h e l l o$ with dollar at the end, then $e l l o$ with dollar plus $h$ , then $l l o$ with dollar plus $h e$ , then $l o$ with dollar plus $h e l$ , then $o$ with dollar plus $h e l l$ , then dollar plus $h e l l o$ . We write one member as $h e l l o $$ , where $$$ marks the end, and the next as $e l l o $ h$ , where $h \in Σ$ is the moved first letter from alphabet $Σ$ . Here $Σ$ is the set of allowed letters, $h$ is a single letter in that set, and $$ \in / Σ$ is a marker outside the alphabet. Each rotation keeps all letters. Only the split point moves.

A permuterm rotation of word $w = c_{1} c_{2} \dots c_{n}$ is each cyclic shift of the padded string $w $$ . For $h e l l o$ the six rotations are $h e l l o $$ , $e l l o $ h$ , $l l o $ h e$ , $l o $ h e l$ , $o $ h e l l$ , and $$ h e l l o$ . Each rotation links back to the source word $h e l l o$ . The dollar marker records word start and end while the star drives the match: without $$$ , a rotated match could not tell a word start from a word middle. Rotation with a dollar marker turns any single-star pattern into a prefix lookup by spinning the pattern until the star sits last.

Rotation helps because it moves the fixed text before the star to the front. Take the pattern $m$ star $n$ . The verbal form was m star n. We first attach the marker to get dollar, $m$ , star, $n$ . Then we rotate until the star sits last. One rotation gives $n$ dollar $m$ star. The verbal form was n dollar m star. That rotated string is now a prefix search. We look for stored rotations that start with $n$ dollar $m$ . Words such as $man$ , $m or o n$ , and $m o n soo n$ were named as possible hits in class. Each of those has $m$ at the start and $n$ later, with varied middle text. The star at the end absorbs that middle text.

Worked rotation for m star n with hello as the spin model. For hello, list $h e l l o $$ , then move $h$ to the end to get $e l l o $ h$ , then move $e$ to get $l l o $ h e$ , and repeat to $$ h e l l o$ . Each of the six keeps all five letters plus $$$ . For m star n, pad to $$ m$ star $n$ , then spin to $n $ m$ star. Lookup finds rotations starting with $n $ m$ . The word man contributes rotation $n $ ma$ , which has prefix $n $ m$ , so man is kept. Moron and monsoon pass the same prefix test. A word like moon gives rotations such as $o n $ m o$ and $$ m oo n$ , none of which starts with $n $ m$ , so it is dropped. Sense-check: each rotation keeps letter count fixed, so a missing or extra letter signals a bad spin at once.

Scope: Permuterm fits single-star patterns of any shape: trailing, leading, or middle. Assumption: One fixed $$ \in / Σ$ marks edges, and every rotation of every term is stored. With two or more stars, one rotation cannot put both stars last, so the method splits the pattern into parts and ANDs them, which widens the superset and leans harder on round-two filtering.

5.2.3 Student Questions and Answers

Q: Can one star stand for many letters, or only one letter? A: One star can stand for many letters. In the S star NG demo the only fixed demands were first letter S and last letters NG. Any middle text of any length was allowed, so sing, song, string, and strong all fit the same pattern. The length of the middle run never matters; only the S start and the NG end are tested.

Q: Why add a dollar marker at all, since search effort goes to the star? A: The dollar marker records where the word starts and ends. The star still drives the match, but the marker lets rotation keep start and end facts intact. Without it, a middle match could not tell start from middle. A pattern like S star NG must know which S is the word start, and only $$$ carries that fact through the spin.

5.2.4 Worked classroom exercise with mama and S star NG

Take the word $mama$ as a rotation drill. First add the dollar marker to get $mama$ with dollar at the end. Then rotate each letter in turn. The set reads $mama$ with dollar at the end, then $ama$ with dollar plus $m$ , then $ma$ with dollar plus $ma$ , then $a$ with dollar plus $mam$ , then dollar plus $mama$ . Here each member keeps all four letters plus the marker, and only the split point moves. A test may ask for just this list with no star involved, since the point is pure rotation skill.

In compact symbols the mama set is $mama $$ , $ama $ m$ , $ma $ ma$ , $a $ mam$ , $$ mama$ . Count check: a four-letter word plus $$$ gives five rotations, one per split point, so five members means none is missed. That count trick catches a dropped rotation fast in a test.

Now take the pattern $S$ star $N G$ as a lookup drill. The verbal form was S star NG. The demand is plain: the word must start with $S$ and end with $N G$ , with any middle text allowed. Sample fits named in class were $s in g$ , $so n g$ , $s t r in g$ , and $s t r o n g$ . First add the marker and rotate the pattern until the star sits last. The rotated key becomes $N G$ dollar $S$ star. The verbal form was NG dollar S star. That key is a prefix search: find stored rotations that start with $N G$ dollar $S$ .

Build the same rotations for each stored word. For $s in g$ , the set is $s in g$ with dollar at the end, then $in g$ with dollar plus $s$ , then $n g$ with dollar plus $s i$ , then $g$ with dollar plus $s in$ , then dollar plus $s in g$ . The member $n g$ with dollar plus $s i$ starts with the key $N G$ dollar $S$ , so $s in g$ is kept. For $so n g$ , the set is $so n g$ with dollar at the end, then $o n g$ with dollar plus $s$ , then $n g$ with dollar plus $so$ , then $g$ with dollar plus $so n$ , then dollar plus $so n g$ . The member $n g$ with dollar plus $so$ matches the same key, so $so n g$ is kept. For a word such as $u s in g$ , spelled $U$ $S$ $I$ $N$ $G$ , rotations include $n g$ with dollar plus $u s i$ . That member starts with $N G$ dollar $U$ , not $N G$ dollar $S$ , so $u s in g$ is dropped. Exact string match on the rotated key decides each word. Keep matches, drop the rest.

Worked S star NG filter. Rotated key is $N G $ S$ star. Candidate sing offers $n g $ s i$ , which starts with $N G $ S$ , so keep sing. Candidate song offers $n g $ so$ , same prefix, so keep song. Candidate using offers $n g $ u s i$ , whose third symbol is $U$ , not $S$ , so drop using. String and strong pass the same way, since each starts with $S$ and ends with $N G$ . Final kept set is sing, song, string, and strong. Sense-check: the key fixes the last two letters and the first letter, so any kept word must show that S start and NG end.

Pitfall: Two slips recur. One is spinning the pattern the wrong way so the star lands first instead of last; always spin until the star is the final symbol. The other is forgetting that $$$ is a real indexed symbol, so NG dollar S star must match the dollar slot too, not just N, G, and S.

Exam note: Expect a rotation task where a short word must be expanded into all rotated forms, and a query rotation where the star must be moved to the end before lookup. For mama write all five rotations with the dollar walk. For S star NG use NG dollar S star as the key and show sing and song as hits with using as a reject.

Recap: Permuterm rotation with a dollar marker turns each single-star pattern into a trailing-star prefix hunt, and the Boolean superset plus filter pass keeps answers exact. Bridge: When patterns have splits on both sides or typing is rough, the slice-and-intersect k-gram net of 5.3 offers a wider but costlier alternative.

5.3 K-Gram Index for Wildcard Queries

5.3.1 What a k-gram is

A k-gram is a short slice of a word with fixed length $k$ . Here $k \in {2, 3, 4}$ is the slice length, often 2 or 3, picked by trial on the data. A bigram means $k = 2$ . A trigram means $k = 3$ . We add a dollar marker at the start and at the end to record word edges. Then we slide a window of length $k$ across the padded word and store each slice.

Why slice words into overlapping chips at all? Because a wildcard or a typo breaks only a few chips while most survive. If enough chips still match, the word is worth a closer look. Slices turn fuzzy sameness into countable overlap.

For the word $c a s tl e$ with $k = 3$ , the verbal demo built slices such as dollar plus $C$ plus $A$ , then $C$ plus $A$ plus $S$ , then $A$ plus $S$ plus $T$ , and so on until $L$ plus $E$ plus dollar. Here $C, A, S, T, L, E$ are single letters, dollar marks an edge, and each trigram is one window position. The dollar at the start tells that the slice touches the word start. The dollar at the end tells that the slice touches the word end. The value of $k$ is not fixed by theory. It comes from tests on the data at hand. Short $k$ gives more hits and larger lists. Long $k$ gives fewer hits and shorter lists.

A k-gram of length $k$ is each length- $k$ window over the padded form $$ w $$ . For $w = c a s tl e$ with $k = 3$ , the windows are $$ C A$ , $C A S$ , $A S T$ , $S T L$ , $T L E$ , and $L E $$ . Each distinct slice points to a posting list of words holding it. The choice of $k$ trades list length against build size: $k = 2$ gives few distinct slices with long lists, while $k = 3$ gives many distinct slices with short lists.

Picture a word as a strip of tiles with a dollar cap on each end. A length- $k$ frame slides one tile at a time, and each frame position is one stored slice. For castle with $k = 3$ the frame stops six times, so six trigrams are stored. The takeaway is that edge caps make start and end slices distinct from middle slices, which is what lets later filters respect word edges.

5.3.2 Worked k-gram build for MON

Take the fixed part $M O N$ as a bigram demo with $k = 2$ . The verbal steps were: add dollar at the start, add dollar at the end, then list all length-two slices. The set is dollar plus $M$ , then $M$ plus $O$ , then $O$ plus $N$ , then $N$ plus dollar. We write the first as $$ M$ , where $$$ is the start marker and $M$ is the first letter, the next as $M O$ , where both are plain letters, the next as $O N$ , and the last as $N $$ , where $$$ is the end marker. The class checked coverage by asking if any slice was missed. All four cover the padded string with no gaps.

Padded form is $$ M O N $$ , which has length 5. A bigram window over length 5 stops $5 - 2 + 1 = 4$ times, so four slices means full coverage. That count check, padded length minus $k$ plus one, confirms no slice was skipped.

Each slice has its own posting list of vocabulary words. For $$ M$ , the list holds words that start with $M$ , such as $ma z e$ , $ma g i c$ , and $ma d$ . For $M O$ without a start marker, the list holds words where $M$ followed by $O$ sits anywhere inside, such as $am o n g$ , $s m o k e$ , and $am o u n t$ . For $O N$ , the list holds words where $O$ followed by $N$ sits inside, such as $a l o n g$ and again $am o n g$ . The dollar makes the contrast sharp: $$ M$ forces word start, while $M O$ allows word middle.

Worked bigram posting pull for MON. Slice $$ M$ pulls maze, magic, and mad, plus every other M-start word. Slice $M O$ pulls among, smoke, and amount, since each holds $M O$ inside. Slice $O N$ pulls along and among. Slice $N $$ pulls only words ending in $N$ . Intersect of the four lists keeps words holding all four slices at once, which is the MON core. A word like mad holds $$ M$ but lacks $M O$ , $O N$ , and $N $$ , so it drops at the AND step. A word like among holds $M O$ and $O N$ but lacks $$ M$ , so it drops too. Sense-check: only words with M at the start and the MON run inside can hold all four slices, so survivors always look MON-like.

5.3.3 Intersect by AND to form the superset

Once each slice list is in hand, we combine them with Boolean AND. The verbal form was bullion operation, meaning Boolean operation, done as intersect or merge. In symbols, let $L_{1}, L_{2}, L_{3}, L_{4}$ be the four posting lists for $$ M$ , $M O$ , $O N$ , and $N $$ . The combined set is $C = (L_{1} \cap L_{2} \cap L_{3} \cap L_{4})$ where $\cap$ means set intersect and each $L_{i}$ is a set of words. Only words present in all four lists stay in $C$ . That merged set is the superset for $M O N$ . It is large by design. The second pass then tests each member against the true MON star pattern and drops mismatches.

A k-gram superset is the AND of posting lists for the query slices. With $L_{i}$ as the list for slice $i$ , the round-one set is $C = ⋂_{i} L_{i}$ . Merging runs like a multi-way zip over sorted lists, keeping only shared ids. $C$ is a Boolean superset: it holds every true MON star fit plus extras such as words with the slices in the wrong order. A final letter-by-letter test against MON star removes those extras.

The price is upkeep. Each distinct k-gram needs its own stored list. When a new word enters the vocabulary, every k-gram inside it must be added to the store. When words leave, lists must be pruned. For a large vocabulary that store is wide. Search itself is fast, but build and update cost is real. That trade shapes the choice between methods.

Scope: K-gram search fits rough patterns, single typos, and short fixed runs like MON where slice overlap is a good screen. Assumption: $k$ is fixed before indexing and edge dollars are stored. Tiny $k = 2$ over-generates with big AND inputs, while $k = 4$ under-generates on short words, so $k = 2$ or $k = 3$ is the usual middle ground from data trials.

Pitfall: Readers often treat the bigram intersect as the final answer. It is only the superset. Skipping the letter-by-letter check leaves words like among or smoke in the answer when they merely share slices. Always run the second pass.

Real-world: k-gram slices power fuzzy word lookup in editors and catalog search, where a typed fragment must still pull near words fast. The same slice lists double as the cheap screen before spelling grids in 5.10, so one build serves two tasks.

Recap: Castle trigram slices and MON bigram lists with maze, magic, among, and smoke show the slice-then-intersect shape: postings per slice, Boolean AND into a superset, then exact filtering. Bridge: Phrase search in 5.4 reuses the same AND-then-check shape, but over word positions instead of letter slices.

5.4 Biword and Positional Indexes for Phrase Search

5.4.1 Biword versus positional in plain terms

A biword is a pair of back-to-back words treated as one token. A biword index stores those pairs. A positional index stores far more: for each term it keeps the document id, the count in that document, and the exact word positions. Here a document id $d \in D$ names one document in collection $D$ , a term $t$ is one vocabulary word, and a position $p \in N$ is the word slot inside the document. The verbal claim repeated in class was that positional search gives more exact phrase answers than biword search, at the cost of a heavier build.

Why keep two phrase tools instead of one? Because speed and exactness pull apart. Pairs are small and fast but blind to order gaps, while positions are bulky but see every gap. The lecture uses both to show what cheap buys and what exact costs.

Biword search feels strong because many common phrases do occur as fixed pairs, such as $d a t a$ $minin g$ , $d a t a$ $sc i e n ce$ , and $in f or ma t i o n$ $r e t r i e v a l$ . For those pairs the pair token hits at once. But many phrase hits are missed when pairs are rare or when wording shifts slightly. Positional search does not rely on pair rarity. It pulls candidate documents for each single word, then checks whether positions line up back-to-back. That extra check removes many false hits.

A biword token is the glued pair $(w_{i}, w_{i + 1})$ , indexed as one key. A positional posting for term $t$ in document $d$ is the list $[p_{1}, p_{2}, \dots]$ of slots where $t$ occurs. A phrase $w_{1} w_{2}$ fits $d$ when some $p$ has $w_{1}$ at $p$ and $w_{2}$ at $p + 1$ . That consecutive test, $p os (w_{2}) = p os (w_{1}) + 1$ , is the positional adjacency rule. Biword lookup is one key fetch; positional lookup is two fetches plus a list merge with plus-one tests.

A side-by-side contrast pins down when to pick which. Biword build is small, since it stores one pair token per adjacent pair. Positional build is large, since it stores every slot of every term. Biword answers are loose, with false positives when words co-occur apart. Positional answers are strict, since each hit proves adjacency. Pick biword when speed and size matter and a few extras are fine. Pick positional when order must be proved.

5.4.2 Worked phrase demo with four short documents

The class used four short sentences as stand-in documents. The first phrase query was $q u i c k$ $b r o w n$ . The verbal result was documents 1 and 3. Both hold the two words side by side, so biword and positional agree there. No error arises in that case.

The second phrase query was $b r o w n$ $f o x$ . The biword path returned documents 1, 2, 3, and 4. Document 3 was the problem. It holds $b r o w n$ and $f o x$ but not side by side. The pair token still fired because the pair exists somewhere in its pair list, or the single words co-occur without adjacency. That is a false positive: a returned item that looks right but breaks the phrase demand. The positional path drops document 3. It sees positions for $b r o w n$ and $f o x$ in document 3, notes they are not consecutive, and rejects it. False positive warning when brown and fox occur apart is the lesson to carry: co-occurrence alone never proves a phrase.

Worked brown fox filter over four documents. Query is $b r o w n$ $f o x$ with demand $p os (f o x) = p os (b r o w n) + 1$ . Document 1 has brown at 2 and fox at 3, so $3 = 2 + 1$ and it stays. Document 2 has the pair in order elsewhere, so it stays. Document 3 has brown at 2 and fox at 9, so $9 \neq = 2 + 1$ and it drops under positional rules, though biword keeps it. Document 4 passes the same plus-one test. Final biword set is 1, 2, 3, 4 while positional set is 1, 2, 4. Quick brown fox as a three-word phrase narrows further to document 1 only, since document 3 holds quick brown in one spot and fox elsewhere. Sense-check: any kept document must show the two words in touching slots, so a gap of even one slot forces a drop.

The third phrase query was $q u i c k$ $b r o w n$ $f o x$ as one three-word phrase. Only document 1 holds all three in a row. Document 3 holds $q u i c k$ $b r o w n$ in one spot and $f o x$ elsewhere. Positional search returns only document 1. Biword search is less strict and can still pull document 3 through its pairs. The pattern is stable: biword is cheaper to build and fine when some extra hits are okay, while positional is stricter and better when exact order matters.

A second worked case used the phrase $t o$ $b e$ $t o$ $b e$ and the line $f oo l s$ $r u s h$ $in$ . The verbal positions for the second were 36, 37, and 38 in document 247. Here 36, 37, 38 $\in N$ are word slots, $f oo l s$ sits at 36, $r u s h$ at 37, and $in$ at 38. Because each step adds one, the three words form one unbroken phrase. A query for $t o$ $b e$ with no adjacent slots in a document fails that plus-one test and is rejected, even though both words occur alone.

Worked fools rush in check. Postings give fools at 36, rush at 37, and in at 38 in document 247. Test one: $37 = 36 + 1$ , so fools rush holds. Test two: $38 = 37 + 1$ , so rush in holds. Both links pass, so the three-word phrase fits document 247. A rival document with fools at 36, rush at 40, and in at 41 fails the first link and drops, even though all three words occur. Final answer is only documents with an unbroken plus-one chain. Sense-check: a three-word phrase needs two passing links, so one gap anywhere breaks the whole phrase.

Picture positions as numbered seats in a row. A phrase is a party that must sit in touching seats with no gaps. Biword search checks that each neighboring pair once sat together somewhere, while positional search checks seat numbers in this document. The takeaway is that seat numbers prove togetherness, while pair memory alone does not.

5.4.3 Student Questions and Answers

Q: Document 3 does hold brown and fox, so why call it a false positive when no positions were asked for? A: A phrase query always demands adjacency. Brown and fox must sit in consecutive slots, such as $p$ and $p + 1$ where $p$ is the slot of brown. In document 3 the slots are apart, so it breaks the phrase demand even though both words occur. Holding both words is needed but not enough; touching slots are the extra demand that phrases add.

Scope: Biword fits frequent pairs and quick hints; positional fits exact phrases and order tests. Assumption: Token order matches reading order and slots count every word, including small stop words, so plus-one math stays aligned. If stop words are dropped at index time, slot numbers shift and phrase tests need matching rules at query time.

Exam note: Expect a small phrase task with two or three short documents where biword pulls an extra document and positional drops it. Show position numbers and the plus-one check. For brown fox mark document 3 as the biword false positive, and for fools rush in cite 36, 37, 38 in document 247 as the passing chain.

Recap: Biword pairs give cheap loose phrase hints like data mining, while positional slots with the consecutive $p$ and $p + 1$ test prove exact phrases like quick brown fox. Bridge: Both feed the same two-pass moral as permuterm and k-gram: a wide first net plus a strict second check, which 5.5 states as the shared shape.

5.5 Two-Pass Retrieval and False Positives in Tolerant Search

5.5.1 The shared shape of permuterm and k-gram search

Both permuterm and k-gram search share one shape. Pass one builds a wide superset with an index. Pass two filters that superset against the true pattern. The verbal line was that both methods take two rounds: derive the superset, then filter. Without round two, false positives stay in the answer.

Why accept a sloppy first pass at all? Because exact tests are costly and the vocabulary is huge. A cheap index quickly drops 99 percent of words, leaving a small pile where careful letter checks are affordable. Loose first, strict second is a speed plan, not laziness.

For permuterm search, round one rotates the query so the star sits last, then takes all stored rotations with that prefix. For k-gram search, round one breaks the query into k-grams, pulls each slice list, and ANDs them. In both cases the round-one set is too big on purpose. Round two reads each candidate word letter by letter and keeps only true fits.

A two-pass tolerant lookup is round one plus round two. Round one builds superset $C$ with an index: prefix match on rotations for permuterm, or $C = ⋂_{i} L_{i}$ over k-gram posting lists for k-gram. Round two applies the true pattern test $f i t (t, Q W)$ to each $t \in C$ and keeps only passes. Filtering means that exact test; a false positive is a member of $C$ that fails it. Skipping round two ships $C$ as the answer, which is wrong by design.

Picture the same funnel for both tools. Permuterm narrows by rotated prefix, k-gram narrows by shared slices, but both funnels end in the same spout: a direct pattern check. The takeaway is that the index buys speed while the filter buys truth, and neither works alone.

5.5.2 Worked contrast on MON star

The demo vocabulary held words such as $m o nk ey$ , $m o ni t or$ , $m o n ey$ , and $m o n t h$ . The query was $M O N$ star. Permuterm round one pulls all rotations with the MON prefix, which gives those four plus close forms. K-gram round one with bigrams pulls a wider net. After round-two filtering, k-gram output still showed $M O N$ itself and $m o t i o n$ as extras in the demo. The verbal point was that k-gram output can keep $M O N$ and $m o t i o n$ popping out unless the second check is applied with care. Those two are false positives for MON star in that demo context: $M O N$ in all caps was a slice artifact and $m o t i o n$ breaks the required letter order at the start.

Worked MON star contrast with monkey, monitor, money, month, and motion extras. Query is $M O N$ star. Permuterm round one with prefix $M O N$ pulls monkey, monitor, money, and month, since each starts with $M O N$ in order. K-gram round one with bigrams $$ M$ , $M O$ , $O N$ , $N $$ pulls the same four plus motion, since motion shares $M O$ and $O N$ slices though its start is $M O T$ , not $M O N$ . Round two tests each word for the MON start. Monkey, monitor, money, and month pass. Motion has fourth-letter order $I$ versus $O$ at the third slot pattern and fails the MON start test, so it drops. The bare slice artifact $M O N$ drops too once the star-run rule is applied with care. Sense-check: any survivor must open with M, then O, then N, so motion with MO then T cannot survive a careful check.

The choice between the two is not fixed. It rests on the word set, the task, and how much tolerance for extra hits is okay. When an empty answer is worse than a few extras, the wider k-gram net can be the right pick. When exact shape matters more, the tighter permuterm path fits better. Since tolerant lookup sits under larger language systems, that choice ripples upward into later stages.

Scope: Permuterm supersets stay tight for single-star patterns; k-gram supersets stay wide and forgiving for rough typing. Assumption: Round two uses the same pattern definition as the user asked, with no silent loosening. If round two is skipped or uses a weaker test, both methods degrade to superset search with lingering false positives.

Pitfall: A common slip is to compare raw round-one sizes and call the larger tool worse. Size alone misleads: k-gram is meant to over-pull and then filter. Judge only round-two outputs, never round-one piles.

Real-world: product search often accepts a few extras to avoid empty pages, while command lookup prefers tight matches to avoid wrong actions. A shopper benefits from seeing motion near MON results, while a pilot typing a command does not.

Recap: Permuterm and k-gram share the superset-then-filtering shape; filtering is what removes MON and motion extras and leaves true MON star fits. Bridge: The same shape returns in spelling work: cheap k-gram screens in 5.10 propose, and exact grids in 5.7 to 5.8 dispose.

5.6 Isolated and Context-Sensitive Spelling Correction

5.6.1 The two rules behind correction

Search boxes fix spelling with two guides. First, among many possible fixes, pick the nearest one. Second, when two fixes sit at almost the same distance, pick the more common word. The verbal form was: use the nearest correction, and when two are almost equal, take the more common word. Nearness is a computed score, not a guess. Commonness comes from word counts in large text.

Why should frequency break ties at all? Because typing alone cannot tell two equally close words apart. If the keys allow both, the word people use more often is the safer bet. Distance picks the shortlist; counts pick the winner.

A lexicon is the stored list of correct spellings used for checks. Here a lexicon entry $w \in V$ is one valid word in vocabulary $V$ . When a typed word is already in $V$ , the checker leaves it alone. When it is absent, the checker ranks nearby members of $V$ and suggests the best one.

An isolated correction score ranks each $w \in V$ by $scor e (w) = d i s t (q, w) - λ lo g f r e q (w)$ , where $q$ is the typed string, $d i s t$ is edit or overlap distance, $f r e q (w)$ is corpus count, and $λ \geq 0$ weighs frequency. Small distance wins first; high frequency wins ties. The lexicon $V$ bounds the search: only members of $V$ can be suggested.

Picture two dials. One dial is closeness in letters, the other is weight from usage counts. A rare word must be much closer in letters to beat a common word. The takeaway is that spelling fix is a trade between what was typed and what people tend to write.

5.6.2 Isolated word versus context-sensitive checks

An isolated-word check looks at each word alone. A context-sensitive check looks at nearby words too. The pair $f r o m$ and $f or m$ shows the gap. Both live in the dictionary, so an isolated check sees no error. In the sentence with $f l e w$ $f r o m$ $H e d r u$ to $N a r i t a$ , the verbal point was that context demands $f r o m$ , not $f or m$ . The words $f l e w$ and the travel pattern $f r o m$ X to Y force the pick. An isolated check cannot see that force. It leaves $f or m$ in place and the error stays.

Worked from versus form choice. Typed sentence is flew form Hedru to Narita. Isolated check tests form alone: form is in $V$ , so no error is raised and the sentence stays wrong. Context check scores pairs: $P (f r o m ∣ f l e w,_, H e d r u)$ is high, since flew from X to Y is a common travel frame, while $P (f or m ∣ f l e w,_, H e d r u)$ is near zero. The context path swaps form to from and the sentence reads flew from Hedru to Narita, which fits the travel frame. Final pick is from by context. Sense-check: both candidates pass the dictionary test, so only neighbor words can split them, which is exactly what context adds.

The misspelling $R$ $E$ $T$ $R$ $E$ $I$ $V$ $A$ $L$ for $r e t r i e v a l$ , spelled $R$ $E$ $T$ $R$ $I$ $E$ $V$ $A$ $L$ , shows the other side. That typed form is absent from $V$ , so even an isolated check can catch it and offer the near correct form. Isolated checks suit light setups where speed matters and some misses are okay. Context checks suit strict setups where a wrong word carries high cost, such as defense files or medical notes. The class line was direct: when a false fix is costly, use the stricter context path.

Think of isolated check like proofing each tile alone, and context check like proofing each tile inside the full mosaic. The mosaic view catches swaps of two valid tiles.

Scope: Isolated-word checks fit non-word errors, where the typed form is absent from $V$ . Context-sensitive checks fit real-word errors like from versus form, where each choice is valid alone. Assumption: The lexicon $V$ matches the task domain, and neighbor models come from matching text. A general lexicon on medical notes misses both words and contexts.

Pitfall: Do not run context checks on every word without need. They cost far more than isolated checks. A sound setup runs isolated checks first and spends context work only on flagged spots plus valid-word confusions.

5.6.3 How nearness is scored for numbers versus words

For number vectors, nearness uses familiar scores such as Euclidean gap, Pearson link, cosine match, Manhattan blocks, and Mahalanobis stretch. Here a vector $x \in R^{d}$ is one data point with $d$ numbers, and the score maps a pair of vectors to one number. For words, those number scores do not apply straight away. Word nearness uses edit distance, weighted edit distance, and k-gram overlap. Each method turns letter change into a cost and then ranks candidates by that cost.

Word nearness has three standard forms. Edit distance counts moves between strings. Weighted edit distance scales each move by a pair weight $w (a, b)$ . K-gram overlap scores shared slices over pooled slices. Number scores like Euclidean gap need fixed-length vectors in $R^{d}$ ; words have varied lengths over a letter alphabet, so letter-move costs replace straight-line gaps.

Worked scoring contrast. Numbers: points $[1, 2]$ and $[4, 6]$ in $R^{2}$ have Euclidean gap $(4 - 1)^{2} + (6 - 2)^{2} = 5$ , a direct plug-in. Words: bok versus book cannot use that gap, since lengths differ and letters are symbols, not axes. Edit path gives distance 1 by one insert, k-gram overlap gives a high shared-slice score, and both rank book above unrelated words. Final lesson is that word scores count changes while number scores measure gaps. Sense-check: swapping two letters changes meaning wholly but moves numbers barely, so the two families must stay apart.

Recap: Nearest-plus-most-common drives fixes; isolated checks catch retrieval misspellings absent from $V$ , while context checks fix from-versus-form swaps with flew from Hedru to Narita as the model. Bridge: Nearness itself needs a ruler, so 5.7 builds the edit ruler, 5.9 weighs it, and 5.10 screens with slices.

5.7 Edit Operations and Levenshtein Distance

5.7.1 Insert, delete, replace, and transpose

An edit operation is one small letter change that turns one word toward another. Insert adds a letter. The demo typed $b o k$ for $b oo k$ . The verbal fix was to insert one $o$ . Here source $s = b o k$ has length 3, target $t = b oo k$ has length 4, and the insert of $o$ bridges the gap. Delete drops a letter. The demo typed extra $o$ shapes for $b oo k$ and the fix deletes the surplus letter. Replace swaps one letter for another. The demo typed $d o f$ for $d o g$ . The verbal note was that $f$ sits next to $g$ on the keyboard, so the slip is natural. The fix replaces $f$ with $g$ . Each of those three demos carries edit distance 1, since one move suffices.

Why start spelling with tiny moves instead of whole-word rules? Because most typos are one slip: a missed key, an extra tap, or a near-key hit. One-move families catch most real errors with almost no machinery.

Transpose swaps two back-to-back letters. The demo contrasted $a c t$ and $c a t$ . Without transpose, the change needs two replaces: $a$ to $c$ and $c$ to $a$ , while $t$ stays. That path costs 2. With transpose, one swap of $a$ and $c$ does the job. That path costs 1. Smaller distance means a closer guess, so transpose earns its place when swaps are common. This class keeps focus on insert, delete, and replace, with transpose noted as the swap shortcut.

An edit operation is one of insert, delete, replace, or transpose. Insert grows length by one, delete shrinks it by one, replace keeps length with one letter swap, and transpose swaps neighbors $ab \to ba$ . Keyboard slip story with $f$ next to $g$ makes replace natural: dof to dog is one replace of $f$ by $g$ , since those keys touch. Bok to book is one insert of $o$ ; act to cat is one transpose of $a$ and $c$ .

Worked one-move set. Case insert: $b o k \to b oo k$ by inserting $o$ after $b$ , giving $b + o + o k = b oo k$ in 1 move. Case delete: $b ooo k \to b oo k$ by deleting one $o$ , from length 5 to length 4 in 1 move. Case replace: $d o f \to d o g$ by replacing $f$ with $g$ in 1 move, aided by key closeness. Case transpose: $a c t \to c a t$ by swapping $a$ and $c$ in 1 move, against 2 by double replace. Each case shows distance 1 under its best move. Sense-check: length change signals insert or delete, same length with one odd letter signals replace, same letters in flipped order signals transpose.

Picture each operation as a hand move on tiles. Insert slides a new tile in, delete lifts one out, replace flips one tile over, transpose swaps two neighbors. The takeaway is that every typo is a short chain of such hand moves, and the shortest chain length is the distance.

5.7.2 Levenshtein recurrence in a grid

Levenshtein distance is the smallest total count of edits that turns a source word into a target word. The method fills a grid. Source letters run down the rows. Target letters run across the columns. Each cell $(i, j)$ stores the best distance for the first $i$ letters of the source and the first $j$ letters of the target. Here $i \in {0, \dots, m}$ counts source letters used, $j \in {0, \dots, n}$ counts target letters used, $m$ is source length, $n$ is target length, and $D (i, j)$ is the stored distance. The verbal description kept with the formula is: source down the rows, target across the columns, move cell by cell.

Moves have fixed meanings. A diagonal step means copy when letters match or replace when they differ. A left-to-right step means insert. A top-to-bottom step means delete. The recurrence is shown in one block:

$D (i, j) = min (D (i - 1, j) + 1, D (i, j - 1) + 1, D (i - 1, j - 1) + cos t)$

Here $D (i - 1, j) + 1$ is the delete path from the top, $D (i, j - 1) + 1$ is the insert path from the left, $D (i - 1, j - 1) + cos t$ is the diagonal path, and $cos t = 0$ when the two current letters match and $cos t = 1$ when they differ. The first row and first column compare against the empty string. The verbal form was: with null, adding each letter costs one more. So the top row reads 0, 1, 2, 3, 4 and the left column reads 0, 1, 2, 3, 4 for four-letter words. A cell uses only its three near neighbors: top, left, and diagonal. No other cells feed it. When the two letters match, take the plain min of the three. When they differ, take that min plus one. That plus-one is the penalty for the needed change.

The Levenshtein recurrence builds $D (i, j)$ from three neighbors: delete from the top, insert from the left, and diagonal copy or replace. Cost is $0$ on a letter match and $1$ on a mismatch. Base row and column are $D (i, 0) = i$ and $D (0, j) = j$ , since turning empty text into $j$ letters needs $j$ inserts. The answer is the bottom-right cell $D (m, n)$ . Transpose is not inside this recurrence; adding it gives the extended Damerau-Levenshtein form.

Worked mini grid for bok to book. Source bok runs down, target book runs across, with null row and column 0, 1, 2, 3, 4. Cell for $b$ versus $b$ matches, so it copies diagonal 0. Cell for $o$ versus $o$ matches and stays low. The extra $o$ in book arrives by one left step, adding 1 for the insert. Bottom-right reads 1, matching the one-insert story. A rival path with a delete plus an insert would cost 2 and loses the min, so the grid keeps 1. Sense-check: length differs by one and all shared letters line up, so distance 1 is the floor and the grid attains it.

Scope: This grid fits insert, delete, and replace with unit costs. Assumption: Each move costs 1 and order is kept left to right. Swaps like act to cat cost 2 here, not 1, since transpose sits outside the three-way min. Weighted costs in 5.9 replace the flat plus-one when slips differ in chance.

5.7.3 Student Questions and Answers

Q: Is edit distance just the count of replaced letters? A: No. Any of insert, delete, or replace adds one. Each of the three single-move demos has distance 1. Longer gaps sum moves, so distance is total moves, not only replaces. Bok to book shows an insert counting the same as dof to dog replace, and act to cat shows transpose as its own move family.

Exam note: Expect a short grid task where the first row and column are given against null and a few inner cells must be filled with the min-plus-cost rule. State the three neighbor values, the match-or-mismatch cost, and the min before writing the cell.

Recap: Insert, delete, replace, and transpose turn bok to book, dof to dog, and act to cat into counted moves, and the diagonal-aware recurrence with the null border turns those moves into a full grid. Bridge: The Oslo to Snow trace in 5.8 runs this grid end to end and then reads the moves back out.

5.8 Worked Levenshtein Example Oslo to Snow with Backtracking

5.8.1 Grid setup and first cells

The source is $os l o$ and the target is $s n o w$ . The verbal labels were query word oslo and true word snow. Both have length 4, so the grid holds 4 by 4 inner cells plus the null row and column. The null row and column are 0, 1, 2, 3, 4. The meaning is plain: turning empty text into $s$ costs 1, into $s n$ costs 2, into $s n o$ costs 3, into $s n o w$ costs 4, and the same holds down the source side.

Why work oslo to snow by hand when code could do it? Because the hand run shows where each number comes from, which is what lets you spot a bad cell later. One careful trace teaches the rule better than ten glances at a finished grid.

Take the cell for source letter $o$ against target letter $s$ . The verbal check was o is not equal to s. The three neighbors are 0, 1, and 1. The min is 0. Since the letters differ, add one. The cell becomes 1. Next, $o$ against $n$ also differs. Its neighbors center on 1, so min plus one gives 2. Next, $o$ against $o$ matches. Take the min of neighbors with no extra penalty. That cell becomes 2. The class hit a snag here when a 3 was written first and then fixed to 2 after rechecking the min. That fix matters: the match case must not add the extra one on the diagonal. The corrected value story where 3 fixed to 2 keeps later cells sound is worth keeping in mind, since every cell below and right builds on this one. A wrong 3 would have pushed later mins up by one and broken the final distance.

Grid setup uses source $s = os l o$ with $m = 4$ down the rows and target $t = s n o w$ with $n = 4$ across the columns. Border is $D (i, 0) = i$ and $D (0, j) = j$ . Inner cell rule is $D (i, j) = min (top + 1, left + 1, diag + cos t)$ with $cos t = 0$ on match and $1$ on mismatch. First-row cells $o$ to $s$ and $o$ to $n$ mismatch and rise to 1 and 2, while $o$ to $o$ matches and holds at 2.

Worked first-row numbers for oslo to snow. Borders are 0, 1, 2, 3, 4 on top and left. Cell $o$ versus $s$ : neighbors 0, 1, 1 give min 0, plus mismatch 1 gives 1. Cell $o$ versus $n$ : neighbors 1, 2, 1 give min 1, plus mismatch 1 gives 2. Cell $o$ versus $o$ : neighbors 2, 3, 2 give min 2, plus match 0 gives 2. Cell $o$ versus $w$ : mismatch lifts the min to 3. Row one reads 1, 2, 2, 3 from left to right. Sense-check: the match column dips or holds flat while mismatch columns climb, which is the visual sign of a sound row.

5.8.2 A simpler four-part cell view

A second view splits each cell into four small parts to track where the value came from. The verbal steps were: add one from each of the three used sides, then take the min for the deciding corner. In plain terms, form three sums: diagonal value plus maybe zero or one, left value plus one, top value plus one. Then keep the smallest.

The extra rule for the diagonal is the heart of it. When the two letters match, do not add to the diagonal carry. Just copy it. When they differ, add one to the diagonal carry. The other two sides always add one because insert and delete always cost a move. For $o$ to $s$ , all three sums grow, and the min is 1. For $o$ to $n$ , the three sums give 2. For $o$ to $o$ , the diagonal stays at 2 with no bump, so the min is 2. For $o$ to $w$ , the three sums were described as 4, 5, and 3, with min 3. The same repeat fills row two and onward to the end. The last cell, at the bottom right, reads 3. That 3 is the full Levenshtein distance from $os l o$ to $s n o w$ .

The four-part cell view writes each cell as three incoming sums plus the chosen min. Let $a = D (i - 1, j - 1) + cos t$ , $b = D (i, j - 1) + 1$ , $c = D (i - 1, j) + 1$ . Then $D (i, j) = min (a, b, c)$ . The corner that attains the min names the move: $a$ is diagonal copy or replace, $b$ is insert, $c$ is delete. Filling row by row to $(4, 4)$ gives $D (4, 4) = 3$ for oslo to snow.

Picture the grid as a city map with cost to reach each crossing. Each crossing is reached from the north, west, or northwest, paying the step toll. The bottom-right corner is the trip total. The takeaway is that local cheapest steps chain into a globally cheapest trip, which is why greedy per-cell mins still give the true distance.

5.8.3 Backtrack to name each move

Distance alone does not name moves. Backtrack does. Start at the last cell and ask where its value came from: left, top, or diagonal. Then step to that source cell and repeat until the null corner is reached. Each step maps to one move with its own cost. Copy costs 0. Insert, delete, and replace each cost 1.

The traced path in class gave five labeled steps for $os l o$ to $s n o w$ . First, value 3 came from the left, so insert $w$ . Cost 1. Next, value 2 came from the diagonal with $o$ matching $o$ , so copy $o$ . Cost 0. Next, value 2 came from the diagonal with $l$ against $n$ , so replace $l$ with $n$ . Cost 1. Next, value 1 came from the diagonal with $s$ matching $s$ , so copy $s$ . Cost 0. Last, source $o$ against null means delete $o$ . Cost 1. Total cost is 1 plus 0 plus 1 plus 0 plus 1, which is 3. That sum matches the last-cell distance.

Worked backtrack chain for oslo to snow with insert, copy, replace, and delete. Start at $(4, 4) = 3$ and step left to insert $w$ for 1. Step diagonally on $o = o$ to copy $o$ for 0. Step diagonally on $l$ versus $n$ to replace $l$ with $n$ for 1. Step diagonally on $s = s$ to copy $s$ for 0. Step up to delete the leading $o$ for 1. Chain sum is $1 + 0 + 1 + 0 + 1 = 3$ , matching $D (4, 4)$ . Forward order is delete $o$ , copy $s$ , replace $l$ with $n$ , copy $o$ , insert $w$ : oslo to snow in five labeled moves costing 3. Sense-check: copies cost nothing, so the two shared letters $s$ and $o$ add zero while the three real changes add one each.

The ordering from source to target reads: delete the first $o$ , keep $s$ , replace $l$ with $n$ , keep $o$ , insert $w$ . Read backward it is the same chain seen from the end. If a task asks only for distance, the last cell suffices. If it asks for moves, the backtrack chain with costs is required.

Scope: Backtracking fits any filled grid and names one cheapest path. Assumption: Ties may give more than one cheapest path; any min path is valid unless the task asks for all. Copy steps never add cost, so long shared runs keep distance low even across long words.

5.8.4 Student Questions and Answers

Q: In the first cell O to S we did one plus zero to get one, but in the same row O to W we seemed to just take values like four without adding. Why the change? A: Both cells add. O to W used three sums where each side had already added one, described as three plus one, two plus one, and four plus one. The min of those sums was three. The diagonal always comes from the diagonal neighbor only, the left from the left only, and the top from the top only. No cell skips its plus-one; the numbers shown had the bump folded in.

Pitfall: Two errors recur. One is adding one on a match diagonal; matches copy with zero. The other is backtracking forward instead of from the end; always start at the bottom-right and walk to the null corner, then reverse the list for source-to-target order.

Exam note: Practice the full Oslo to Snow grid by hand, then trace back and label each step as insert, delete, copy, or replace with its cost. Distance 3 alone earns only part marks; the five-step chain with $1 + 0 + 1 + 0 + 1 = 3$ earns full marks.

Recap: Oslo to snow fills to distance 3 and backtracks through insert $w$ , copy $o$ , replace $l$ with $n$ , copy $s$ , and delete $o$ . Bridge: When some slips deserve smaller bills than others, the flat plus-one gives way to the weighted grid of 5.9.

5.9 Weighted Edit Distance

5.9.1 Why equal costs can mislead

Plain edit distance charges 1 for every move. Human slips do not spread evenly. Letters close on a keyboard swap more often, such as $m$ with $n$ or $g$ with $h$ . A flat cost of 1 treats a likely slip the same as a rare one. That flat view can rank the wrong candidate first when two words sit one move away but one move is far more natural.

Which fix would you trust: a swap of neighbors on the keyboard or a swap of far-apart keys? Both are one move, yet the first happens far more often. Equal bills hide that chance gap, so rankings need weights that reflect how people really mistype.

A weighted edit distance gives small penalties to likely slips and larger penalties to odd ones. The verbal examples were m to n and g to h as high-chance swaps from key closeness. Instead of cost 1, such a pair might cost 0.2 or 0.3. An odd change keeps cost near 1. The rank then favors the natural slip.

A weight table $w (a, b)$ sets the bill for turning letter $a$ into $b$ . Likely pairs like $m \to n$ or $g \to h$ get small penalties such as $0.2$ or $0.3$ ; odd pairs keep $1$ ; matches keep $0$ . With two candidates at unit distance 1, the weighted totals split apart and the natural slip wins. Keyboard proximity, scan confusions, and mobile slips each get their own table from measured error counts.

Worked ranking split for m to n versus m to q. Typed word ends in $m$ and candidates offer $n$ or $q$ . Flat costs give both distance 1, a tie. Weighted table gives $w (m, n) = 0.3$ for near keys and $w (m, q) = 1.0$ for far keys. Totals are 0.3 against 1.0, so the $n$ candidate ranks first. Same move count, different bills, and the likely slip wins. Sense-check: weights only break ties and near-ties; a two-move natural slip still loses to a one-move odd slip unless tables are extreme.

5.9.2 How weights enter the grid

Let $w (a, b)$ be the cost of turning letter $a$ into letter $b$ . Here $a$ and $b$ are single letters, $w (a, a) = 0$ for a match, $0 < w (a, b) < 1$ for a likely slip, and $w (a, b) = 1$ for a plain change. The grid recurrence keeps its shape but swaps the flat plus-one for the weight:

$D (i, j) = min (D (i - 1, j) + d e l, D (i, j - 1) + in s, D (i - 1, j - 1) + w (a, b))$

Here $d e l$ is the delete weight, $in s$ is the insert weight, and $w (a, b)$ is the replace weight for the current pair. The verbal source kept with the formula is: same grid, but weights replace the flat one. A stored weight table holds the pair costs. A rule might read: when the pair is m to n, use 0.3. The table must exist before search starts. Common tables target keyboard slips, scan errors from optical character tools, and mobile typing slips. Ready code in common language libraries can apply these tables without hand math.

The weighted recurrence keeps the three-way min but pays table prices. Delete pays $d e l$ , insert pays $in s$ , diagonal pays $w (a, b)$ for the current pair. Borders add $d e l$ or $in s$ per step instead of flat ones. The bottom-right cell is still the answer, now in weighted units. Setting all weights to 1 returns the plain Levenshtein grid, so plain distance is a special case of weighted distance.

Worked weighted cell for $g$ to $h$ . Neighbors are top 1.0, left 1.0, diagonal 0.5. Table gives $w (g, h) = 0.2$ for key closeness, with $d e l = in s = 1$ . Sums are diagonal $0.5 + 0.2 = 0.7$ , left $1.0 + 1 = 2.0$ , top $1.0 + 1 = 2.0$ . Min is 0.7 by replace, far below the flat-grid 1. A rival pair $g$ to $q$ with $w = 1.0$ would give $1.5$ at the same spot and lose. Final cell shows how weights pull likely slips down without touching odd pairs. Sense-check: diagonal wins whenever the pair weight is small, which is exactly when the slip is likely.

Picture the grid as toll roads where some lanes discount. Flat grids charge 1 at every gate; weighted grids post small tolls on busy slip lanes like $m$ to $n$ and full tolls elsewhere. The takeaway is that traffic counts set the tolls, and tolls steer the cheapest path.

Scope: Weights fit typed, scanned, and mobile text where error shapes skew. Assumption: Tables are learned from matching data and stay fixed during search. A keyboard table on scan errors misprices pairs, since look-alike glyphs differ from near keys.

Pitfall: Do not hand-tune weights per query. Tables come from counts over many errors, not from one example. Changing $w (m, n)$ to force one fix breaks ranking elsewhere.

Real-world: phone keyboards and scanned pages gain the most, since their error shapes are skewed toward near keys and look-alike glyphs. Mail search and catalog entry both use these tables to favor slips users really make.

Recap: Equal costs tie natural slips with odd ones, so letter-pair weights with penalties like 0.2 and 0.3 let keyboard pairs win on merit. Bridge: Cheap slice screens still open the race, so 5.10 pairs Jaccard overlap with these grids: slices propose, weights dispose.

5.10 K-Gram Overlap and Jaccard Match for Spelling

5.10.1 Why not score every dictionary word with a full grid

A full grid per dictionary word is slow. Each compare walks rows times columns. Across a large vocabulary that cost explodes. The class line was plain: doing grids for every term by hand already feels slow, so doing it for a whole dictionary at search time is far too slow. The fix is a cheap screen first. Build k-gram sets for the query and for each stored word, rank by overlap, and run the heavy grid only on top ranks when needed.

How slow is full-grid search really? A four-by-four grid is 16 cells, which feels fine once. Times 100,000 words it is 1.6 million cells per query, far past a search-time budget. A slice screen cuts that pile to a shortlist of tens before any grid runs.

Cheap screen first avoids slow full grids across whole dictionary runs. The screen uses inverted slice lists already built for wildcard search, so no new heavy build is needed. Only top slice scorers pay for grids. The takeaway is a two-stage budget: pennies per word for slices, dollars only for finalists.

A two-stage spelling pipeline is screen plus refine. Stage one scores every candidate by k-gram overlap in near-linear time over slice lists. Stage two runs edit grids only on the top $K$ scorers, with $K$ like 10 or 50. Total cost drops from $∣ V ∣ \times m \times n$ grid work to slice merges plus $K \times m \times n$ , where $∣ V ∣$ is vocabulary size and $m \times n$ is grid size.

5.10.2 Jaccard score in plain terms

The Jaccard score for two sets $A$ and $B$ is shared items divided by all distinct items. Here $A$ is the k-gram set of the query, $B$ is the k-gram set of one candidate, $A \cap B$ is the shared part, and $A \cup B$ is the pooled distinct part. The formula in one block is:

$J (A, B) = \frac{∣ A \cap B ∣}{∣ A \cup B ∣}$

Here $∣ S ∣$ means count of items in set $S$ . The verbal form kept with the formula is: A intersect B by A union B. A higher value means a closer shape. The pick is the candidate with the top score.

The Jaccard score normalizes overlap by size. Shared count $∣ A \cap B ∣$ rewards matching slices; pooled count $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ stops long words from winning by bulk alone. Score lies in $[0, 1]$ , with 1 for same sets and 0 for disjoint sets. Jaccard match for spelling ranks candidates by this ratio and keeps the top scorer.

Worked tiny Jaccard warm-up apart from bord. Sets are $A = {x, y, z}$ and $B = {y, z, w}$ . Shared items are $y$ and $z$ , so $∣ A \cap B ∣ = 2$ . Pooled distinct items are $x, y, z, w$ , so $∣ A \cup B ∣ = 3 + 3 - 2 = 4$ . Score is $2/4 = 0.5$ . A rival $C = {x, y, z}$ would score $3/3 = 1$ . Final order is $C$ first, then $B$ . Sense-check: pooled count always lies between the larger set size and the sum, so the ratio stays inside zero to one.

Picture two circles overlapping. The lens in the middle is the shared part; the full inked area of both circles is the pooled part. Jaccard is lens over ink. The takeaway is that shape match, not raw size, drives the score.

5.10.3 Worked match for bord against board, bold, and bird

The query shape is $b or d$ , spelled $B$ $O$ $R$ $D$ . The verbal setup wavered between board and bord, but the math that follows pins it down: the query lacks $A$ while the top candidate holds $A$ . With $k = 2$ and dollar edges, the query set is dollar plus $B$ , $B$ plus $O$ , $O$ plus $R$ , $R$ plus $D$ , and $D$ plus dollar. That is five bigrams. The candidate $b o a r d$ , spelled $B$ $O$ $A$ $R$ $D$ , gives dollar plus $B$ , $B$ plus $O$ , $O$ plus $A$ , $A$ plus $R$ , $R$ plus $D$ , and $D$ plus dollar. That is six bigrams. Shared items are dollar plus $B$ , $B$ plus $O$ , $R$ plus $D$ , and $D$ plus dollar: four in all. Pooled distinct count is 5 plus 6 minus 4, which is 7. So the score is 4 divided by 7, about 0.57. We write $J = 4/7$ with $4 = ∣ A \cap B ∣$ shared and $7 = ∣ A \cup B ∣$ pooled.

The candidate $b o l d$ , spelled $B$ $O$ $L$ $D$ , gives dollar plus $B$ , $B$ plus $O$ , $O$ plus $L$ , $L$ plus $D$ , and $D$ plus dollar. Shared with the query are dollar plus $B$ , $B$ plus $O$ , and $D$ plus dollar: three items. Pooled count is 5 plus 5 minus 3, which is 7. Score is 3 divided by 7, about 0.43. The candidate $bi r d$ , spelled $B$ $I$ $R$ $D$ , gives dollar plus $B$ , $B$ plus $I$ , $I$ plus $R$ , $R$ plus $D$ , and $D$ plus dollar. Shared are dollar plus $B$ , $R$ plus $D$ , and $D$ plus dollar: three items. Score is again 3 divided by 7, about 0.43. The top pick is $b o a r d$ at 0.57. The class called this path easy and relatable next to full grids, while noting that fit depends on the data. Light setups favor this screen. Strict setups still want the full grid on top hits.

Worked bord ranking with Jaccard 0.57 and 0.43. Query bord has 5 bigrams. Board has 6 with 4 shared, so pooled is $5 + 6 - 4 = 7$ and $J = 4/7 \approx 0.57$ . Bold has 5 with 3 shared, so pooled is $5 + 5 - 3 = 7$ and $J = 3/7 \approx 0.43$ . Bird has 5 with 3 shared, so pooled is again 7 and $J = 3/7 \approx 0.43$ . Order is board first at 0.57, then bold and bird tied at 0.43. Final pick is board. Sense-check: board keeps both edge slices and two middle slices, while rivals keep edges but lose middle runs, so board must lead.

Scope: Bigram Jaccard screens fit short words and single-error typos where most slices survive. Assumption: $k = 2$ with dollar edges is fixed for query and candidates alike. Mixed $k$ across sides breaks counts, since slice sets would differ in kind.

5.10.4 Student Questions and Answers

Q: Should the bord versus bold score be 3 by 6 instead of 3 by 7? A: The bottom is the pooled distinct set, not the longer list alone. Query has 5, bold has 5, shared has 3, so pooled is 5 plus 5 minus 3, which is 7. The score is 3 by 7. Using 6 would double-count shared slices instead of pooling distinct items once.

Exam note: Show both the shared count and the pooled math as 5 plus 6 minus 4 for the board case, not just the final decimal. Write each slice set, mark shared items, then show pooled as total minus shared before dividing.

Recap: Full grids over the dictionary cost too much, so Jaccard overlap over bigram sets screens bord against board, bold, and bird as 4 by 7, 3 by 7, and 3 by 7 with board first. Bridge: When errors keep sound but change letters, slice screens miss and sound buckets in 5.11 take over.

5.11 Phonetic Matching with Soundex

5.11.1 The hash idea and the three rules

A phonetic hash maps sound-alike words to one code. Search then pulls all words with the same code. Soundex is one such hash, with Metaphone and Double Metaphone as later options. The method uses three rules. First, keep the first letter as is. Next, turn the rest into digits by fixed groups. Last, shape the result as the first letter plus three digits, padding with zeros when short.

Why hash by sound when spelling tools already exist? Because names break spelling rules: Smith and Smyth sound close but share few slices. Sound buckets pull spelling variants together before finer rank steps run, catching what letter screens miss.

The digit groups in class were: vowels plus $H$ , $W$ , $Y$ map to 0 and are skipped, $B$ , $F$ , $P$ , $V$ map to 1, $C$ , $G$ , $J$ , $K$ , $Q$ , $S$ , $X$ , $Z$ map to 2, $D$ , $T$ map to 3, $L$ maps to 4, $M$ , $N$ map to 5, and $R$ maps to 6. Here each letter $c$ maps to digit $f (c)$ by that table, $f (c) = 0$ means drop the letter, and the code is $C = (l_{1}, d_{1}, d_{2}, d_{3})$ where $l_{1}$ is the kept first letter and each $d_{i}$ is a kept digit. The verbal form kept with the formula is: first letter as is, rest to numbers, then first letter plus three digits. The table is fixed by the method. In a test the table would be given, so recall of each group from memory is not the point.

A Soundex code is $l_{1} d_{1} d_{2} d_{3}$ : kept first letter plus three digits. Mapping $f$ sends letter groups to digits 1 through 6 and vowels plus $H, W, Y$ to 0 for dropping. Adjacent same digits collapse to one, zeros drop, and short codes pad with zeros to length four. Soundex digits group by rough sound place, not by alphabet order, so $B, F, P, V$ share 1 as lip sounds.

Picture buckets labeled S530, S540, and so on. Each name card drops into the bucket matching its sound code. Lookup pulls the whole bucket, not one spelling. The takeaway is that recall rises since variants land together, while precision falls since unlike names can share a bucket.

5.11.2 Worked codes for Smith and Smyth

Take $S mi t h$ , spelled $S$ $M$ $I$ $T$ $H$ . Keep $S$ . Map $M$ to 5. Map $I$ to 0, so drop it. Map $T$ to 3. Map $H$ to 0, so drop it. Kept digits are 5 and 3. That is only two digits, so pad one zero to reach three. The code is $S 530$ , where $S$ is the kept first letter, $5 = f (M)$ , $3 = f (T)$ , and $0$ is the pad. Take $S m y t h$ , spelled $S$ $M$ $Y$ $T$ $H$ . Keep $S$ . Map $M$ to 5. Map $Y$ to 0, so drop it. Map $T$ to 3. Map $H$ to 0, so drop it. The code is again $S 530$ . Both spellings land in one bucket, so a search for one suggests the other. That shared bucket is the whole point of the hash.

Worked Smith and Smyth codes with padded zero. Smith: keep $S$ , $M \to 5$ , $I \to 0$ drop, $T \to 3$ , $H \to 0$ drop, digits $5, 3$ , pad to $S 530$ . Smyth: keep $S$ , $M \to 5$ , $Y \to 0$ drop, $T \to 3$ , $H \to 0$ drop, digits $5, 3$ , pad to $S 530$ . Both map to $S 530$ with padded zero, so one query pulls both spellings. A name like Schmidt keeps $S$ , then $C \to 2$ , $H$ drops, $M \to 5$ , $I$ drops, $D \to 3$ , $T \to 3$ collapsing, giving a nearby but distinct code that shows bucket limits. Sense-check: kept first letter plus three slots forces length four, so $S 53$ without the pad would be malformed and must gain a zero.

More names follow the same path. Forms such as $E r i cso n$ with $K$ , with $C$ , or with $E$ shifts can land near one another when their kept consonants match and vowels drop. The demo also noted an exercise set for free-time practice with more such names. The takeaway stays small: sound buckets pull spelling variants together before finer rank steps run.

Scope: Soundex fits Anglo name variants where first letters match and consonant frames carry sound. Assumption: Table is given and first letter is trusted. Names with shifted first sounds or non-English frames break the hash, which is where Metaphone and Double Metaphone tune groups with more study.

5.11.3 Student Questions and Answers

Q: Why add a zero at the end of S53? A: The code shape is fixed as one letter plus three digits. When a word yields only two digits, pad with zeros to reach three. S53 becomes S530 by that rule. Padding keeps all codes the same length so bucket keys line up.

Q: If any vowel can replace I and H still gives the same code, does sound stay the same? A: No. The code can stay the same while sound shifts. That gap is a known weak spot of this hash. It is why later hashes such as Metaphone and Double Metaphone exist. They keep the bucket idea but tune the letter groups with more study. Soundex buys recall at the price of false mates.

Real-world: name search in records and customer lists uses sound hashes to catch Smith versus Smyth without asking the user to guess each spelling. Helplines, voter rolls, and patient files all lean on this bucket trick when callers spell names by ear.

Recap: Soundex keeps the first letter, maps groups to digits, and pads to one letter plus three digits, so Smith and Smyth both give S530. Bridge: The same edit moves that fix names also read gene strings, where 5.12 swaps the alphabet to four bases.

5.12 Edit Operations in DNA Sequences

5.12.1 Bases as an alphabet

DNA bases use a four-letter alphabet: $A$ , $T$ , $C$ , $G$ . Here each base is one symbol, a gene string $G = g_{1} g_{2} \dots g_{n}$ is a long chain over those four symbols, and $n$ can run very large. The class image was that a full decoded chain is so long it invites jokes about reaching the moon. The short strings below stand in for real genes to keep the moves visible.

Why study genes in a spelling lecture? Because DNA reads are strings over a tiny alphabet where the same insert, delete, and replace moves apply. Spelling tools transfer straight across once letters become bases.

A gene string is $G = g_{1} g_{2} \dots g_{n}$ with each $g_{i} \in {A, T, C, G}$ . Length $n$ runs to thousands or millions in real reads, so short demo strings stand in for full chains. Edit distance over this four-letter alphabet counts base changes the same way it counts letter changes over 26 letters.

Picture the four bases as four tile colors in a very long row. A patient sample is one row, the known gene is a second row below it. Matching rows line up tile by tile; gaps and color swaps mark edits. The takeaway is that string match cares about order and symbols, not about what the symbols mean.

5.12.2 Worked insert, delete, and replace on gene strings

Suppose a known gene string $A$ is on file and a new sample from a patient shows $A T GC A T G$ . The verbal read was that base $C$ is missing in the sample relative to the known form. In edit terms, the sample needs an insert of $C$ at the right slot to match the known gene. If the known form drives harm, that insert models what a fix must add. Delete and replace read the same way: a surplus base in the sample means a delete step, while a swapped base means a replace step. The same three moves from word search so describe base change. That shared math is why the distance unit felt worth the effort.

Worked gene edits on patient sample ATGCATG. Case insert: known form has $C$ at slot 4 while the patient sample ATGCATG lacks it at that slot, so insert $C$ there in 1 move to restore the known frame. Case delete: a sample reading $A T GC C A T G$ with doubled $C$ needs delete of one $C$ in 1 move to reach the known form. Case replace: a sample reading $A T G AA T G$ with $A$ where $C$ belongs needs replace of $A$ by $C$ in 1 move. Each case uses one of insert, delete, or replace on gene strings, with the patient sample as source and the known gene as target. Sense-check: base counts shift by one for insert and delete and stay flat for replace, so length change names the move family at once.

Scope: Single-base insert, delete, and replace fit point changes between a patient sample and a known gene string. Assumption: Reads align slot to slot with a trusted known form. Long repeats and shifted frames need full alignment grids, not single-move labels alone.

Real-world: gene read comparison uses these moves to spot single-base changes across samples before deeper study starts. Labs flag the one-letter gap first, then run heavier alignment only on flagged regions.

Recap: Bases $A$ , $T$ , $C$ , $G$ form the alphabet, and the patient gene sample ATGCATG with its missing $C$ shows insert, delete, and replace on real strings. Bridge: This closes the lecture arc from wildcard trees through spelling grids to living strings: one edit toolkit serves catalogs, keyboards, name lists, and genes.

Exam Guidance Summary

Exam note: Rotation tasks are likely. For a short word such as mama, write dollar at the end and list each rotation. For a pattern such as S star NG, rotate until the star sits last and use NG dollar S as the lookup key. Show sing and song as hits and using as a reject. Count check is word length plus one for the dollar slot: mama with four letters gives five rotations, so a four-member list is missing one.

Exam note: Phrase tasks are likely. With quick brown, brown fox, and quick brown fox over a few short documents, state which documents each of biword and positional return. Mark document 3 as the biword false positive for brown fox. Cite positions such as 36, 37, 38 in document 247 for fools rush in. Show the plus-one links $37 = 36 + 1$ and $38 = 37 + 1$ rather than only naming documents.

Exam note: Grid tasks are likely. Fill Levenshtein cells with the min-plus-cost rule, keep the null row and column as 0, 1, 2, 3, 4, and give both distance and moves. For Oslo to Snow the distance is 3 via insert W, copy, replace L with N, copy S, and delete O. A second grid of the same size may be given for solo practice. Backtrack from the bottom-right and label each step with its cost so the chain sums to the last cell.

Exam note: Jaccard tasks are likely. For bord against board, bold, and bird, show shared over pooled counts as 4 by 7, 3 by 7, and 3 by 7, then pick board at about 0.57. Write the pooled step as total minus shared, such as 5 plus 6 minus 4 is 7. List slice sets first so shared and pooled counts can be checked.

Exam note: Soundex tasks are likely with the table given. Keep the first letter, drop zeros, keep three digits, and pad with zeros. Smith and Smyth both give S530. Do not recall groups from memory; read the given table and show each letter map plus the pad step.

Exam note: pace from here is fast. Index build, index size control, vector models, and scoring steps close out the midterm span. Keep each derivation and each worked number ready for quick recall.

Key Industry Applications

Real-world: trailing-star and leading-star trees speed prefix search in catalogs, editors, and database filters. Reversed trees let suffix search run as fast as prefix search. Type-ahead boxes and SQL-style star filters both ride this path.

Real-world: permuterm rotation supports mid-pattern search such as S star NG for sing, song, string, and strong in one lookup. Log search and SKU hunt use the same spin when codes vary in the middle.

Real-world: k-gram slices support fast tolerant lookup when typed text is rough. The same slices screen spelling fixes before heavy grids run. Editors and catalog search share one slice build for both tasks.

Real-world: biword pairs serve quick phrase hints such as data mining and information retrieval, while positional slots serve exact phrase demands such as quick brown fox in one document only. Chat search favors pairs for speed; legal search favors positions for proof.

Real-world: search engines and mail search use wildcard and spelling paths to return useful pages despite slips. SQL-style star filters are the early root of the same habit.

Real-world: phone keyboards, scanned pages, and mobile typing gain most from weighted costs that favor near-key slips such as m to n and g to h. Autocorrect tables are tuned per device for this reason.

Real-world: customer record search uses Soundex buckets such as S530 to pull Smith and Smyth together. Helplines and patient files catch sound variants without asking callers to spell each name.

Real-world: gene string comparison uses insert, delete, and replace to flag single-base changes such as a missing C in ATGCATG before deeper lab work. Flagged regions then move to full alignment.

IR Lecture 5 notes · Tolerant Retrieval: Wildcard Queries and Spelling Correction

Information Retrieval· postgraduate· 2026-09-14

Sections Breakdown

1Trailing and Leading Wildcard Search with Trees

Trailing-star walks one prefix path; leading-star repeats it on a reversed tree with NOM spellings.

2Permuterm Index for General Wildcard Queries

Permuterm rotation with dollar marker turns any single star into a trailing-star prefix hunt plus Boolean superset filtering.

3K-Gram Index for Wildcard Queries

K-gram slices per word are ANDed into a Boolean superset, then filtered letter by letter.

4Biword and Positional Indexes for Phrase Search

Biword pairs give cheap loose hints; positional slots with plus-one tests prove exact phrases.

5Two-Pass Retrieval and False Positives in Tolerant Search

Permuterm and k-gram share superset-then-filtering; round two removes MON and motion extras.

6Isolated and Context-Sensitive Spelling Correction

Nearest-plus-most-common drives fixes; isolated catches non-words, context fixes from versus form.

7Edit Operations and Levenshtein Distance

Insert delete replace transpose counted by the Levenshtein recurrence over a grid.

8Worked Levenshtein Example Oslo to Snow with Backtracking

Oslo to snow fills to distance 3 and backtracks through insert copy replace delete.

9Weighted Edit Distance

Letter-pair weights with penalties like 0.2 and 0.3 let likely keyboard slips win.

10K-Gram Overlap and Jaccard Match for Spelling

Cheap Jaccard screen first avoids slow full grids; bord ranks board 4 by 7 first.

11Phonetic Matching with Soundex

Soundex keeps first letter plus three digits; Smith and Smyth share S530.

12Edit Operations in DNA Sequences

Bases A T C G form the alphabet; patient sample ATGCATG shows insert delete replace.

Postgraduate students in 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.

Trailing and Leading Wildcard Search with Trees

Must-know: Trailing-star tree walk lists the MON subtree; reversed tree turns star MON into NOM star.

$W = {t : t fits P}$

Top pitfall: Star means any run including empty, not one letter.

Self-check: Recall the worked numbers for 5.1.