## 4 Optimal Q-Gram Filter
### Optimal Count Q-Gram Filter for Fuzzy Token Similarity
As a result, by employing a pre-built inverted Q-gram index that incorporates the distribution of ascending sorted lengths, a time complexity of \(\mathcal{O}(1)\) can be attained. **Theorem 11** (Q-gram Filter Efficiency). : _Let \(\alpha_{optim}\) be a minimal efficient threshold for a Q-gram filter to be effective at filtering dissimilar records for bipartite matching \(s_{n}(\mathcal{R}_{1},\mathcal{R}_{2})\geq\alpha\). Then,_  
\[\alpha_{optim}\geq\frac{2q-1}{2q+1}. \tag{61}\]  
From Equation (51), it follows that \(F_{X}[|\mathcal{M}|]\leq\sum_{i=1}^{|\mathcal{M}|}|X_{i}|\). So, we should prove that, in the ordered statistics, \(|X_{1}|\leq|X_{2}|,\ldots,|X_{m-1}|\leq|X_{\mathcal{M}}|\), we also have \(t_{X_{1}}\leq t_{X_{2}},\ldots,t_{X_{m-1}}\leq t_{X_{M}}\). We show that, for any \(|X_{i}|\) and \(|X_{j}|=|X_{i}|+1\), we have \(t_{X_{i}}\leq t_{X_{j}}\). Thus, we obtain the inequality  
\[ \begin{split}|X|-q+1-qd(\alpha,|X|,|X|)&\leq(|X|+1 )-q+1-qd(\alpha,|X|+1,|X|+1),\\ |X|-q+1-q\frac{2|X|-2\alpha|X|}{1+\alpha}&\leq(|X|+ 1)-q+1-q\frac{2(|X|+1)-2\alpha(|X|+1)}{1+\alpha},\\ -q\frac{2|X|-2\alpha|X|}{1+\alpha}&\leq 1-q\frac{2(|X|+1 )-2\alpha(|X|+1)}{1+\alpha},\\ 2|X|-2\alpha|X|&\geq 2(|X|+1)-2\alpha(|X|+1)-\frac{1+ \alpha}{q}\\ \alpha&\geq\frac{2q-1}{2q+1}.\end{split}  \tag{62}\]  
As derived previously in (8), the Q-gram filter works for \(\alpha\geq\alpha_{sing}\). If we put \(\alpha_{optim}=\frac{2q-1}{2q+1}\), then the convergence of this is obvious:  
\[\lim_{|X|\rightarrow\infty}\alpha_{sing}(|X|)=\alpha_{optim}. \tag{63}\]  
By evaluating the expression we obtain an effective Q-gram filter for bigram \(\alpha\geq 0.6\), for trigram \(\alpha\geq\frac{5}{9}\), and for fourgram \(\alpha\geq\frac{7}{9}\). The conditions for the minimum thresholds make sense for ordinary use in real applications and have great robustness to errors. Now, we incorporate in our previous model also a padding extension, which should further improve the efficiency of the filtering. **Theorem 12** (Optimal Q-gram Filter with Padding for Bipartite Matching). : _Let \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\) be records with token sets padded by string \(p\in\Sigma^{*}\). Thus, the Q-gram similarity in bipartite matching with cardinality \(|\mathcal{M}|\) for the threshold \(\alpha\) is given by_  
\[t_{M_{p}}=\inf_{\alpha,p}\{|Q_{\mathcal{R}_{1}}\cap Q_{\mathcal{R}_{2}}|\}=t_{ \mathcal{M}}+|\mathcal{M}||p| \tag{64}\]  
_where \(t_{\mathcal{M}}\) is the unpadded Q-gram similarity threshold._  
Proof. : Apply Corollary 10 to each matched token pair \((X_{i},Y_{j})\in\mathcal{M}\) and sum over all \(|\mathcal{M}|\) pairs:  
\[t_{M_{p}}=\sum_{(i,j)\in\mathcal{M}}(t_{\alpha}+|p|)=\sum_{(i,j)\in\mathcal{M} }t_{\alpha}+|\mathcal{M}||p|=t_{\mathcal{M}}+|\mathcal{M}||p|.\]  
**Corollary 11** (Approximate Lower Bound to Optimal Count Q-gram Filter with Padding for Bipartite Matching). : _Let \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\) be records representing a set of tokens, and let the total number of padding characters in the records \(\mathcal{R}_{1}\) and \(\mathcal{R}2\) be denoted as \(|p\mathcal{R}1|\) and \(|p\mathcal{R}_{2}|\), respectively. Then, the Q-gram similarity in bipartite matching of \(\mathcal{R}_{1}\), \(\mathcal{R}_{2}\) with cardinality \(N\) for a given threshold, \(\alpha\), is at least_  
\[t_{M_{p}}\approx\widehat{t}_{M_{p}}=\widehat{t}_{\mathcal{M}}+\min\{|p_{ \mathcal{R}_{1}}|,|p_{\mathcal{R}_{2}}|\}. \tag{65}\]  
Proof. : Similarly to the previous, use Corollary 10 and Theorem 10. The counting of the total padding characters per each record is due to the existence of tokens shorter than \(q\), where we do not append any padding characters, but only prolong the string to be at least of size \(q\) and so extract at least one Q-gram feature.