# 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 '15 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. – Harald Dec 9 '15 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 '15 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 . – Harald Dec 9 '15 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. – Yuval Filmus Dec 10 '15 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$.