## 4 Optimal Q-Gram Filter
### Optimal Count Q-Gram Filter for Fuzzy Token Similarity  
In this generalization, we consider the records \(\mathcal{R}_{1},\mathcal{R}_{2}\), consisting of token sets that are matched in a bipartite graph. As mentioned previously, \(|\mathcal{M}|\) is the resulting maximum edge-connected pair token for the optimal combinatorial assignment problem. We assume that the only known factors are the matching token pairs given by \(\mathcal{M}\), with unknown edit distances, but we can predict them in accordance with the expected edit distances. It can be very confusing that the edit distances are unknown while this model assumes a known matching \(\mathcal{M}\), which is calculated on the adjacency matrix. Building such a model has aquite tricky reason, which we may express as a model depending on threshold \(\alpha\) and token lengths of \(X_{i}\in\mathcal{R}_{1}\) and \(Y_{j}\in\mathcal{R}_{2}\). We formulate this generalization in the following. **Theorem 9** (Optimal Count Q-gram Filter for Bipartite Matching [57; 58]). : _Let \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\) be records representing a set of tokens. Then, the Q-gram similarity in bipartite matching of \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\), and cardinality, \(|\mathcal{M}|\), for a given threshold, \(s_{n}(\mathcal{R}_{1},\mathcal{R}_{2})\geq\alpha\), is at least_  
\[t_{\mathcal{M}}=\inf_{\alpha}\{|Q_{\mathcal{R}_{1}}\cap Q_{ \mathcal{R}_{2}}|\}=\] \[\sum_{ \begin{subarray}{c}(i,j)\in M\\ \text{maximum shared Q-grams}\end{subarray} }-q\underbrace{\max_{\alpha}\sum_{ \begin{subarray}{c}(i,j)\in M\\ \text{loss function}\end{subarray} }d(\alpha_{i,j},|X_{i}|,|Y_{j}|)}_{\text{ loss function}}, \tag{45}\]  
_containing a linear combination of_  
\[d(\alpha_{i,j},|X_{i}|,|Y_{j}|)=\frac{1-\alpha_{i,j}}{1+\alpha_{i,j}}(|X_{i}|+|Y_{j}|) \tag{46}\]  
_under the constraint \(\alpha=\frac{\sum_{ \begin{subarray}{c}(i,j)\in M\\ \text{$|\mathcal{M}|$}\end{subarray} }\alpha_{i,j}}{|\mathcal{M}|}\) for which the linear combination is maximized._  
Proof. : From (31), consider the sum over connected pairs of tokens with cardinality \(|\mathcal{M}|\)  
\[ \begin{split}&\inf_{\alpha}\{|Q_{\mathcal{R}_{1}}\cap Q_{ \mathcal{R}_{2}}|\}\\ &=\inf_{\alpha}\Bigg{\{}\sum_{(i,j)\in M}|Q_{X_{i}}\cap Q_{Y_{i}}| \Bigg{\}}=\sum_{(i,j)\in M}\inf_{\alpha_{i,j}}\{|Q_{X_{i}}\cap Q_{Y_{j}}|\}\\ &=\sum_{(i,j)\in M}\inf_{\alpha_{i,j}}\{\max\{|X_{i}|,|Y_{j}|\}-q +1-qd(X,Y)\}\\ &=\sum_{(i,j)\in M}\{\max\{|X_{i}|,|Y_{j}|\}-q+1-q\sup_{\alpha_{i,j}}d(X,Y)\}\\ &=\sum_{(i,j)\in M}\{\max\{|X_{i}|,|Y_{j}|\}-q+1-qd(\alpha_{i,j}, |X_{i}|,|Y_{j}|)\}.\end{split}  \tag{47}\]  
Each \(\alpha_{i,j}\) is the distributed minimum similarity for each token, giving a threshold vector that should maximize the sum of the expected distances \(d(\alpha_{i,j},|X_{i}|,|Y_{j}|)\), so that \(s_{n}(\mathcal{R}_{1},\mathcal{R}_{2})\geq\alpha=\frac{\sum_{(i,j)\in M} \alpha_{i,j}}{|\mathcal{M}|}\) holds for \(t_{M}\). Formalizing this, we obtain the integer linear programming task  
\[ \begin{split}\text{maximize}&\sum_{(i,j)\in M}d( \alpha_{i,j},|X_{i}|,|Y_{j}|),\\ \text{subject to}&\sum_{(i,j)\in M}\alpha_{i,j}\geq \alpha|\mathcal{M}|\qquad\alpha\in[0,1],\qquad i=1,\ldots,|\mathcal{M}|,\\ &\alpha_{i,j}\in[0,1],\quad j=1,\ldots,|\mathcal{M}|.\end{split} \]  
After a small reformulation, this leads to the well-known and well-solvable knapsack problem. The optimization can be reduced to a knapsack problem and solved using dynamic programming with complexity \(\mathcal{O}(nb)\), where \(n\) is the number of items and \(b\) is the capacity. While this appears polynomial, it is actually pseudo-polynomial, since the true input size depends on \(\log_{2}b\) rather than \(b\) directly [59]. This distinction is important as the algorithm's runtime depends on the magnitude of the numbers involved, not just their bit length.