Definition
For a string x x x q ∈ N q \in \mathbb{N} q ∈ N q-gram of x x x x x x q q q multiset of q-grams is
Q q ( x ) = { x [ i . . i + q − 1 ] : 1 ≤ i ≤ ∣ x ∣ − q + 1 } , Q_q(x) = \{\, x[i..i+q-1] : 1 \le i \le |x| - q + 1 \,\}, Q q ( x ) = { x [ i .. i + q − 1 ] : 1 ≤ i ≤ ∣ x ∣ − q + 1 } , counted with multiplicity (the same q-gram may occur several times).
∣ Q q ( x ) ∣ = ∣ x ∣ − q + 1 ( ∣ x ∣ ≥ q ) . |Q_q(x)| = |x| - q + 1 \qquad (|x| \ge q). ∣ Q q ( x ) ∣ = ∣ x ∣ − q + 1 ( ∣ x ∣ ≥ q ) . With q − 1 q - 1 q − 1 ∣ Q q ( x ′ ′ ) ∣ = ∣ x ∣ |Q_q(x'')| = |x| ∣ Q q ( x ′′ ) ∣ = ∣ x ∣ q − 1 q - 1 q − 1 ∣ Q q ( x ′ ) ∣ = ∣ x ∣ + q − 1 |Q_q(x')| = |x| + q - 1 ∣ Q q ( x ′ ) ∣ = ∣ x ∣ + q − 1
Properties# 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 q Intersections and differences are taken as multisets, e.g. Q 3 ( ababa ) = { aba , bab , aba } Q_3(\text{ababa}) = \{\text{aba}, \text{bab}, \text{aba}\} Q 3 ( ababa ) = { aba , bab , aba } aba twice. c o m m q ( x , y ) : = ∣ Q q ( x ) ∩ Q q ( y ) ∣ \mathrm{comm}_q(x, y) := |Q_q(x) \cap Q_q(y)| comm q ( x , y ) := ∣ Q q ( x ) ∩ Q q ( y ) ∣ Padding# Before extracting q-grams, the strings are padded with q − 1 q - 1 q − 1 $ that does not occur in the strings. Padding yields more q-grams, including distinctive ones for the word boundaries, so the q-gram filter rules out more non-matches; the filter result stays correct.
Padding Example (q = 3 q = 3 q = 3 Use Why it is correct q − 1 q-1 q − 1 $ on both sides $$freiburg$$ED searchfor padded x ′ , y ′ x', y' x ′ , y ′ E D ( x , y ) = E D ( x ′ , y ′ ) \mathrm{ED}(x, y) = \mathrm{ED}(x', y') ED ( x , y ) = ED ( x ′ , y ′ ) q − 1 q-1 q − 1 $ on the left only $$freiburgPED (prefix) searchfor padded x ′ ′ , y ′ ′ x'', y'' x ′′ , y ′′ P E D ( x ′ ′ , y ′ ′ ) = P E D ( x , y ) \mathrm{PED}(x'', y'') = \mathrm{PED}(x, y) PED ( x ′′ , y ′′ ) = PED ( x , y ) none freiburgboth still correct, but fewer distinctive q-grams, weaker filter right side (alone or with left)freiburg$$— invalid for PED : changes PED values
! No right padding for PED
Right padding appends $ to the query, which the matching prefix y ′ y' y ′ P E D ( frei$$ , freiburg$$ ) = 2 \mathrm{PED}(\texttt{frei\$\$}, \texttt{freiburg\$\$}) = 2 PED ( frei$$ , freiburg$$ ) = 2 P E D ( frei , freiburg ) = 0 \mathrm{PED}(\text{frei}, \text{freiburg}) = 0 PED ( frei , freiburg ) = 0 P E D ( $$br$$ , $$breisgau$$ ) = 2 ≠ 0 \mathrm{PED}(\texttt{\$\$br\$\$}, \texttt{\$\$breisgau\$\$}) = 2 \ne 0 PED ( $$br$$ , $$breisgau$$ ) = 2 = 0
Example# Q 3 ( freiburg ) = { fre , rei , eib , ibu , bur , urg } Q_3(\text{freiburg}) = \{\text{fre}, \text{rei}, \text{eib}, \text{ibu}, \text{bur}, \text{urg}\} Q 3 ( freiburg ) = { fre , rei , eib , ibu , bur , urg } 8 − 3 + 1 = 6 8 - 3 + 1 = 6 8 − 3 + 1 = 6
Left-padded (q = 3 q = 3 q = 3 Q 3 ( $$freiburg ) = { $$f , $fr , fre , rei , eib , ibu , bur , urg } Q_3(\texttt{\$\$freiburg}) = \{\texttt{\$\$f}, \texttt{\$fr}, \text{fre}, \text{rei}, \text{eib}, \text{ibu}, \text{bur}, \text{urg}\} Q 3 ( $$freiburg ) = { $$f , $fr , fre , rei , eib , ibu , bur , urg } 8 = ∣ freiburg ∣ 8 = |\text{freiburg}| 8 = ∣ freiburg ∣
Both sides (q = 3 q = 3 q = 3 Q 3 ( $$alfa$$ ) = { $$a , $al , alf , lfa , fa$ , a$$ } Q_3(\texttt{\$\$alfa\$\$}) = \{\texttt{\$\$a}, \texttt{\$al}, \text{alf}, \text{lfa}, \texttt{fa\$}, \texttt{a\$\$}\} Q 3 ( $$alfa$$ ) = { $$a , $al , alf , lfa , fa$ , a$$ } Q 3 ( $$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\$\$}\} Q 3 ( $$alpha$$ ) = { $$a , $al , alp , lph , pha , ha$ , a$$ } { $$a , $al , a$$ } \{\texttt{\$\$a}, \texttt{\$al}, \texttt{a\$\$}\} { $$a , $al , a$$ }
Sources# Slides 08, p. 15 (motivation), p. 16 (definition), p. 22 (padding)DBIS_VL08 > Q-grams , DBIS_VL08 > Padding DBIS_VL13 > Example Task: Q-Grams and Edit Distance (WS 22/23, Task 2.2, 5 points) Exams: DBIS Exam WS1516 (not published) (Task 6, purpose of padding), DBIS Exam WS2223 (not published) (Task 2.1), DBIS Exam WS2324 (not published) (Tasks 4.1, 4.2)