## 4 Optimal Q-Gram Filter
### Optimal Count Q-Gram Filter for Fuzzy Token Similarity
In other words, we can simply ask how the maximum expected edit distance can be allocated across tokens, so that there will be at least \(s_{n}(\mathcal{R}_{1},\mathcal{R}_{2})\geq\alpha\) for records \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\). The above optimization algorithm should answer such a question. Note that this is not a completely trivial task, because greater distance allocation will be in larger tokens. This means that the error \(\epsilon_{ij}=1-\alpha_{i,j}\) will be distributed first on the longest tokens to achieve the maximum sum of distances, \(d(\alpha_{i,j},|X_{i}|,|Y_{j}|)\), where \(\alpha_{i,j}\) are variables depending on the lengths of the tokens. For the sake of exposition, we explain two terms of the optimal Q-gram filter equation. The term _maximum shared Q-grams_ counts the maximum possible number of shared Q-grams, \(|\mathcal{Q}_{\mathcal{R}_{1}}\cap\mathcal{Q}_{\mathcal{R}_{2}}|\), that could be achieved with tokens with corresponding lengths, \(|X_{i}|,|Y_{j}|\), given by the resulting matching set of \(\mathcal{M}\) on the complete bipartite graph. In fact, this term is simple because it counts only the Q-grams across matching token pairs \(|X_{i}|\) and \(|Y_{j}|\). The most crucial term is the _loss function_, which must be maximized for an unknown expected distance distribution of the tokens employing a user-defined global threshold, \(\alpha\). Table 1 (bottom) contains a complete list of the constraints previously imposed on the integer linear programming problem as well as the fuzzy token similarity functions that have been introduced. Note that, in previous publications, this task was simplified: there was no consideration of the dependence of \(t_{\mathcal{M}}\) on variables such as the length of the Q-gram \(q\) and the lengths of the tokens \(|X_{i}|\)\(|Y_{j}|\). The derived model solves it for optimality and cannot be further improved. A naive approximation would be to assume the constancy of \(\alpha_{i,j}=\alpha\), which actually performs an average distance allocation among the tokens. This is the approximation of the optimal lower bound Q-gram pairs for maximum weight matching in a bipartite graph. We note the fact that \(X_{i}\) and \(Y_{i}\) are connected by a resulting edge. However, we can not predict which tokens will be matched on the bipartite graph, and so cannot predict their lengths. **Theorem 10** (Approximate Count Q-gram Filter). : _Let \(F_{\mathcal{R}_{1}}\) and \(F_{\mathcal{R}_{2}}\) be discrete distribution functions representing the ascending sorted lengths \(|X_{i}|\) and \(|Y_{i}|\), respectively. Let \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\) be sets of records with unknown edge connections and let \(\mathcal{M}\) denote the set of matched record pairs with cardinality, \(|\mathcal{M}|\). Under the assumption of constant similarity \(\alpha_{i,j}=\alpha\) for all \((i,j)\), the Q-gram similarity in bipartite matching satisfies the following:_  
\[\widehat{t}_{\mathcal{M}} = \frac{2q\alpha+\alpha-2q+1}{2+\alpha}\big{(}F_{\mathcal{R}_{1}}[ |\mathcal{M}|]+F_{\mathcal{R}_{2}}[|\mathcal{M}|]\big{)}+ \tag{48}\] \[+\frac{1}{2}\big{|}F_{\mathcal{R}_{1}}[|\mathcal{M}|]-F_{\mathcal{ R}_{2}}[|\mathcal{M}|]\big{|}-|\mathcal{M}|q+|\mathcal{M}|\]  
_for the classification threshold \(s_{n}(\mathcal{R}_{1},\mathcal{R}_{2})\geq\alpha\) in fuzzy bipartite matching._  
Proof. : We begin with three fundamental inequalities. For any matched pairs, \((i,j)\in\mathcal{M}\):  
\[\max\Bigg{\{}\sum_{(i,j)\in\mathcal{M}}|X_{i}|,\sum_{(i,j)\in\mathcal{M}}|Y_{j} |\Bigg{\}}\leq\sum_{(i,j)\in\mathcal{M}}\max\{|X_{i}|,|Y_{j}|\} \tag{49}\]