2
$\begingroup$

The edit distance between two strings $d(w_1, w_2)$ sums up the cost of edit operations that transform one string into the other. If done right, the edit distance is a metric.

In particular, the cost of an edit operation may depend on the character inserted or deleted, meaning we have costs $w_\text{insert}(a)$ and $w_\text{delete}(a)$ for all characters $a$.

Question: If the cost also depends on the position in the input string where it is applied, will the result still be a metric?

As an example, consider a spell checker that assumes mistakes in the first character of a word are rather seldom as compared to other positions, so when searching for corrected words, a change in the first position would have high cost.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ I pretty sure that the answer depends on how it depends on the position. Can you formulate reasonable restrictions? What have you tried towards checking the requirements for a metric, and where did you get stuck? $\endgroup$
    – Raphael ♦
    Dec 9, 2015 at 13:11
  • $\begingroup$ I tried to find a proof that Levensthein is a metric to go from there, but googling for it just brings up tons of links to the algorithm. I might have more luck digging through my dusted CS books tonight. As for the position cost, I would first look at the proof and derive necessary restrictions from there. $\endgroup$
    – Harald
    Dec 9, 2015 at 20:37
  • 1
    $\begingroup$ Try proving that yourself; iirc it's not hard. The process will give you more insight than just reading the proof. $\endgroup$
    – Raphael ♦
    Dec 9, 2015 at 20:44
  • $\begingroup$ Thanks for the motivation, but I did my share of proofs like this when I studied CS long ago, so I rather go and look it up elsewhere . $\endgroup$
    – Harald
    Dec 9, 2015 at 20:55
  • 1
    $\begingroup$ If you are not willing to work it out yourself, why should we work it out for you? We also did our share of proofs like this in undergrad. $\endgroup$
    – Yuval Filmus
    Dec 10, 2015 at 5:41

1 Answer 1

Reset to default
4
$\begingroup$

Here is why the usual edit distance is a metric:

  1. $d(w,w) = 0$ since no operations need to be performed to get from $w$ to $w$.

  2. $d(x,y) = d(y,x)$ since given a sequence of operations for transforming $x$ to $y$, we can perform it in reverse to transform $y$ to $x$ at the same cost. This shows that $d(y,x) \leq d(x,y)$, and similarly $d(x,y) \leq d(y,x)$.

  3. $d(x,y) \leq d(x,z) + d(z,y)$ since if $\alpha$ transforms $x$ to $z$ and $\beta$ transforms $z$ to $y$ then $\alpha\beta$ transforms $x$ to $y$, and moreover the cost of $\alpha\beta$ is the sum of the costs of $\alpha$ and $\beta$.

Now you're in a position to answer your question yourself.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot. I was missing the insight that it becomes trivial when not thinking about the Levensthein algorithm stuff but just about reversible steps with a cost attached performed. The requirement for reverse transform in (2) shows we need reversible single-step ops, where the pair must have equals cost. (3) requires non-negative cost. And the tricky part about position dependent cost, my original question, is to get it reversible, which it likely is not. $\endgroup$
    – Harald
    Dec 11, 2015 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.