# Variation to edit distance depending on position still a metric?

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.

• 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?
– Raphael
Dec 9, 2015 at 13:11
• 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. Dec 9, 2015 at 20:37
• Try proving that yourself; iirc it's not hard. The process will give you more insight than just reading the proof.
– Raphael
Dec 9, 2015 at 20:44
• 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 . Dec 9, 2015 at 20:55
• 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. Dec 10, 2015 at 5:41

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$.