Editing Edit distance (section)

==Formal definition and properties==
Given two strings {{mvar|a}} and {{mvar|b}} on an alphabet {{math|Σ}} (e.g. the set of [[ASCII]] characters, the set of [[byte]]s [0..255], etc.), the edit distance {{nowrap|d({{mvar|a}}, {{mvar|b}})}} is the minimum-weight series of edit operations that transforms {{mvar|a}} into {{mvar|b}}. One of the simplest sets of edit operations is that defined by Levenshtein in 1966:<ref name="slp"/>

<!-- FIXME: If this is a quote, it should use {{blockquote}}; if it's not, it should use * list rather than : list as that is the appropriate semantic -->
:'''Insertion''' of a single symbol. If {{mvar|a}} = {{mvar|u}}{{mvar|v}}, then inserting the symbol {{mvar|x}} produces {{mvar|u}}{{mvar|x}}{{mvar|v}}. This can also be denoted ε→{{mvar|x}}, using ε to denote the empty string.
:'''Deletion''' of a single symbol changes {{mvar|u}}{{mvar|x}}{{mvar|v}} to {{mvar|u}}{{mvar|v}} ({{mvar|x}}→ε).
:'''Substitution''' of a single symbol {{mvar|x}} for a symbol {{mvar|y}} ≠ {{mvar|x}} changes {{mvar|u}}{{mvar|x}}{{mvar|v}} to {{mvar|u}}{{mvar|y}}{{mvar|v}} ({{mvar|x}}→{{mvar|y}}).

In Levenshtein's original definition, each of these operations has unit cost (except that substitution of a character by itself has zero cost), so the Levenshtein distance is equal to the minimum ''number'' of operations required to transform {{mvar|a}} to {{mvar|b}}. A more general definition associates non-negative weight functions {{mvar|w}}<sub>ins</sub>({{mvar|x}}), {{mvar|w}}<sub>del</sub>({{mvar|x}}) and {{mvar|w}}<sub>sub</sub>({{mvar|x}},&nbsp;{{mvar|y}}) with the operations.<ref name="slp">{{cite book |author1=Daniel Jurafsky |author2=James H. Martin |title=Speech and Language Processing |publisher=Pearson Education International |pages=107–111}}</ref>

Additional primitive operations have been suggested. [[Damerau–Levenshtein distance]] counts as a single edit a common mistake: '''transposition''' of two adjacent characters, formally characterized by an operation that changes {{mvar|u}}{{mvar|x}}{{mvar|y}}{{mvar|v}} into {{mvar|u}}{{mvar|y}}{{mvar|x}}{{mvar|v}}.<ref name="ukkonen83">{{cite conference |author=Esko Ukkonen |title=On approximate string matching |conference=Foundations of Computation Theory |year=1983 |pages=487–495 |publisher=Springer|doi=10.1007/3-540-12689-9_129 }}</ref><ref name="ssm"/>
For the task of correcting [[Optical character recognition|OCR]] output, '''merge''' and '''split''' operations have been used which replace a single character into a pair of them or vice versa.<ref name="ssm">{{cite journal |first1=Klaus U. |last1=Schulz |first2=Stoyan |last2=Mihov |year=2002 |citeseerx=10.1.1.16.652 |title=Fast string correction with Levenshtein automata |journal=International Journal of Document Analysis and Recognition |volume=5 |issue=1 |pages=67–85 |doi=10.1007/s10032-002-0082-8|s2cid=207046453 }}</ref>

Other variants of edit distance are obtained by restricting the set of operations. [[Longest common subsequence problem|Longest common subsequence (LCS)]] distance is edit distance with insertion and deletion as the only two edit operations, both at unit cost.<ref name="navarnarutoro" />{{rp|37}} Similarly, by only allowing substitutions (again at unit cost), [[Hamming distance]] is obtained; this must be restricted to equal-length strings.<ref name="navarnarutoro" />
[[Jaro–Winkler distance]] can be obtained from an edit distance where only transpositions are allowed.

===Example===
The [[Levenshtein distance]] between "kitten" and "sitting" is 3. A minimal edit script that transforms the former into the latter is:

# '''k'''itten → '''s'''itten (substitute "s" for "k")
# sitt'''e'''n → sitt'''i'''n (substitute "i" for "e")
# sittin → sittin'''g''' (insert "g" at the end)

LCS distance (insertions and deletions only) gives a different distance and minimal edit script:

# '''k'''itten → itten (delete "k" at 0)
# itten → '''s'''itten (insert "s" at 0)
# sitt'''e'''n → sittn (delete "e" at 4)
# sittn → sitt'''i'''n (insert "i" at 4)
# sittin → sittin'''g''' (insert "g" at 6)

for a total cost/distance of 5 operations.

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