Lab 03

Tolerant Retrieval and Spelling Correction

Wild-cards Edit distance n-gram overlap Soundex

Work in progress These notes are still being written and reviewed: content may change, and some parts may still contain mistakes.

Overview of the lab

Goal: find documents even when the query does not match the dictionary exactly: the user types part of a word, misspells it, or spells a name as it sounds. The lab goes with the lecture on tolerant retrieval (IIR, chapter 3).

Tolerant retrieval: the problem, and what we need before we start (a list of correct words).
Wild-card queries: B-trees, the permuterm index, k-gram indexes.
Edit distance: how far apart two words are, computed by dynamic programming.
Finding candidates fast: n-gram overlap, the Jaccard coefficient, tries.
Context and choosing a suggestion: flew form Heathrow, "Did you mean", thesauri.
Soundex: matching names by how they sound.
Putting it together: which queries the engine can now answer.

Tolerant retrieval

So far a query term had to match a dictionary term exactly. Real queries are messier: mon* (any word starting with mon), Alanis Morisett (misspelled), chaikofski (a name spelled as it sounds). Tolerant retrieval maps such query terms to the dictionary terms the user probably meant, and then runs the usual Boolean query on the inverted index.

Wild-card queries: the user gives part of a term; we enumerate every dictionary term that fits.
Spelling correction: the user's term is not what they meant; we find the closest correct terms.
Soundex: the user wrote a name as it sounds; we match terms that sound alike.

Spelling correction: uses and flavors

Two uses: correcting the documents being indexed (mainly OCR'ed text: the goal is a dictionary with fewer OCR-induced misspellings), and correcting the query, our main focus. For a query we can either retrieve documents indexed by the correct spelling, or suggest alternative queries: Did you mean …?
Isolated-word correction: check each word on its own. It cannot catch typos that are real words: from → form.
Context-sensitive correction: look at the surrounding words: I flew form Heathrow to Narita.
Domain knowledge helps: OCR confuses O and D more often than O and I, which are the likely pair when typing (adjacent on the QWERTY keyboard).

Prerequisite: a list of words at hand

Isolated-word correction rests on one premise: there is a lexicon the correct spellings come from. Given the lexicon and a character sequence $q$, return the lexicon words closest to $q$.

A public list of all words in a language: e.g. Google Books Ngrams, Project Gutenberg, a standard dictionary, or a hand-maintained industry-specific lexicon.
The words in the indexed documents: this covers names, acronyms and domain terms, but it also contains the misspellings. You can add domain-specific words by hand.

💡 In this lab the lexicon is the dictionary of the 100 sci.crypt posts from Lab 01: 4,389 words made of letters only, each with its document frequency. It shows the downside of a corpus lexicon: goverment (2 posts), govenment and geovernment are in it, next to government (31 posts).

Lecture

Wild-card queries

A * stands for any sequence of characters: mon* asks for all documents containing a word that begins with mon. First enumerate the dictionary terms that match the pattern, then look up the postings of each and combine them with OR.

A `*` at the end or at the start: B-trees

Trailing wild-card mon*: easy if the dictionary is a search tree (a B-tree, or a trie): retrieve all words in the range mon ≤ w < moo.
Leading wild-card *mon: harder. Keep a second B-tree of the terms written backwards and retrieve the range nom ≤ w < non.
One * in the middle pro*cent: take the terms starting with pro from the first tree, those ending in cent from the reverse tree, and intersect the two sets.
Cost: every enumerated term becomes its own lookup in the inverted index, so se*ate AND fil*er can turn into many Boolean AND queries.

Any `*`: the permuterm index

Idea: rotate every wild-card query so that the * ends up at the end, then use a B-tree prefix lookup as before. Add an end symbol $ to each term and index every rotation of term$, each pointing back to the term.

Query	Look up	Example
`X`	`X$`	`hello` → `hello$`
`X*`	`$X*`	`hel` → `$hel`
`*X`	`X$*`	`llo` → `llo$`
`X`	`X*`	`ll` → `ll*`
`X*Y`	`Y$X*`	`helo` → `o$hel`
`XYZ`	`Z$X*`, then keep terms with `Y` in between	`fimoer` → `er$fi`: fishmonger* stays, filibuster is filtered out

💡 The slide lists five rotations of hello$ and writes the rule for X* as X*$. There are six rotations ($hello is missing), and X* is looked up as $X*, which needs exactly that rotation. The price: every term is stored once per rotation. The lecture calls it about four times the lexicon; IIR says almost ten-fold for a dictionary of English terms.

Any `*`: k-gram indexes

k-grams: all sequences of $k$ characters in a term, with $ marking its start and end. The 2-grams (bigrams) of month: $m mo on nt th h$.
A second inverted index: from each k-gram to the dictionary terms that contain it ($m → mace, madden, …; mo → among, amortize, …).
Querying: mon* becomes $m AND mo AND on. Fast and space efficient.
❗ Post-filter: the AND also returns terms that contain all the k-grams but do not fit the pattern (the lecture's moon; in sci.crypt morons and motivation). Check every enumerated term against the query before looking it up in the inverted index.

Try it: one wild-card query, three indexes

A query with * on the sci.crypt lexicon. Each method must find the same terms; compare how. Struck-out terms are the bigram index's false matches, removed by post-filtering.

Try it: the permuterm vocabulary of a term

💡 Wild-cards can make queries expensive: one special-index lookup, then filtering, then one inverted-index lookup per enumerated term. That is one reason to keep them behind an "Advanced search" button: it avoids clutter and deters users from typing a prefix and a * when they do not need to.

Notebook

Finding the correct word: edit distance

To pick the lexicon words "closest" to a misspelled query we need a distance between strings. The standard one counts single-character edits.

📐 Edit (Levenshtein) distance

The minimum number of single-character edits that turn $s_1$ into $s_2$. The edits are insert, delete and replace a character. E.g. the edit distance from cat to dog is 3. It is solved with dynamic programming in $O(|s_1| \cdot |s_2|)$ time.

Edit distance algorithm

Cell $m[i, j]$ holds the edit distance between the first $i$ letters of $s_1$ and the first $j$ letters of $s_2$.

Initialize the matrix with zeros; it has $|s_1|+1$ rows and $|s_2|+1$ columns.
Initialize the first row and column with the numbers from 0 to $|s_2|$ and from 0 to $|s_1|$: the cost of building a prefix by inserting letters, starting from the empty string.
Every other cell is the cheapest of three moves:

m[i,j] = \min\begin{cases} m[i-1,j] + 1 & \text{delete } s_1[i] \\ m[i,j-1] + 1 & \text{insert } s_2[j] \\ m[i-1,j-1] + \begin{cases}0 & s_1[i] = s_2[j]\\ 1 & \text{otherwise}\end{cases} & \text{replace (or keep)} \end{cases}

The minimum edit distance is in the last cell, $m[|s_1|, |s_2|]$.

Try it: fill the table

The default is the notebook's SUNDAY vs SATURDAY table (distance 3). Step through the cells, or click any cell to see which of its three neighbours it came from. The highlighted path is one cheapest sequence of edits (the backtrace).

transpositions (Damerau) keyboard-weighted replace

💡 The keyboard weights are made up for illustration: replacing a letter by one of its QWERTY neighbours costs 0.5 (m → n), any other replacement costs 1 (m → q). Real systems learn such weights from data.

1Compute the edit distance between the words elephant and relevant.

3: insert r at the start, replace p by v, delete h (r·elephant → relevant). Load elephant / relevant in the widget to see the table and the path. The distance is symmetric: edit_distance('relevant', 'elephant') is also 3.

Exercise 2: implement the minimum edit distance algorithm. The notebook's version returns the distance and the whole matrix:

edit_distance.py (a solution) Python

import numpy as np

def edit_distance(s1, s2):
    """
    Return the minimum edit distance between the two words
    """
    m = np.zeros((len(s1) + 1, len(s2) + 1), dtype=int)
    m[:, 0] = range(len(s1) + 1)     # delete every letter of s1
    m[0, :] = range(len(s2) + 1)     # insert every letter of s2
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            m[i, j] = min(m[i - 1, j] + 1,                            # delete s1[i-1]
                          m[i, j - 1] + 1,                            # insert s2[j-1]
                          m[i - 1, j - 1] + (s1[i - 1] != s2[j - 1]))  # replace or keep
    return m[-1, -1], m

print(edit_distance('sunday', 'saturday')[0])     # 3
print(edit_distance('elephant', 'relevant')[0])   # 3
print(edit_distance('lullaby', 'lollipop')[0])    # 5

Variants

Weighted edit distance: the cost of an operation depends on the characters involved, to capture keyboard errors (m is more likely mistyped as n than as q) or OCR errors (different weights). It needs a weight matrix as input; some literature treats the weight as the probability of the error.
Keeping a backtrack of the symbol alignments: store which neighbour each cell came from, then follow the arrows back from the last cell (the highlighted path above).
Only two rows: if no backtrack is needed, each row only depends on the previous one, so memory drops from $O(nm)$ to $O(2m)$.
Damerau–Levenshtein: also allow swapping two adjacent letters as one edit. smtih → smith costs 1 instead of 2 (try it with transpositions on).

Some implementations

pyxDamerauLevenshtein: Damerau–Levenshtein distance in Cython, for speed.
Peter Norvig's spelling corrector: generate every string at edit distance 1 and 2 from the word, keep those that are real words, and pick the most probable one (a language model, with priority to fewer edits). It can include an error model, e.g. from lists of common errors (aspell test data).
TextBlob: contains a spellchecker trained on text (from Project Gutenberg), based on Norvig's idea. In the notebook: TextBlob("I havv goood speling!").correct() gives I have good spelling!
Corpora of real misspellings, for testing: Roger Mitton's collection.

libraries.py Python

# pip install textblob pyxDamerauLevenshtein
from textblob import TextBlob
blob = TextBlob("I havv goood speling!")
print(blob.correct())   # I have good spelling!   (the notebook's output)

from pyxdameraulevenshtein import damerau_levenshtein_distance, normalized_damerau_levenshtein_distance
print(damerau_levenshtein_distance('smtih', 'smith'))              # one transposition: 1
print(normalized_damerau_levenshtein_distance('smtih', 'smith'))   # the distance scaled to [0, 1]

import nltk
print(nltk.jaccard_distance(set('mapping'), set('mappings')))      # 0.14285714285714285

Notebook + lecture

Finding candidates fast: n-gram overlap and tries

A problem with the edit distance approach: do we compute the edit distance from the query to every dictionary term? That is slow. We first cut the dictionary down to a few plausible candidates, and compute edit distances only for those.

Solution 1: a character n-gram index

Build a character n-gram index: n-gram → the words containing it (av → avocado, pavement, …), the same k-gram index as for wild-cards.
Retrieve the postings of every n-gram of the query and merge them, counting how many n-grams each word shares with the query.
Normalize: a raw count favours long words (car shares all its bigrams with carbon). Use the Jaccard coefficient of the two n-gram sets and declare a match above a threshold.
Then rank the candidates by edit distance (and, among equals, by how common the word is).

📐 Jaccard coefficient

For two sets $X$ and $Y$ (here: the n-grams of two words). It is 1 when the sets are equal and 0 when they are disjoint; the sets need not have the same size.

J(X, Y) = \frac{|X \cap Y|}{|X \cup Y|}

Lecture example with trigrams: november (nov, ove, vem, emb, mbe, ber) and december (dec, ece, cem, emb, mbe, ber) share 3 of 6 trigrams each, so $J = 3 / 9 \approx 0.33$.

💡 The postings scan only needs each term's number of n-grams, not the term itself: when scanning for bord reaches boardroom with 2 matching bigrams, and boardroom has 8 bigrams, $J = 2 / (8 + 3 - 2)$ (IIR 3.3.4). The lecture's example slide is titled "trigrams" but uses the bigrams of lord (lo, or, rd).

Try it: an n-gram spell-checker on the sci.crypt lexicon

The notebook's example enginering is the default. The table lists every word that shares at least one n-gram; words above the Jaccard threshold (0.7 in the notebook) are the candidates, ranked by edit distance, then by document frequency. For comparison, Norvig's method generates all strings one or two edits away.

Jaccard ≥0.70

Exercise 3: implement the n-gram overlap spell-checker and find the best Jaccard threshold for your dataset. A solution with the notebook's function names:

ngram_spellcheck.py (a solution) Python

from collections import defaultdict, Counter

def get_word_ngrams(word, n):
    return [word[i:i+n] for i in range(len(word)-n+1)]

def build_ngram_postings(n, tokenized_documents):
    """
    Create postings from the tokenized documents -
    For each n-gram we want to have the list of words, containing that n-gram. (E.g. av: [avocado, pavement, ...])
    """
    vocabulary = sorted({token for doc in tokenized_documents for token in doc})
    postings = defaultdict(list)
    for word in vocabulary:                        # each word once per n-gram
        for gram in set(get_word_ngrams(word, n)):
            postings[gram].append(word)
    return postings

def ngram_spellcheck(word, postings, n, jaccard_threshold=0.7):
    """Return the words from the postings structure, which are closest to the input word."""
    query = set(get_word_ngrams(word, n))
    shared = Counter()                             # merge the postings: word -> number of shared n-grams
    for gram in query:
        shared.update(postings.get(gram, []))
    scored = []
    for candidate, common in shared.items():
        size = len(set(get_word_ngrams(candidate, n)))
        jaccard = common / (len(query) + size - common)
        if jaccard >= jaccard_threshold:
            scored.append((candidate, jaccard))
    return sorted(scored, key=lambda x: -x[1])

# on the sci.crypt vocabulary (the lexicon of the widget above):
# ngram_spellcheck('enginering', postings, 2)  ->  [('engineering', 0.875), ('engineer', 0.75)]

💡 The notebook's output on rec.autos is [('engineering', 0.7647…), ('enginerring', 0.7647…)]. These scores are not the Jaccard coefficient of the two bigram sets (that is 0.875 for engineering), and its postings['ar'] lists das-news.harvard.edu twice, once per occurrence; the notebook's own solution counted differently. Note also that enginerring, itself a typo, is in the rec.autos lexicon.

Jaccard vs overlap coefficient

Exercise 5: we have two sets $A$ and $B$ with 50 words in common, and the combined set has 100 words. What is the Jaccard coefficient? Does it change if we remove 10 words from $A$ and add 10 to $B$, keeping the 50 shared words? Compare with the overlap coefficient, $|A \cap B| / \min(|A|, |B|)$.

$|A|$75

5Answer to Exercise 5.

Jaccard: $50 / 100 = 0.5$, and it does not change: moving 10 words from $A$ to $B$ keeps the intersection (50) and the union (100).

Overlap coefficient: $|A| + |B| = 100 + 50 = 150$. With $|A| = |B| = 75$ it is $50 / 75 \approx 0.67$; with $|A| = 65, |B| = 85$ it is $50 / 65 \approx 0.77$. It grows as the smaller set shrinks and reaches 1 when one set is contained in the other, however large the other is. Jaccard only looks at intersection and union, so it does not care how the rest is split.

Solution 2: tries

To correct lates we might compute the edit distance to late, latest and latte, and every time we recompute the rows for the common prefix lat. Store the whole vocabulary in a trie, where each node is one letter and its branches are the letters that can follow; then each prefix's row of the edit-distance table is computed once, and branches whose row is already above the limit are cut off (Steve Hanov's post).

Try it: edit distance on a trie

The lecture's five words. Each node shows the edit distance between its prefix and the query; a word ending is a double circle. Nodes whose whole row is above the limit are pruned (grey), with their subtrees.

limit2

Exercise 4: if you already know your project, build and tune your own spellchecker, maybe even one for Bulgarian. Choose an implementation and a list of words (TextBlob's spellchecker is trained on Gutenberg's data), run your corpus through it, find words that were "corrected" although they were spelled correctly, and add them to your word list. 💡 A Grammarly-like spelling and grammar corrector for Bulgarian can be a good course project; if you are interested, we can discuss how to collect data and approach the task.

Lecture

Context and choosing a suggestion

Isolated-word correction cannot fix flew form Heathrow: every word is spelled correctly. If the phrase query matches no documents, we would like to answer Did you mean "flew from Heathrow"?

First idea: for each query word, retrieve the dictionary terms close to it in (weighted) edit distance, then try the phrases with one word replaced at a time (flew from heathrow, fled form heathrow, flea form heathrow, …) and suggest the one with many hits. With 7 alternatives for flew, 19 for form and 3 for heathrow that is 7 + 19 + 3 = 29 phrases; trying every combination would be far more (8 · 20 · 4 = 640, counting each original word as an option).
Another approach: break the phrase into a conjunction of biwords (Lab 01), look for biwords that need only one term corrected, and keep only frequent ones (flew from rather than fled fore) before extending them to the next word.
Which suggestion to show? Many alternatives are enumerated for "Did you mean"; show one or a few. Heuristics: the alternative that hits the most documents, and query-log analysis for especially popular, topical queries.
Cost: spelling correction is computationally expensive. Run it only on queries that matched few documents, not routinely on every query.
Caveat: everything depends on what the index token is. In Chinese and Japanese, spelling correction and wild-cards are poorly defined.

Thesauri and query expansion

Thesaurus: a language-specific list of synonyms for terms likely to be queried (car → automobile); a hand-made alternative to edit distance. Machine learning can help build it.
Query expansion, not index expansion: rewrite the query rather than the index. No index blow-up, but query processing slows down. It may retrieve more junk: puma → jaguar retrieves documents about cars instead of sneakers.

Lecture

Soundex

Some misspellings come from typing a word as it sounds, mostly names: chebyshev vs tchebycheff. Soundex heuristics give every term a phonetic hash so that similar-sounding terms get the same code. Language specific, mainly for names.

Index: turn every token into a 4-character code and build an index from codes to terms; do the same with query terms, and search this index when the query asks for a Soundex match.
Why it works: vowels are treated as interchangeable when transcribing names, and consonants with similar sounds (like D and T) share a digit.

📐 Soundex, the typical algorithm

Keep the first letter of the word.
Change A, E, I, O, U, H, W, Y to 0.
Change letters to digits: B F P V → 1; C G J K Q S X Z → 2; D T → 3; L → 4; M N → 5; R → 6.
Repeatedly remove one out of each pair of consecutive identical digits.
Remove all zeros.
Pad with trailing zeros and return the first four positions: a letter and three digits. Herman becomes H655.

💡 Step 4 on the slide reads "remove all pairs of consecutive digits". It should be one of each pair of identical consecutive digits (IIR): Hermann → H 0 6 5 0 5 5 → H 0 6 5 0 5 → H655, the same code as Herman.

Try it: Soundex codes

Type names separated by commas; each row shows the steps. Names with the same code are grouped.

💡 Soundex keeps the first letter, so the lecture's own example does not match: chebyshev is C121 and tchebycheff is T212. Such rules depend on the writing system; for Chinese names in Wade-Giles vs Pinyin, Soundex maps both hs and x to 2 but maps j and r differently.

Big picture

Putting it together

We now have a basic inverted index with skip pointers, a wild-card index, spelling correction and Soundex. Together they can answer queries such as

(SPELL(moriset) /3 toron*to) OR SOUNDEX(chaikofski)

Language detection: many of these components need to know the language. For documents and paragraphs there is enough text for machine learning; for queries it is much harder, so add other cues (client settings, the domain the query comes from).
Results caching: if 25% of your users search for britney AND spears, you probably need spelling correction, but you do not need to keep intersecting those two postings lists. The web query distribution is extremely skewed, so caching results for common queries pays off.
Design choices: does stemming happen before the Soundex index? What about n-grams? How is a query parsed and dispatched to the different indexes?

Summary: key takeaways

Tolerant retrieval: map a query term to the dictionary terms the user meant, then run the normal query; correction needs a lexicon of correct words.
Wild-cards: B-trees for X* (and a reverse B-tree for *X); a permuterm index rotates any query so the * is at the end; a k-gram index answers with an AND of k-grams plus a post-filter.
Edit distance: insert, delete, replace; a dynamic-programming table in $O(|s_1| \cdot |s_2|)$; weighted, transposition and two-row variants.
Candidates: never compare the query with every term. Use an n-gram index and the Jaccard coefficient to shortlist, then rank by edit distance; a trie shares the work for common prefixes.
Context: fix one word at a time or use biwords, choose the suggestion with the most hits, and run correction only when a query finds little.
Soundex: a 4-character phonetic code (letter + 3 digits) for matching names that sound alike.

Tolerant Retrieval and Spelling Correction

Overview of the lab

Tolerant retrieval

Spelling correction: uses and flavors

Prerequisite: a list of words at hand

Wild-card queries

A * at the end or at the start: B-trees

Any *: the permuterm index

Any *: k-gram indexes

Try it: one wild-card query, three indexes

Try it: the permuterm vocabulary of a term

Finding the correct word: edit distance

Edit distance algorithm

Try it: fill the table

Variants

Some implementations

Finding candidates fast: n-gram overlap and tries

Solution 1: a character n-gram index

Try it: an n-gram spell-checker on the sci.crypt lexicon

Jaccard vs overlap coefficient

Solution 2: tries

Try it: edit distance on a trie

Context and choosing a suggestion

Thesauri and query expansion

Soundex

Try it: Soundex codes

Putting it together

Summary: key takeaways

A `*` at the end or at the start: B-trees

Any `*`: the permuterm index

Any `*`: k-gram indexes