LectureDBISAI-written · not yet proofread

VL08 Fuzzy Search, Prefix Edit Distance, Q-Gram Index

Error-tolerant (prefix) search over a dictionary using edit distance, prefix edit distance, the q-gram lemma and its corollaries, and a q-gram index for fast candidate filtering.

Held Tue 9 Dec 2025 Source lecture-08

Summary

Fuzzy (prefix) search finds the names in a large dictionary that match a query despite typos, e.g. brei → freiburg. Relevance is modelled by the edit distance $\mathrm{ED}$ (computed by dynamic programming in $\Theta(|x| \cdot |y|)$ ) and, for search-as-you-type, by the prefix edit distance $\mathrm{PED}$ (minimum of the last row of the same table). Computing these for every dictionary word is too slow; the q-gram lemma $|Q_q(x) \setminus Q_q(y)| \le q \cdot \mathrm{ED}(x, y)$ and its corollaries give a lower bound on the number of common q-grams, which filters out most non-matches. A q-gram index (an inverted index from q-grams to word ids) computes these common counts for all words at once, so the expensive (P)ED is computed only for the few surviving candidates. This is ES8.

Organisation#

Fuzzy Search#

Problem setting#

Given a dictionary $D$ , a list of “names” of any kind (for ES8: 1,736,613 Wikidata entities), find the names from $D$ that match a query (Slide 5, Fuzzy Search):

Query	Match	Kind
`frei`	`freiburg`	prefix search
`breifurg`	`freiburg`	fuzzy search
`brei`	`freiburg`	fuzzy prefix search

The lecture solves the last two; normal prefix search is a special case. As in Lectures 1–2 there are two challenges:

a good model of relevance (what matches), here (P)ED,
an index to find the matches fast, here the q-gram index.

Possible origins of the dictionary (Slide 6): popular queries from a query log (basis of Google’s query suggestions); words and common phrases of a text collection (phrase extraction is a problem of its own, not covered); entities of a knowledge graph (ES8: Wikidata entities with popularity and synonyms).

Simple solution: linear scan#

Iterate over all strings of the dictionary and check each one (Slide 7). The command-line tools grep and agrep do this:

grep -x frei.* <file>          # -x: match whole line
agrep -x -2 breifurg <file>    # -2: allow up to 2 "errors"
agrep -x -2 brei.* <file>

This takes time linear in the size of the dictionary: good enough for medium-sized, not for large dictionaries. The rest of the lecture precomputes an index to do better.

Edit Distance#

Notation (Slide 9): $\varepsilon$ is the empty word, $|x|$ the length (number of characters) of $x$ , and $x[i..j]$ the substring from position $i$ to $j$ , $1 \le i \le j \le |x|$ . Below, $n := |x|$ and $m := |y|$ .

ProofProof sketches (the slides recommend proving these as exam preparation)

Every operation can be undone by one operation (insert ↔ delete, replace ↔ replace). Reversing an optimal sequence from $x$ to $y$ gives a sequence of the same length from $y$ to $x$ , so $\mathrm{ED}(y,x) \le \mathrm{ED}(x,y)$ , and vice versa.
$|x|$ deletions suffice. Each operation reduces the length by at most 1, so at least $|x|$ operations are needed.
Each operation changes the length by at most 1, and the length must change from $|x|$ to $|y|$ .
Apply an optimal sequence for $x[1..n-1] \to y[1..m-1]$ to the first $n-1$ characters of $x$ ; this leaves $x[n]$ as the last character. Then one replace turns $x[n]$ into $y[m]$ (or nothing is needed if $x[n] = y[m]$ ).

Recursive formula#

TheoremRecurrence for ED

For $|x| > 0$ and $|y| > 0$ , $\mathrm{ED}(x, y)$ is the minimum of

\begin{aligned} &(1)\quad \mathrm{ED}(x[1..n], y[1..m-1]) + 1 \\ &(2)\quad \mathrm{ED}(x[1..n-1], y[1..m]) + 1 \\ &(3a)\quad \mathrm{ED}(x[1..n-1], y[1..m-1]) + 1 \quad \text{if } x[n] \ne y[m] \\ &(3b)\quad \mathrm{ED}(x[1..n-1], y[1..m-1]) \quad\;\;\; \text{if } x[n] = y[m] \end{aligned}

For $|x| = 0$ : $\mathrm{ED}(x, y) = |y|$ . For $|y| = 0$ : $\mathrm{ED}(x, y) = |x|$ . (Slide 10)

Case (1) corresponds to inserting $y[m]$ at the end, (2) to deleting $x[n]$ , (3a) to replacing $x[n]$ by $y[m]$ , (3b) to keeping a matching last character.

Dynamic programming algorithm#

The recurrence leads to a DP algorithm: fill a table whose entry in row $i$ , column $j$ is $\mathrm{ED}(x[1..i], y[1..j])$ (rows: prefixes of $x$ , columns: prefixes of $y$ , row/column 0 = $\varepsilon$ ). Each entry depends only on its left, upper and upper-left neighbour. The result is the bottom-right entry (Slide 11).

Time and space: $\Theta(|x| \cdot |y|)$ .
Space $O(\min\{|x|, |y|\})$ also works: only the previous row is needed (row/column roles can be swapped).

Example $\mathrm{ED}(\text{BLOED}, \text{DOOF})$

	$\varepsilon$	D	O	O	F
$\varepsilon$	0	1	2	3	4
B	1	1	2	3	4
L	2	2	2	3	4
O	3	3	2	2	3
E	4	4	3	3	3
D	5	4	4	4	4

Every entry is the ED of two prefixes, e.g. $\mathrm{ED}(\varepsilon, \text{DOO}) = 3$ , $\mathrm{ED}(\text{B}, \text{DOOF}) = 4$ , $\mathrm{ED}(\text{BLO}, \text{DOO}) = 2$ , $\mathrm{ED}(\text{BLOE}, \text{DOOF}) = 3$ , and $\mathrm{ED}(\text{BLOED}, \text{DOOF}) = 4$ .

Prefix Edit Distance#

PED is the relevance model for fuzzy search-as-you-type suggestions; all large web search engines have this feature because it is so convenient. The entity search on wikidata.org does not have it.

Computation#

(Slide 13)

Compute the same table as for ED.
The PED is the minimum of the entries in the last row (instead of the bottom-right entry), since entry $(|x|, j)$ is $\mathrm{ED}(x, y[1..j])$ .
Optimization: if $|x| \ll |y|$ and we only want to know whether $\mathrm{PED}(x, y) \le \delta$ for a given threshold $\delta$ , it suffices to compute the first $|x| + \delta + 1$ columns (column $\varepsilon$ and the prefixes $y[1..j]$ for $j \le |x| + \delta$ ).

ProofWhy the first

|x| + \delta + 1

columns suffice

For $j > |x| + \delta$ , property 3 of ED gives $\mathrm{ED}(x, y[1..j]) \ge j - |x| > \delta$ . So no column to the right can contribute an entry $\le \delta$ to the last row: if $\mathrm{PED}(x, y) \le \delta$ , the minimum is attained among the first $|x| + \delta + 1$ columns, i.e. $\mathrm{PED}(x, y) = \mathrm{PED}(x, y[1..|x|+\delta])$ .

ExampleIs $\mathrm{PED}(\text{fibu}, \text{freiburg}) \le 2$ ?

Only the columns $\varepsilon$ , f, r, e, i, b, u ( $4 + 2 + 1 = 7$ ) are needed. The last row is

	$\varepsilon$	f	r	e	i	b	u	r	g
fibu	4	3	3	3	3	3	2	3	4

so $\mathrm{PED} = 2$ (attained at $y' = \text{freibu}$ ), e.g. $\mathrm{ED}(\text{fibu}, \text{fr}) = 3$ . The entries right of the cut (here 3, 4) are all $\ge 3$ and need not be computed.

Implementation for ES8#

The PED is performance-critical, so ES8 provides it (and merge_lists) ready-made: a Rust implementation (pip install ad-freiburg-qgram-utils) and a Python fallback; the code template uses Rust if installed (Slide 14).

Fuzzy Search with Q-Grams#

Motivation#

Goal: find fuzzy matches of $x$ in $D$ faster than by computing $\mathrm{ED}(x, y)$ or $\mathrm{PED}(x, y)$ for all $y \in D$ . Intuition: strings with a small edit distance overlap in many of their parts. $\mathrm{ED}(\text{freiburg}, \text{stuttgart})$ is large, the strings differ “everywhere”; $\mathrm{ED}(\text{freiburg}, \text{breifurg}) = 2$ is small, the strings agree “at many places” (Slide 15).

Q-grams#

The q-gram lemma#

Proof

Case $\mathrm{ED}(x, y) = 1$ : one edit operation changes at most $q$ q-grams (those that overlap the edited position), hence $|Q_q(x) \setminus Q_q(y)| \le q$ .

General case $\mathrm{ED}(x, y) = k$ : let $x = x_0 \to x_1 \to \dots \to x_k = y$ be a sequence of $k$ edit operations, so $\mathrm{ED}(x_{i-1}, x_i) = 1$ and therefore $|Q_q(x_{i-1}) \setminus Q_q(x_i)| \le q$ . It remains to show that for any sequence of sets $A_0, \dots, A_k$

A_0 \setminus A_k \subseteq \bigcup_{i=1}^{k} \bigl(A_{i-1} \setminus A_i\bigr).

Let $a \in A_0 \setminus A_k$ and let $i \ge 1$ be the smallest index with $a \notin A_i$ (it exists because $a \notin A_k$ ). Then $a \in A_{i-1}$ , so $a \in A_{i-1} \setminus A_i$ . With $A_i := Q_q(x_i)$ :

|Q_q(x) \setminus Q_q(y)| \le \sum_{i=1}^{k} |Q_q(x_{i-1}) \setminus Q_q(x_i)| \le k \cdot q.

(The last step after the inclusion is the usual completion; the slides end with the inclusion.)

Corollaries: lower bounds on common q-grams#

Proof

For arbitrary sets $A, B$ : $|A \setminus B| = |A| - |A \cap B|$ . With the lemma:

|Q_q(x)| - |Q_q(x) \cap Q_q(y)| = |Q_q(x) \setminus Q_q(y)| \le q \cdot \mathrm{ED}(x, y).

Since $\mathrm{ED}(x, y) = \mathrm{ED}(y, x)$ , the lemma applied to $(y, x)$ gives

|Q_q(y)| - |Q_q(x) \cap Q_q(y)| = |Q_q(y) \setminus Q_q(x)| \le q \cdot \mathrm{ED}(y, x).

Both inequalities together give the corollary.

ProofProof sketch

$\mathrm{PED}(x, y) = \mathrm{ED}(x, y')$ for some prefix $y'$ of $y$ . As for Corollary 1:

|Q_q(x)| - |Q_q(x) \cap Q_q(y')| = |Q_q(x) \setminus Q_q(y')| \le q \cdot \mathrm{ED}(x, y') = q \cdot \mathrm{PED}(x, y).

Since $Q_q(y) \supseteq Q_q(y')$ , we have $|Q_q(x) \cap Q_q(y)| \ge |Q_q(x) \cap Q_q(y')|$ , which gives the corollary.

Filter algorithms#

For a fixed $q \in \mathbb{N}$ (Slide 21):

ED. Given $x$ and a threshold $\delta$ , find all $y \in D$ with $\mathrm{ED}(x, y) \le \delta$ . For each $y \in D$ :

Is $|Q_q(x) \cap Q_q(y)| \ge \max\{|Q_q(x)|, |Q_q(y)|\} - q \cdot \delta$ ?
No → by Corollary 1, $\mathrm{ED}(x, y) > \delta$ , so $y$ is not a match.
Yes → compute $\mathrm{ED}(x, y)$ to decide whether $y$ is a match.

PED. Given $x$ and $\delta$ , find all $y \in D$ with $\mathrm{PED}(x, y) \le \delta$ : the same, with the test $|Q_q(x) \cap Q_q(y)| \ge |Q_q(x)| - q \cdot \delta$ (Corollary 2).

The filter has no false negatives; it only saves the (P)ED computations for the words it rules out.

Padding#

(Slide 22)

	Padding	Example ( $q = 3$ )	Why it is correct
ED	$q-1$ times `$` on both sides	`freiburg` → `$$freiburg$$`	for padded $x', y'$ : $\mathrm{ED}(x, y) = \mathrm{ED}(x', y')$
PED	$q-1$ times `$` on the left side only	`freiburg` → `$$freiburg`	for padded $x'', y''$ : $\mathrm{PED}(x'', y'') = \mathrm{PED}(x, y)$

The algorithm gives the same result with padding, and padding is an improvement: it yields more q-grams (including distinctive ones for the word boundaries), so step 2 of the filter applies more often.

Q-Gram Index#

Motivation#

The filter algorithm needs $|Q_q(x) \cap Q_q(y)|$ for a given $x$ and all $y \in D$ ; for ES8, $D$ contains 1.7 million strings. This is done efficiently with a q-gram index (Slide 23).

Definition#

DefinitionQ-gram index

For each q-gram of a string from $D$ , store an inverted list of all strings from $D$ that contain it, sorted lexicographically. As usual, store the ids of the strings, not the strings themselves (Slide 24, Q-Gram Index).

$fr : frankfurt, freiburg, freetown, fresno, …
ibu : chicibu, freiburg, ibusuki, malibu, …

A q-gram index is an Inverted Index with different objects than a document index:

document index: for each word, a list of document ids,
q-gram index: for each q-gram, a list of word ids.

Accordingly, the code from Lecture 1 carries over almost unchanged (lecture code public/code/lecture-08/qgram_index.py):

def q_grams(self, x: str) -> list[str]:
    x = self.padding + x + self.padding        # padding = "$" * (q - 1)
    return [x[i : i + self.q] for i in range(len(x) - self.q + 1)]

def build_from_file(self, file_name: str):
    with open(file_name, "r") as file:
        word_id = 0
        for line in file:
            word_id += 1
            word = line.split("\t", 2)[0].lower()
            for q_gram in self.q_grams(word):
                if q_gram not in self.inverted_lists:
                    self.inverted_lists[q_gram] = []
                self.inverted_lists[q_gram].append(word_id)

Using the index#

For the (appropriately padded) input $x$ (Slide 25):

Compute $Q_q(x)$ .
For each q-gram of $Q_q(x)$ , fetch its inverted list.
Compute the union of these $|Q_q(x)|$ inverted lists and count how often each word occurs.

If a word $y$ occurs $k$ times in the union, it contains exactly $k$ q-grams of $Q_q(x)$ , hence $|Q_q(x) \cap Q_q(y)| = k$ . Words that do not occur in the union at all have $|Q_q(x) \cap Q_q(y)| = 0$ ; they are only relevant if the right-hand side of the filter test (step 1 on Slide 21) is $\le 0$ .

Example $x = \text{brei}$ , $\delta = 1$ , 2-gram index, PED

Padded: $brei → q-grams $b, br, re, ei, so $|Q_2(x)| = 4$ (Slide 26).

$b : bangalore, beijing, berlin, …
br : brisbane, brussels, gibraltar, …
re : bangalore, freiburg, singapore, …
ei : beijing, freiburg, marseille, …

By Corollary 2, every $y$ with $\mathrm{PED}(x, y) \le 1$ needs $|Q_2(x) \cap Q_2(y)| \ge 4 - 2 \cdot 1 = 2$ . Merging the lists, these words occur (at least) twice: bangalore, beijing, freiburg. Only they are checked; for all others $\mathrm{PED}(x, y) > 1$ is already known. $\mathrm{PED}(\text{brei}, \text{bangalore}) = 3$ ✗, $\mathrm{PED}(\text{brei}, \text{beijing}) = 1$ ✓, $\mathrm{PED}(\text{brei}, \text{freiburg}) = 1$ ✓.

The complete fuzzy prefix search (Fuzzy Search): left-pad $x$ , fetch and merge the inverted lists of its q-grams, keep the words with at least $|Q_q(x)| - q \cdot \delta$ occurrences, and compute PED only for those. The filter phase takes time linear in the total length of the fetched inverted lists, which is typically much smaller than computing PED for every word.

References#

Course textbook, Section 3 “Tolerant Retrieval”, in particular 3.2 (wildcard queries) and 3.3 (spelling correction); Wikipedia on N-gram, approximate string matching and Levenshtein distance (Slide 27).

Concepts#

Fuzzy Search — problem setting (fuzzy and fuzzy prefix search over a dictionary) and the overall filter-then-verify algorithm
Edit Distance — relevance model for fuzzy search; definition, properties, recurrence, $\Theta(|x| \cdot |y|)$ DP
Prefix Edit Distance — relevance model for search-as-you-type; min of the last DP row, $|x| + \delta + 1$ column cut-off
Q-Gram — multiset $Q_q(x)$ of length- $q$ substrings, $|x| - q + 1$ elements, padding
Q-Gram Lemma — $|Q_q(x) \setminus Q_q(y)| \le q \cdot \mathrm{ED}(x, y)$ and Corollaries 1 (ED) and 2 (PED) as filter bounds
Q-Gram Index — inverted lists from q-grams to word ids; merging them yields all common-q-gram counts
Inverted Index — the q-gram index is an inverted index over q-grams instead of words
Dynamic programming — technique behind the ED/PED table
Q-gram padding — $-padding (both sides for ED, left only for PED) that sharpens the filter