Bag distance

Given a string $x$ over an alphabet $\Sigma$, let $x = ms(x)$ denote the multiset (bag) of symbols in $x$. For instance, $ms(peer) = \lbrace\lbrace e, e, p, r \rbrace\rbrace$. The following can be easily proved to be a metric on multisets:

$$dis_{bag}(x, y) = \max(|x \setminus y|, |y \setminus x|)$$

where the difference has a bag semantics (e.g. $\lbrace\lbrace a, a, a, b\rbrace\rbrace \setminus \lbrace\lbrace a, a, b, c, c\rbrace\rbrace = \lbrace\lbrace a \rbrace\rbrace$), and $| · |$ counts the number of elements in a multiset (e.g. $|\lbrace\lbrace a, a \rbrace\rbrace | = 2$).
In practice, $dis_{bag}$ first “drops” common elements, then takes the maximum
considering the number of “residual” elements. For instance:

$$dis_{bag}(\lbrace\lbrace a, a, a, b \rbrace\rbrace, \lbrace\lbrace a, a, b, c, c \rbrace\rbrace ) = \max(|\lbrace\lbrace a \rbrace\rbrace |, |\lbrace\lbrace c, c \rbrace\rbrace |) = 2$$

It is immediate to observe that $dis_{bag}(x, y) \leq dis_{Lev}(x, y), \forall x, y \in \Sigma^{\ast}$. See Levenshtein distance.

Further, since computing $dis_{bag}(x, y)$ is $O(|x| + |y|)$, $dis_{bag}$ can indeed be effectively used to quickly filter out candidate strings.

Reading

• Bartolini, I., Ciaccia, P., Patella, M. (2002). String Matching with Metric Trees Using an Approximate Distance ↗