## 4 Optimal Q-Gram Filter
### Optimal Count Q-Gram Filter for Edit Similarity  
The normalization of the edit distance has received less attention in many scientific articles, but we find it to have great importance for many real-world applications that need to measure normalized similarity independently of the length of the string. The edit distance, \(d=1\), on a string with a length of \(|X|=24\) is very often totally different from that of a string, \(Y\), with a length of, e.g., \(|Y|=6\). The normalization factor that this brings is related well to the human perception of the similarity of different objects. From similarity space theory, the strings could often have different self-similarities. Self-similarity could be a measure of the number of extracted Q-grams or string lengths. For instance, having German words \(X=\)'Einkommensetwearerklarung' (income tax return) and \(Y=\)'Steuer' (tax), we have \(s(X,X)\geq s(Y,Y)\) when counting string lengths, common characters, or Q-grams. Whenever we compare two objects with different feature sizes, we ask the following question: Are these objects also of different importance? In our model, we say no; hence, we obtain the following argument for normalization among strings. Similar to the previous (3), we reformulate our normalized least-sharing Q-gram pairs as a threshold similarity, as follows:  
\[t_{\alpha}=\inf_{\alpha}\{|Q_{X}\cap Q_{Y}|\}=\max\{|X|,|Y|\}-q+1-qd(\alpha,| X|,|Y|), \tag{31}\]  
where we substitute for the edit distance the worst case scenario with \(d(X,Y)=d(\alpha,|X|,|Y|)\), and we use this case later in this paper. The occurrence of a singularity of the Q-gram filter, \(t_{\alpha}\), depends on the string lengths \(|X|\) and \(|Y|\) and the user-chosen threshold parameter, \(\alpha\in[0,1]\). **Corollary 6**: _Let \(|X|\) and \(|Y|\) be string lengths, where \(t_{\alpha}=0\) for a normalized edit similarity, \(s_{n}(X,Y)\geq\alpha\). We call this a singularity of the Q-gram filter._  
\[|X|_{sing}=qd(\alpha,|X|,|Y|)+q-1. \tag{32}\]  
Proof. : With \(t_{\alpha}=0\), it can be proven  
\[ \begin{split} 0=|X|-q+1-qd(\alpha,|X|,|Y|),\\ |X|_{sing}=qd(\alpha,|X|,|Y|)+q-1.\end{split}  \tag{33}\]  
For simplicity, we assume the tokens have the same lengths, \(|X|=|Y|\). For illustration, we introduce these examples: if \(d(\alpha,|X|,|Y|)=1\), then we obtain \(|X|_{sing}=|Y|_{sing}=2q-1\) for a trigram, \(|X|_{sing}=5\), and for a bigram, \(|X|_{sing}=3\). For another example, if \(d(\alpha,|X|,|Y|)=2\), then \(|X|_{sing}=|Y|_{sing}=3q-1\) for the trigram \(|X|_{sing}=8\) and for the bigram \(|X|_{sing}=5\). Figure 3: An example of a singularity of a trigram filter for \(d=1\) and \(|X|_{sing}=5\). Suppose the worst case for fixed \(d=1\) is the substitution in the position of character C destroying all trigrams {“_CAC_”, “_ACH_”, “_CHE_”]; hence, \(t=0\). **Corollary 7** (Edit Distance Singularity of Q-gram Filter). : _Suppose that we are given an expected edit distance of \(d_{sing}(\alpha,|X|,|Y|)\), which is a singularity of the Q-gram filter for an edit distance, that is, where \(t_{\alpha}=0\). Then,_  
\[d_{sing}(\alpha,|X|,|Y|)=\left\lceil\frac{|Q_{X}|}{q}\right\rceil \tag{34}\]  
_where \(Q_{X}\) is the Q-gram set of string \(X\)._  
Proof. : Since \(t_{\alpha}=0\), then, similar to before,  
\[ \begin{split} 0&=\max\{|X|,|Y|\}-q+1-qd_{sing}( \alpha,|X|,|Y|),\\ d_{sing}(\alpha,|X|,|Y|)&=\left\lceil\frac{\max\{| X|,|Y|\}-q+1}{q}\right\rceil,\\ d_{sing}(\alpha,|X|,|Y|)&=\left\lceil\frac{\sup\{| Q_{X}\cap Q_{Y}|\}}{q}\right\rceil.\end{split}  \tag{35}\]  
For simplicity, again assume \(|X|=|Y|\). Then, we obtain finally  
\[d_{sing}(\alpha,|X|,|Y|)=\left\lceil\frac{|Q_{X}|}{q}\right\rceil. \tag{36}\]  
The fractional part leads to the remaining Q-grams, which have the size \(|Q_{X}|\bmod q\). In addition, the remaining Q-grams must be destroyed with \(d=1\); hence, we use ceiling function \(\lceil.\rceil\) to handle the fractional part. Simply explained, a Q-gram filter can work efficiently if \(d(X,Y)\leq d_{sing}(\alpha,|X|,|Y|)\).