## 3 Approximate Record Matching in Similarity Space
### Proposed Model of Fuzzy Record Similarity Metric (FRSM)
We now introduce a normalization of \(d(X_{i},Y_{j})\) differences (generally called the edit distance) for Levenshtein similarity in the interval \([0,1]\), which is one of the most used in [4; 12; 30; 42]:  
\[s(X_{i},Y_{j})=1-\frac{d(X_{i},Y_{j})}{\max\{|X_{i}|,|Y_{j}|\}}. \tag{13}\]  
It can be easily shown, for example, Appendix A.3, that this normalization also violates the triangle inequality; therefore, all the distances or similarity functions introduced in the articles based on this normalization are not metrics and cannot be used well in applications like cluster analysis. **Theorem 5** (Normalized Edit Similarity Metric). : _Let \(\Sigma\) be a finite alphabet, and let \(\Sigma^{*}\) represent the set of all possible strings formed over \(\Sigma\). Given \(X,Y\in\Sigma^{*}\), the generalized Rozinek similarity over \(\Sigma\) is the normalized edit similarity metric:_  
\[s_{n}(X,Y)=\frac{s(X,X)+s(Y,Y)-d(X,Y)}{s(X,X)+s(Y,Y)+d(X,Y)}=\frac{|X|+|Y|-d(X, Y)}{|X|+|Y|+d(X,Y)}, \tag{14}\]  
_where \(s_{n}(X,Y)\colon\Sigma^{*}\times\Sigma^{*}\to[0,1]\subset\mathbb{R}\) and \(|\,.\,|\) denote the cardinality of a set, specifically the number of characters of the string._  
Proof. : Without loss of generality, we can assume that the self-similarity \(s(X,X)\) is a set function. Specifically, \(s(X,X)\) represents a measure, \(\mu(X)\), defined on a \(\sigma\)-algebra over the finite alphabet \(\Sigma\). The set of all strings, \(\Sigma\), induces a \(\sigma\)-algebra on the finite alphabet \(\Sigma\), which results in a measure space represented by the triple \((\Sigma,\Sigma^{\prime}\mu)\). In the abstract sense, the edit distance, \(d(x,y)\), can be interpreted as the symmetric difference of ordered sets, known as the Frechet-Nikodym metric [43], where \(d(X,Y)=\mu(X\triangle Y)\) is calculated by an algorithm of dynamic programming. For finite sets, the cardinality is a natural measure of size. In this case, we take the cardinality \(|\,.\,|\) of sets given by the number of characters in the sets. We express  
\[s_{R}(X,Y) = s_{n}(X,Y)=\frac{s(X,X)+s(Y,Y)-d(X,Y)}{s(X,X)+s(Y,Y)+d(X,Y)} \tag{15}\] \[= \frac{\mu(X)+\mu(Y)-\mu(X\triangle Y)}{\mu(X)+\mu(Y)+\mu(X \triangle Y)}=\frac{|X|+|Y|-d(X,Y)}{|X|+|Y|+d(X,Y)}.\]  
From Theorem 2, it is proven that \(s_{R}(X,Y)\) is a normalized similarity metric; therefore, this is complete. Alternatively, we also give a second proof [24; 43] to support our statement:  
\[\frac{|X|+|Y|-d(X,Y)}{|X|+|Y|+d(X,Y)}=1-\frac{2d(X,Y)}{|X|+|Y|+d(X,Y)}=1-d_{n} (X,Y), \tag{16}\]where \(d_{n}(x,y)\) is a normalized edit distance of the form  
\[d_{n}(X,Y)=\frac{2d(X,Y)}{|X|+|Y|+d(X,Y)}. \tag{17}\]  
In [24], it is further proved that \(d_{n}\) is a normalized distance metric. Hence, by the duality between normalized similarity metrics and normalized distance metrics, \(s_{n}(x,y)=1-d_{n}(x,y)\) is also proven [43]. Now, consider a scenario in which we want to predict the edit distance based on knowing only the lengths of the strings \(X\) and \(Y\). The calculation of the edit distance, \(d(X,Y)\), itself is computationally expensive, in quadratic time it is \(\mathcal{O}(|X||Y|)\), so we would like to obtain at least a rough estimate of the worst case of the expected edit distance for the minimum edit normalized similarity, given by the threshold \(s_{n}(X,Y)\geq\alpha\). We introduce an expected edit distance, \(\sup_{\alpha}d(X,Y)=d(\alpha,|X|,|Y|)\), depending on already-known parameters--the threshold \(\alpha\) and the lengths of the strings \(|X|\) and \(|Y|\). Finally, we obtain a prediction which is computationally feasible in constant time, \(\mathcal{O}(1)\), and will help in developing an optimal filter in further chapters. **Definition 5** (Expected Edit Distance).