1
$\begingroup$

Let $(M,d)$ be a metric space. Consider two sequences $a = (a_i)_{i=1}^n$, $b = (b_i)_{i=1}^m$, $n, m \in \mathbb{N}$ with elements in $M$. For two sequences $[n],[m]$, call $$\Gamma([n], [m]) = \big\{E \subseteq [n] \times [m]\mid \forall i < j, k>l: \neg ((i,k) \in E \wedge (j, l) \in E) \wedge \pi_1(E) = [n] \wedge \pi_2(E) = [m]\big\}$$ the set of weakly increasing matchings (that's a title I made up for them).

Define a function $\tilde d \colon M^\mathbb N \times M^\mathbb N \to \mathbb R^+$, $$ \widetilde d(a, b) = \min_{E \in \Gamma ([n],[m])} \sum_{i, j \in E} d(a_i, b_{j}). $$ This should define a metric, which I'm tempted to call string matching distance (which seems to be, after a brief google, already taken by the edit distance, which is different). Questions:

  • Does this metric have a name?
  • For which classes of metrics is this metric efficiently computable/approximable?
Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ As you've written it this is not a metric, because the minimum always occurs when $E$ is empty. Assuming the definition you probably meant to write (namely, adding the condition that the projections of $E$ onto $[n]$ and $[m]$ are surjective) it is straightforward to write down a dynamic-programming approach to compute $\tilde{d}$ that is quadratic in $\max(m,n)$. So the only interesting question in this post is for what metrics you can approximate this in sub-quadratic time; this may be more suitable for cstheory.SE. $\endgroup$
    – dvitek
    Dec 27, 2021 at 16:03
  • $\begingroup$ What does "two sequences $[n]$, $[m]$" mean? As written, your definition seems very specific to (I assume you mean, or maybe you prefer to shift by $1$) $[n] = \{0, \dotsc, n - 1\}$ and $m = \{0, \dotsc, m - 1\}$; do you really mean it to apply to arbitrary sequences? $\endgroup$
    – LSpice
    Dec 27, 2021 at 16:05
  • $\begingroup$ Thanks, dvitek, dynamic programming was a good call. The only think I don't see is how to make it quadratic (and not cubic): I thought that one needs to go trough the matched index of k = n downto 1 and the one for k+1 (which would be stored). That would give cubic time. $\endgroup$
    – Andreas Haupt
    Jan 9, 2022 at 20:24

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.