ConceptDBISAI-written · not yet proofread

Q-Gram Lemma

The q-gram lemma states |Q_q(x) \ Q_q(y)| ≤ q · ED(x, y), so strings with small edit distance (or prefix edit distance) must share many q-grams, which gives a lower bound used to filter fuzzy-search candidates.

Know these firstQ-Gram Edit Distance

Formula#

With $\mathrm{comm}_q(x, y) := |Q_q(x) \cap Q_q(y)|$ the number of common q-grams:

Corollary 1 (ED).

\mathrm{comm}_q(x, y) \ge \max\{|Q_q(x)|, |Q_q(y)|\} - q \cdot \mathrm{ED}(x, y)

Corollary 2 (PED).

\mathrm{comm}_q(x, y) \ge |Q_q(x)| - q \cdot \mathrm{PED}(x, y)

Both also hold for consistently padded strings, with $|Q_q|$ counted on the padded strings (see Q-Gram > Padding).

ProofProof of the lemma

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

$\mathrm{ED}(x, y) = k$ : take an optimal sequence $x = x_0 \to x_1 \to \dots \to x_k = y$ with $\mathrm{ED}(x_{i-1}, x_i) = 1$ . For any sets $A_0, \dots, A_k$ ,

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

for $a \in A_0 \setminus A_k$ let $i \ge 1$ be the smallest index with $a \notin A_i$ ; then $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.

ProofProof of Corollary 1

$|A \setminus B| = |A| - |A \cap B|$ , so the lemma gives $|Q_q(x)| - \mathrm{comm}_q(x, y) \le q \cdot \mathrm{ED}(x, y)$ . Since ED is symmetric, the lemma for $(y, x)$ gives $|Q_q(y)| - \mathrm{comm}_q(x, y) \le q \cdot \mathrm{ED}(x, y)$ . Together: the max.

Properties#

Intuition: similar strings share many q-grams; more precisely, each edit operation “affects” at most $q$ q-grams.
The bounds give necessary conditions only: a word that meets the bound may still be far away, so (P)ED must be verified; a word that misses it is certainly not a match (no false negatives).
Reading it backwards gives a lower bound on ED: $\mathrm{ED}(x, y) \ge \bigl(\max\{|Q_q(x)|, |Q_q(y)|\} - \mathrm{comm}_q(x, y)\bigr) / q$ .
ED filter: given $x$ and $\delta$ , every $y$ with $\mathrm{ED}(x, y) \le \delta$ satisfies $\mathrm{comm}_q(x, y) \ge \max\{|Q_q(x)|, |Q_q(y)|\} - q \cdot \delta$ ; if not, $\mathrm{ED}(x, y) > \delta$ without computing it.

Application to PED Filtering#

Corollary 2 is the filter for fuzzy prefix search (Fuzzy Search): given the query $x$ and threshold $\delta$ ,

\mathrm{comm}_q(x, y) < |Q_q(x)| - q \cdot \delta \implies \mathrm{PED}(x, y) > \delta,

so $y$ can be pruned without computing $\mathrm{PED}(x, y)$ . Only the survivors are verified with the Prefix Edit Distance. With left-only padding, $|Q_q(x'')| = |x|$ , so the threshold is $|x| - q\delta$ . The counts $\mathrm{comm}_q(x, y)$ for all $y$ at once come from the Q-Gram Index.

ProofProof of Corollary 2

$\mathrm{PED}(x, y) = \mathrm{ED}(x, y')$ for some prefix $y'$ of $y$ . By the lemma, $|Q_q(x)| - \mathrm{comm}_q(x, y') \le q \cdot \mathrm{ED}(x, y') = q \cdot \mathrm{PED}(x, y)$ . Every q-gram of $y'$ is a q-gram of $y$ ( $Q_q(y) \supseteq Q_q(y')$ ), so $\mathrm{comm}_q(x, y) \ge \mathrm{comm}_q(x, y')$ .

Example#

$x = \text{freeburger}$ , $y = \text{breeurger}$ , $q = 2$ , $\mathrm{ED}(x, y) = 2$ (replace f→b, delete b):

$Q_2(x) = \{\text{fr}, \text{re}, \text{ee}, \text{eb}, \text{bu}, \text{ur}, \text{rg}, \text{ge}, \text{er}\}$ (9), $Q_2(y) = \{\text{br}, \text{re}, \text{ee}, \text{eu}, \text{ur}, \text{rg}, \text{ge}, \text{er}\}$ (8).
Lemma: $|Q_2(x) \setminus Q_2(y)| = |\{\text{fr}, \text{eb}, \text{bu}\}| = 3 \le 2 \cdot 2 = 4$ .
Corollary 1: $\mathrm{comm}_2(x, y) = 6 \ge \max\{9, 8\} - 2 \cdot 2 = 5$ .
Same strings with $q = 3$ : $|Q_3(x)| = 8$ , $|Q_3(y)| = 7$ , common $\{\text{ree}, \text{urg}, \text{rge}, \text{ger}\}$ , so $4 \ge 8 - 3 \cdot 2 = 2$ .

Corollary 2: $\mathrm{PED}(\text{bree}, \text{freeburger}) = 1$ and $\mathrm{comm}_2 = |\{\text{re}, \text{ee}\}| = 2 \ge 3 - 2 \cdot 1 = 1$ .

Exam WS 22/23, Task 2.2: two strings of length 5 with 3 common 3-grams (padding on both sides) have $|Q_3(x')| = |Q_3(y')| = 9 - 3 + 1 = 7$ , so $3 \ge 7 - 3 \cdot \mathrm{ED}(x, y)$ , i.e. $\mathrm{ED}(x, y) \ge 4/3$ , hence $\mathrm{ED}(x, y) \ge 2$ .

Sources#

Slides 08, pp. 17–18 (lemma and proof), p. 19 (Corollary 1), p. 20 (Corollary 2), p. 21 (filter algorithms)
DBIS_VL08 > The q-gram lemma, DBIS_VL08 > Corollaries: lower bounds on common q-grams, DBIS_VL08 > Filter algorithms
Slides 13, p. 20, DBIS_VL13 > Example Task: Q-Grams and Edit Distance (WS 22/23, Task 2.2, 5 points)
Exams: DBIS Exam WS1314 (not published) (Task 2.3), DBIS Exam WS1718 (not published) (Task 3), DBIS Exam WS1819 (not published) (Task 3.2), DBIS Exam WS2223 (not published) (Task 2.2), DBIS Exam WS2324 (not published) (Task 4.1)

Connections

Required by builds on this1

Fuzzy Search

Mentioned in inline links7

Edit Distance
A single operation sequence only proves an upper bound on ED; the exact value needs the DP table or a lower-bound argument (e.g. property 3, or the Q-Gram Lemma read backwards). §
Fuzzy Search
Filter with the q-gram lemma, Corollary 2: keep only words with §
Q-Gram Index
If $y$ occurs $k$ times in the merged result, then $\mathrm{comm}_q(x, y) = |Q_q(x) \cap Q_q(y)| = k$ . Words absent from the result have $\mathrm{comm}_q(x, y) = 0$ ; they only matter if the filter threshold of the Q-Gram Lemma is $\le 0$ . §
Q-Gram
Q-grams are a cheap proxy for string similarity: strings with a small Edit Distance agree “at many places” and therefore share many q-grams. The Q-Gram Lemma makes this precise (each edit operation affects at most $q$ q-grams). §
VL08 – Fuzzy Search, Prefix Edit Distance, Q-Gram Index
where $A \setminus B$ is the set difference (the elements of $A$ without those of $B$ ); if $B$ is very similar to $A$ , then $A \setminus B$ is small (Slides 17–18, Q-Gram Lemma). §
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 §
VL13 – Evaluation, Exam, Work in our Group
Slide 20. This task applies the Q-Gram Lemma from Fuzzy Search and Q-Grams. §
Q-Gram Lemma — gives the lower bound $\text{ED} \geq 2$ in WS 22/23 Task 2.2 §
Fuzzy Search and Q-Grams
Q-Gram Lemma — lower bound on common q-grams from ED / PED §
Speed-up: ED/PED for all of $D$ is a linear scan. The Q-Gram Lemma gives a necessary condition on the number of common q-grams, and the Q-Gram Index computes these counts for all words by merging $|Q_q(x)|$ lists. Only words passing the bo… §

Search in these mentions →