Study Vault Search notes, aliases and full text
Study Vault
Graph
On this page
Connections ↓
TopicDBISAI-written · not yet proofread

Fuzzy Search and Q-Grams

Error-tolerant (prefix) search over a dictionary with edit distance and prefix edit distance, made fast by filtering candidates with the q-gram lemma and a q-gram index.

Concepts#

  1. Fuzzy Searchthe problem and the filter-then-verify algorithm start here
  2. Edit Distancerelevance model for whole words, Θ(∣x∣∣y∣)\Theta(|x||y|) DP
  3. Prefix Edit Distancerelevance model for search-as-you-type, minimum of the last DP row
  4. Q-Gramlength-qq substrings, with padding
  5. Q-Gram Lemmalower bound on common q-grams from ED / PED
  6. Q-Gram Indexinverted lists from q-grams to word ids, yields all common counts

How it fits together#

Two challenges, as for keyword search: relevance (what matches) and an index (find it fast).

  1. Relevance: ED for fuzzy search, PED for fuzzy prefix search; PED is computed from the same table as ED.
  2. Speed-up: ED/PED for all of DD 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 ∣Qq(x)∣|Q_q(x)| lists. Only words passing the bound are verified.
  3. Padding must match the distance, otherwise the bound or the distance changes.
Fuzzy search (ED)Fuzzy prefix search (PED)
MatchesED(x,y)≤δ\mathrm{ED}(x,y) \le \deltaPED(x,y)≤δ\mathrm{PED}(x,y) \le \delta
Paddingq−1q-1 $ on both sidesq−1q-1 $ on the left only
Filtercommq≥max⁡{∣Qq(x)∣,∣Qq(y)∣}−qδ\mathrm{comm}_q \ge \max\{\lvert Q_q(x)\rvert, \lvert Q_q(y)\rvert\} - q\deltacommq≥∣Qq(x)∣−qδ\mathrm{comm}_q \ge \lvert Q_q(x)\rvert - q\delta
VerifyDP, bottom-right entryDP, min of last row, first ∣x∣+δ+1\lvert x\rvert+\delta+1 columns
Index size∑i(∣vi∣+q−1)\sum_i (\lvert v_i\rvert + q - 1)∑i∣vi∣\sum_i \lvert v_i\rvert

Typical traps: PED is not symmetric and has no length lower bound; right padding breaks PED; no padding stays correct but filters less.

Key Formulas#

  • Recurrence and DP of Edit Distance; PED(x,y)=min⁡jM[∣x∣][j]\mathrm{PED}(x,y) = \min_j M[\lvert x\rvert][j].
  • ∣Qq(x)∣=∣x∣−q+1\lvert Q_q(x)\rvert = \lvert x\rvert - q + 1 (Q-Gram).
  • ∣Qq(x)∖Qq(y)∣≤q⋅ED(x,y)\lvert Q_q(x) \setminus Q_q(y)\rvert \le q\cdot\mathrm{ED}(x,y) and its corollaries (Q-Gram Lemma).

Exercises & Exam Questions#

SuccessSolution

3.1 Padded: $abba (1), $bab (2), $aba (3).

2-gramInverted list
$a1, 3
$b2
ab1, 2, 3
ba1, 2, 3
bb1

3.2 x′=x' = $aaab, 2-grams $a, aa, aa, ab. Lookups: $a → {1, 3}, aa → none, ab → {1, 2, 3}. Counts: abba 2, bab 1, aba 2. Threshold ∣x′∣−qδ=4−2=2|x'| - q\delta = 4 - 2 = 2, so candidates abba and aba. PED(aaab,abba)=2>1\mathrm{PED}(\text{aaab}, \text{abba}) = 2 > 1 and PED(aaab,aba)=2>1\mathrm{PED}(\text{aaab}, \text{aba}) = 2 > 1: no word matches.

SuccessSolution

ED=2\mathrm{ED} = 2: replace f → p, insert h. Q3($$alfa$$)={$$a,$al,alf,lfa,fa$,a$$}Q_3(\texttt{\$\$alfa\$\$}) = \{\texttt{\$\$a}, \texttt{\$al}, \text{alf}, \text{lfa}, \texttt{fa\$}, \texttt{a\$\$}\}, Q3($$alpha$$)={$$a,$al,alp,lph,pha,ha$,a$$}Q_3(\texttt{\$\$alpha\$\$}) = \{\texttt{\$\$a}, \texttt{\$al}, \text{alp}, \text{lph}, \text{pha}, \texttt{ha\$}, \texttt{a\$\$}\}. Common: {$$a,$al,a$$}\{\texttt{\$\$a}, \texttt{\$al}, \texttt{a\$\$}\} (3). Check with the lemma: 3≥6−3⋅2=03 \ge 6 - 3\cdot 2 = 0.

SuccessSolution
  1. True. yy is a prefix of itself.
  2. False. PED(br,breisgau)=0\mathrm{PED}(\text{br}, \text{breisgau}) = 0, but ∣∣x∣−∣y∣∣=6\bigl||x|-|y|\bigr| = 6.
  3. True. Padding only affects filter efficiency: more false candidates pass, so more PED computations.
  4. False. Right padding changes PED: PED($$br$$,$$breisgau$$)=2≠0\mathrm{PED}(\texttt{\$\$br\$\$}, \texttt{\$\$breisgau\$\$}) = 2 \ne 0.

Exam occurrences#

SemesterTaskPointsSubtopics
DBIS Exam WS1314 (not published)Task 220PED, comm2, proof for PED=1
DBIS Exam WS1516 (not published)Task 653-gram padding purpose
DBIS Exam WS1617 (not published)Task 653-gram inverted list formula
DBIS Exam WS1718 (not published)Task 320ED, PED, q-gram bound, valid_utf8_char
DBIS Exam WS1819 (not published)Task 3202-gram index, PED filtering, fuzzy_prefix_search
DBIS Exam WS2122 (not published)Task 325SPARQL, PED function, PED proof
DBIS Exam WS2223 (not published)Task 220ED(alfa,alpha), q-gram common count, one_delete
DBIS Exam WS2324 (not published)Task 4203-gram analysis, PED true/false, HTML forms
DBIS Exam WS2324-2 (not published)Task 4202-gram index with counts, PED true/false

Lectures#

  • DBIS_VL08 — fuzzy search, ED, PED, q-grams, q-gram lemma, q-gram index
  • DBIS_VL13 — exam example task on q-grams and edit distance (WS 22/23, Task 2.2)

Search

Type In
↑ ↓ move ↵ open ⇥ next section Ctrl↵ results page Prefix # to search text only