I am studying some aspects concerning string distance functions, and I am sure there are generic results available in the field of metric spaces, but I have not been able to find appropriate references.
The problem I have is the following. Let $d$ be a string distance function. The operation '+' denotes string concatenation. Consider the following trivial property:
$$d(a, b) = d(a+c, b+c) \tag{I} \label{eq1}$$
For example, under a function satisfying this property the distance between the strings abc and def would be the same as between abcxyz and defxyz. Many of the most famous distance functions satisfy this property. For example, the famous Levenshtein distance does. However, not all of them do. For example, consider the following $n$-gram based distance (adapted from this paper):
$$d_1(a, b) = 1 - \frac{ \left| a_2 \cap b_2 \right|}{\mathrm{max} \left( \left| a_2 \right|, \left| b_2 \right| \right)}$$
where $a_2$ and $b_2$ are the sets of distinct $2$-grams in the strings $a$ and $b$, respectively. For the strings"abcde" and "abhij" $d_1($"abcde"$,$"abhij"$)$ is equal to $0.75$. In case we append the suffix "x" to both strings, the new distance would be $d_1($"abcde"$+$"x"$,$"abhij"$+$"x"$) = 0.8 > 0.75$. Conversely, in case we append the suffix "xy" to both strings, the new distance would be $d_1($"abcde"$+$"xy"$,$"abhij"$+$"xy"$) = 0.667 < 0.75$. Note that in the first case the value obtained is greater than the original (">"), and in this second case, the value obtained is less ($<$).
Of the distances that do not satisfy \eqref{eq1}, there are some of them that satisfy a more relaxed condition:
$$d(a, b) \leq d(a+c, b+c) \tag{II} \label{eq2}$$
For example, the following distance function, also based on $n$-grams, satisfies this property (adapted from this paper):
$$d_2(a, b) = \left| a_2 \ominus b_2 \right|$$
i.e. size of the symmetric difference between the two sets of $2$-grams.
I have several questions regarding all this:
- What is the name of property \eqref{eq1}?
- What is the name of property \eqref{eq2}?
- I am looking for the proof that if two distances $d_1$ and $d_2$ satisfy \eqref{eq2}, a new distance $d_3$ defined as a linear combination of them (i.e. $d_3(a, b) = \alpha \cdot d_1(a, b) + \beta \cdot d_2(a, b)$, for $\alpha, \beta \in \mathbb{R}$) will also satisfy \eqref{eq2}.
Thanks a lot in advance
