## 4 Optimal Q-Gram Filter
### Optimal Count Q-Gram Filter for Edit Similarity
If equality holds, then all Q-grams could be destroyed, as the worst case scenario. **Corollary 8**. : _(Edit Similarity Singularity of Q-gram Filter) Let \(\alpha_{sing}\) be a singularity threshold of a Q-gram filter, where \(t_{\alpha}=0\)._  
\[\alpha_{sing}=\frac{2q|X|-|X|+q-1}{2q|X|+|X|-q+1}=\frac{2q|X|-|Q_{X}|}{2q|X|+| Q_{X}|}. \tag{37}\]  
Proof. : If we assume an unfractional part, then we have  
\[ \begin{split} d(\alpha,|X|,|Y|)&=d_{sing}(\alpha,|X |,|Y|),\\ \frac{1-\alpha}{1+\alpha}(|X|+|Y|)&=\frac{\sup\{|Q_{X }\cap Q_{Y}|\}}{q},\\ \frac{1-\alpha}{1+\alpha}&=\frac{\sup\{|Q_{X}\cap Q_{ Y}|\}}{q(|X|+|Y|)},\\ \alpha&=\frac{q(|X|+|Y|)-\sup\{|Q_{X}\cap Q_{Y}|\}}{ q(|X|+|Y|)+\sup\{|Q_{X}\cap Q_{Y}|\}}.\end{split}  \tag{38}\]  
This is proven by finding a root of the equation for \(\alpha\). If we assume the strings have equal lengths, then we can simplify this to  
\[\alpha=\frac{2q|X|-|Q_{X}|}{2q|X|+|Q_{X}|}=\frac{2q|X|-|X|+q-1}{2q|X|+|X|-q+1}. \tag{39}\]In other words, we should always select a threshold, \(\alpha\geq\alpha_{sing}\), for the corresponding token lengths, to have a working and efficient Q-gram filter that is capable of filtering any dissimilar records. **Corollary 9**. : _Shorter strings less than \(|X|<\left\lceil\frac{1+\alpha}{2-2\alpha}\right\rceil\) must have an exact match with size for all Q-grams \(|Q_{X}|\) for the Q-gram filter_  
\[|X|<\left\lceil\frac{1+\alpha}{2-2\alpha}\right\rceil\implies t_{\alpha}=|Q_{ X}|=|X|-q+1. \tag{40}\]  
Proof. : Thus, we show that a non-integer fractional part, \(d(\alpha,|X|,|Y|)<1\), leads to an exact match after applying the floor function, \(d(\alpha,|X|,|Y|)<1\implies\left\lfloor d(\alpha,|X|,|Y|)\right\rfloor=0\). \[\left\lfloor\frac{2|X|-2\alpha|X|}{\alpha+1}\right\rfloor <1, \tag{41}\] \[|X| <\left\lceil\frac{\alpha+1}{2-2\alpha}\right\rceil.\]  
Indeed, for \(d=1\) and \(\alpha=0.8\), we obtain \(|X|=5\). Shorter strings must always have \(s_{n}(X,Y)<\alpha\) for \(d>0\). A singularity of a Q-gram filter could cause performance problems on certain string lengths, \(|X|_{sing}\), due to generating a large candidate set. This property is demonstrated in Figure 4. To resolve this kind of problem, we should extend our model with at least 1 padding Q-gram, denoted by \(p\in\Sigma^{*}\). From nature, empirical observation, and some blocking techniques [28; 29; 30], increasing the importance of initial letters seems reasonable. For an initial solution, we could define a prefix or postfix '\(p=\#\)', or both of them for each token, and extend the Q-gram sets by about \(|Q_{X}|+|p|\) Q-grams. **Definition 9** (Q-gram Set with Padding). : _Let \(X\) be a string over the alphabet, \(\Sigma\), and \(p\in\Sigma^{*}\) be a padding string. The padded Q-gram set \(Q_{X,p}\) is obtained by extracting Q-grams from the concatenated string, \(p\cdot X\cdot p\)._  
Figure 4: Sawtooth function of different string lengths \(|X|\) and fixed \(q\) and \(\alpha\). The zero crossings of \(t_{\alpha}\) illustrate the singularities of the Q-gram filter. This is similar to the results in [54]. **Corollary 10** (Q-gram Filter with Padding). : _Let \(Q_{X}\) and \(Q_{Y}\) be \(Q\)-gram sets for strings \(X\) and \(Y\), and let \(p\) be a padding string. Then, for any normalized edit similarity threshold, \(s_{n}(X,Y)\geq\alpha\), and expected edit distance, \(d(\alpha,|X|,|Y|)>0\), the padded \(Q\)-gram similarity satisfies:_  
\[t_{a_{p}}=t_{\alpha}+|p| \tag{42}\]  
_where \(t_{\alpha}\) is the unpadded \(Q\)-gram similarity threshold and \(|p|\) is the length of the padding string._  
Proof. : For padded strings, \(X_{p}=p\cdot X\cdot p\) and \(Y_{p}=p\cdot Y\cdot p\):  
\[t_{a_{p}} =\max\{|X_{p}|,|Y_{p}|\}-q+1-qd(\alpha,|X|,|Y|)\] \[=\max\{|X|,|Y|\}+|p|-q+1-qd(\alpha,|X|,|Y|)\] \[=t_{\alpha}+|p|\]  
Note that padding characters do not affect the edit distance calculation \(d(\alpha,|X|,|Y|)\) between the original strings. The behavior of the Q-gram filters near the singularity points plays a fundamental role in their theoretical and practical performance.