## 4 Optimal Q-Gram Filter
### Optimal Count Q-Gram Filter for Fuzzy Token Similarity
\begin{table}
\begin{tabular}{c c} \hline
**Similarity Measure** & **Subject to \(\sum_{(i,j)\in\mathcal{M}}\alpha_{i,j}\)** \\ \hline Fuzzy Dice & \(\frac{\alpha}{2}(|\mathcal{R}_{1}|+|\mathcal{R}_{2}|)\) \\ \hline Fuzzy Cosine & \(\alpha\sqrt{|\mathcal{R}_{1}||\mathcal{R}_{2}|}\) \\ \hline Fuzzy Jaccard & \(\frac{\alpha}{1+\alpha}(|\mathcal{R}_{1}|+|\mathcal{R}_{2}|)\) \\ \hline Fuzzy Overlap /FRMS & \(\alpha\min\{|\mathcal{R}_{1}|,|\mathcal{R}_{2}|\}\) \\ \hline \end{tabular}
\end{table} 
Table 1: An overview of fuzzy token similarity functions and their corresponding constraints, as discussed in [60], is provided for the integer linear programming problem. For arbitrary real numbers, \(a,b\in\mathbb{R}\):  
\[\max\{a,b\}=\frac{1}{2}(a+b+|a-b|) \tag{50}\]  
Furthermore, for the cumulative sums:  
\[\max\{F_{\mathcal{R}_{1}}[|\mathcal{M}|],F_{\mathcal{R}_{2}}[|\mathcal{M}|]\} \leq\max\Bigg{\{}\sum_{(i,j)\in\mathcal{M}}|X_{i}|,\sum_{(i,j)\in\mathcal{M}}| Y_{j}|\Bigg{\}} \tag{51}\]  
Beginning with the definition of Q-gram similarity in the context of bipartite matching:  
\[t_{\mathcal{M}}=\sum_{(i,j)\in\mathcal{M}}\max\{|X_{i}|,|Y_{j}|\}-|\mathcal{M} |q+|\mathcal{M}|-q\max_{\alpha}\sum_{(i,j)\in\mathcal{M}}d(\alpha,|X_{i}|,|Y_ {j}|) \tag{52}\]  
Initially keeping the individual \(\alpha_{i,j}\) terms:  
\[=\sum_{(i,j)\in\mathcal{M}}\max\{|X_{i}|,|Y_{j}|\}-|\mathcal{M}|q+|\mathcal{M }|-q\max_{\alpha}\sum_{(i,j)\in\mathcal{M}}\frac{1-\alpha_{i,j}}{1+\alpha_{i, j}}(|X_{i}|+|Y_{j}|) \tag{53}\]  
Under the assumption of constant \(\alpha_{i,j}=\alpha\) for all \((i,j)\):  
\[\approx\sum_{(i,j)\in\mathcal{M}}\max\{|X_{i}|,|Y_{j}|\}-|\mathcal{M}|q+| \mathcal{M}|-q\frac{1-\alpha}{1+\alpha}\sum_{(i,j)\in\mathcal{M}}\left(|X_{i} |+|Y_{j}|\right) \tag{54}\]  
Applying inequality (49):  
\[\geq\max\Bigg{\{}\sum_{(i,j)\in\mathcal{M}}|X_{i}|,\sum_{(i,j)\in\mathcal{M}}| Y_{j}|\Bigg{\}}-|\mathcal{M}|q+|\mathcal{M}|-\frac{q-q\alpha}{1+\alpha}\sum_{(i,j )\in\mathcal{M}}\left(|X_{i}|+|Y_{j}|\right) \tag{55}\]  
Using the analytical maximum form (50):  
\[ \begin{split}&=\frac{1}{2}\sum_{(i,j)\in\mathcal{M}}\left(|X_{i} |+|Y_{j}|\right)+\frac{1}{2}\Bigg{|}\sum_{(i,j)\in\mathcal{M}}|X_{i}|-\sum_{( i,j)\in\mathcal{M}}|Y_{j}|\Bigg{|}\\ &\quad-|\mathcal{M}|q+|\mathcal{M}|-\frac{q-q\alpha}{1+\alpha} \sum_{(i,j)\in\mathcal{M}}\left(|X_{i}|+|Y_{j}|\right)\end{split}  \tag{56}\]  
Collecting terms with common factor \(\sum_{(i,j)\in\mathcal{M}}\left(|X_{i}|+|Y_{j}|\right)\):  
\[ \begin{split}&=\left(\frac{1}{2}-\frac{q-q\alpha}{1+\alpha} \right)\sum_{(i,j)\in\mathcal{M}}\left(|X_{i}|+|Y_{j}|\right)\\ &\quad+\frac{1}{2}\Bigg{|}\sum_{(i,j)\in\mathcal{M}}|X_{i}|-\sum_ {(i,j)\in\mathcal{M}}|Y_{j}|\Bigg{|}-|\mathcal{M}|q+|\mathcal{M}|\end{split}  \tag{57}\]  
Through algebraic manipulation:  
\[ \begin{split}&=\frac{2q\alpha+\alpha-2q+1}{2+\alpha}\sum_{(i,j )\in\mathcal{M}}\left(|X_{i}|+|Y_{j}|\right)\\ &\quad+\frac{1}{2}\Bigg{|}\sum_{(i,j)\in\mathcal{M}}|X_{i}|-\sum_ {(i,j)\in\mathcal{M}}|Y_{j}|\Bigg{|}-|\mathcal{M}|q+|\mathcal{M}|\end{split}  \tag{58}\]Applying inequality (51):  
\[ \begin{split}&\geq\frac{2q\alpha+\alpha-2q+1}{2+\alpha}(F_{\mathcal{ R}_{1}}[|\mathcal{M}|]+F_{\mathcal{R}_{2}}[|\mathcal{M}|])\\ &\quad+\frac{1}{2}\Big{|}F_{\mathcal{R}_{1}}[|\mathcal{M}|]-F_{ \mathcal{R}_{2}}[|\mathcal{M}|]\Big{|}-|\mathcal{M}|q+|\mathcal{M}|\end{split}  \tag{59}\]  
Finally, taking the floor function to ensure integer values:  
\[ \begin{split}\widehat{t}_{\mathcal{M}}&=\bigg{[} \frac{2q\alpha+\alpha-2q+1}{2+\alpha}(F_{\mathcal{R}_{1}}[|\mathcal{M}|]+F_{ \mathcal{R}_{2}}[|\mathcal{M}|])\\ &\quad+\frac{1}{2}\Big{|}F_{\mathcal{R}_{1}}[|\mathcal{M}|]-F_{ \mathcal{R}_{2}}[|\mathcal{M}|]\Big{|}\bigg{]}-|\mathcal{M}|q+|\mathcal{M}| \end{split}  \tag{60}\]  
Therefore, \(t_{\mathcal{M}}\approx\widehat{t}_{\mathcal{M}}\) provides a lower bound approximation for the Q-gram similarity under the constant \(\alpha\) assumption, with the approximation becoming tighter as the variation in individual \(\alpha_{ij}\) values decreases.