Editing Edit distance (section)

===Properties===
Edit distance with non-negative cost satisfies the axioms of a [[Metric (mathematics)|metric]], giving rise to a [[metric space]] of strings, when the following conditions are met:<ref name="navarnarutoro" />{{rp|37}}

* Every edit operation has positive cost;
* for every operation, there is an inverse operation with equal cost.

With these properties, the metric axioms are satisfied as follows:

:{{mvar|d}}({{mvar|a}}, {{mvar|b}}) = 0 if and only if a=b, since each string can be trivially transformed to itself using exactly zero operations.
:{{mvar|d}}({{mvar|a}}, {{mvar|b}}) > 0 when {{mvar|a}} ≠ {{mvar|b}}, since this would require at least one operation at non-zero cost.
:{{mvar|d}}({{mvar|a}}, {{mvar|b}}) = {{mvar|d}}({{mvar|b}}, {{mvar|a}}) by equality of the cost of each operation and its inverse.
:Triangle inequality: {{mvar|d}}({{mvar|a}}, {{mvar|c}}) ≤ {{mvar|d}}({{mvar|a}}, {{mvar|b}}) + {{mvar|d}}({{mvar|b}}, {{mvar|c}}).<ref>{{cite conference |author1=Lei Chen |author2=Raymond Ng |title=On the marriage of L<sub>p</sub>-norms and edit distance |conference=Proc. 30th Int'l Conf. on Very Large Databases (VLDB) |url=http://www.cs.ust.hk/~leichen/pub/04/vldb04.pdf |volume=30 |year=2004 |doi=10.1016/b978-012088469-8.50070-x}}</ref>

Levenshtein distance and LCS distance with unit cost satisfy the above conditions, and therefore the metric axioms. Variants of edit distance that are not proper metrics have also been considered in the literature.<ref name="navarnarutoro" />

Other useful properties of unit-cost edit distances include:

* LCS distance is bounded above by the sum of lengths of a pair of strings.<ref name="navarnarutoro" />{{rp|37}}
* LCS distance is an upper bound on Levenshtein distance.
* For strings of the same length, Hamming distance is an upper bound on Levenshtein distance.<ref name="navarnarutoro" />

Regardless of cost/weights, the following property holds of all edit distances:

* When {{mvar|a}} and {{mvar|b}} share a common prefix, this prefix has no effect on the distance. Formally, when {{mvar|a}} = {{mvar|uv}} and {{mvar|b}} = {{mvar|uw}}, then {{mvar|d}}({{mvar|a}}, {{mvar|b}}) = {{mvar|d}}({{mvar|v}}, {{mvar|w}}).<ref name="ssm"/> This allows speeding up many computations involving edit distance and edit scripts, since common prefixes and suffixes can be skipped in linear time.