Editing Edit distance

{{short description|Computer science metric of string similarity}}
In [[computational linguistics]] and [[computer science]], '''edit distance''' is a [[string metric]], i.e. a way of quantifying how dissimilar two [[String (computing)|strings]] (e.g., words) are to one another, that is measured by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in [[natural language processing]], where automatic [[Spell checker|spelling correction]] can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question. In [[bioinformatics]], it can be used to quantify the similarity of [[DNA]] sequences, which can be viewed as strings of the letters A, C, G and T.

Different definitions of an edit distance use different sets of like operations. [[Levenshtein distance]] operations are the removal, insertion, or substitution of a character in the string. Being the most common metric, the term ''Levenshtein distance'' is often used interchangeably with ''edit distance''.<ref name="navarnarutoro">{{cite journal|last1=Navarro|first1=Gonzalo|title=A guided tour to approximate string matching|journal=ACM Computing Surveys|date=1 March 2001|volume=33|issue=1|pages=31–88|doi=10.1145/375360.375365|url=http://users.csc.calpoly.edu/~dekhtyar/570-Fall2011/papers/navarro-approximate.pdf|access-date=19 March 2015|citeseerx=10.1.1.452.6317|s2cid=207551224 }}</ref>

== Types of edit distance ==

Different types of edit distance allow different sets of string operations. For instance:
{| class="wikitable"
|+ Algorithms and the operations allowed
|-
!Algorithm
!Insertions
!Deletions
!Substitutions
![[Transposition (mathematics)|Transposition]]
|-
|[[Levenshtein distance|Levenshtein Distance]] 
|✓
|✓
|✓
|
|-
|[[longest common subsequence|Longest Common Subsequence]] (LCS) 
|✓
|✓
|
|
|-
|[[Hamming distance|Hamming Distance]]
|
|
|✓
|
|-
|[[Damerau–Levenshtein distance|Damerau–Levenshtein Distance]]
|✓
|✓
|✓
|✓
|-
|[[Jaro distance]] 
|
|
|
|✓
|}
Some edit distances are defined as a parameterizable metric calculated with a specific set of allowed edit operations, and each operation is assigned a cost (possibly infinite). This is further generalized by DNA [[sequence alignment]] algorithms such as the [[Smith–Waterman algorithm]], which make an operation's cost depend on where it is applied.

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

==Computation==

The first algorithm for computing minimum edit distance between a pair of strings was published by [[Frederick J. Damerau|Damerau]] in 1964.<ref>{{Cite journal |title=Techniques for Automatically Correcting Words in Text |first=Karen |last=Kukich |journal=ACM Computing Surveys |volume=24 |issue=4 |year=1992 |url=http://dc-pubs.dbs.uni-leipzig.de/files/Kukich1992Techniqueforautomatically.pdf |doi=10.1145/146370.146380 |pages=377–439 |s2cid=5431215 |access-date=2017-11-09 |archive-url=https://web.archive.org/web/20160927030713/http://dc-pubs.dbs.uni-leipzig.de/files/Kukich1992Techniqueforautomatically.pdf |archive-date=2016-09-27 |url-status=dead }}</ref>

===Common algorithm===
{{main|Wagner–Fischer algorithm}}
Using Levenshtein's original operations, the (nonsymmetric) edit distance from <math>a = a_1\ldots a_m</math> to <math>b = b_1\ldots b_n</math> is given by <math>d_{mn}</math>, defined by the [[Recursive definition|recurrence]]<ref name="slp"/>

:<math>\begin{align}d_{i0} &= \sum_{k=1}^{i} w_\mathrm{del}(a_{k}), & & \quad  \text{for}\; 1 \leq i \leq m \\
d_{0j} &= \sum_{k=1}^{j} w_\mathrm{ins}(b_{k}), & & \quad \text{for}\; 1 \leq j \leq n \\
d_{ij} &= \begin{cases} d_{i-1, j-1} & \text{for}\; a_{i} = b_{j}\\ \min \begin{cases} d_{i-1, j} + w_\mathrm{del}(a_{i})\\ d_{i,j-1} + w_\mathrm{ins}(b_{j}) \\ d_{i-1,j-1} + w_\mathrm{sub}(a_{i}, b_{j}) \end{cases} & \text{for}\; a_{i} \neq b_{j}\end{cases} & & \quad  \text{for}\; 1 \leq i \leq m, 1 \leq j \leq n.\end{align}</math>
This algorithm can be generalized to handle transpositions by adding another term in the recursive clause's minimization.<ref name="ukkonen83"/>

The straightforward, [[Recursion (computer science)|recursive]] way of evaluating this recurrence takes [[exponential time]]. Therefore, it is usually computed using a [[dynamic programming]] algorithm that is commonly credited to [[Wagner–Fischer algorithm|Wagner and Fischer]],<ref>{{cite journal |author1=R. Wagner |author2=M. Fischer |s2cid=13381535 |title=The string-to-string correction problem |journal=J. ACM |volume=21 |year=1974 |pages=168–178 |doi=10.1145/321796.321811|doi-access=free }}</ref> although it has a history of multiple invention.<ref name="slp"/><ref name="ukkonen83"/>
After completion of the Wagner–Fischer algorithm, a minimal sequence of edit operations can be read off as a backtrace of the operations used during the dynamic programming algorithm starting at <math>d_{mn}</math>.

This algorithm has a [[time complexity]] of Θ({{mvar|m}}{{mvar|n}})  where {{mvar|m}} and {{mvar|n}} are the lengths of the strings. When the full dynamic programming table is constructed, its [[space complexity]] is also {{nowrap|Θ({{mvar|m}}{{mvar|n}})}}; this can be improved to {{nowrap|Θ(min({{mvar|m}},{{mvar|n}}))}} by observing that at any instant, the algorithm only requires two rows (or two columns) in memory. However, this optimization makes it impossible to read off the minimal series of edit operations.<ref name="ukkonen83"/> A linear-space solution to this problem is offered by [[Hirschberg's algorithm]].<ref>{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title = The Algorithm Design Manual |publisher=[[Springer Science+Business Media]] |edition=2nd |year = 2010 |isbn=978-1-849-96720-4|bibcode=2008adm..book.....S }}</ref>{{rp|634}} A general recursive divide-and-conquer framework for solving such recurrences and extracting an optimal sequence of operations cache-efficiently in space linear in the size of the input is given by Chowdhury, Le, and Ramachandran.<ref name="CLR-08">{{cite journal |last1=Chowdhury |first1=Rezaul |last2=Le |first2=Hai-Son |last3=Ramachandran |first3=Vijaya |title=Cache-oblivious dynamic programming for bioinformatics |journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics |date=July 2010 |volume=7 |issue=3 |pages=495–510 |doi=10.1109/TCBB.2008.94 |pmid=20671320 |s2cid=2532039 |url=https://ieeexplore.ieee.org/document/4609376}}</ref>

===Improved algorithms===
Improving on the Wagner–Fisher algorithm described above, [[Esko Ukkonen|Ukkonen]] describes several variants,<ref>{{cite journal |title=Algorithms for approximate string matching |journal=Information and Control |volume=64 |issue=1–3 |year=1985 |doi=10.1016/S0019-9958(85)80046-2|url=http://www.cs.helsinki.fi/u/ukkonen/InfCont85.PDF |pages=100–118|last1=Ukkonen |first1=Esko |doi-access=free }}</ref> one of which takes two strings and a maximum edit distance {{mvar|s}}, and returns {{nowrap|min({{mvar|s}}, {{mvar|d}})}}. It achieves this by only computing and storing a part of the dynamic programming table around its diagonal. This algorithm takes time {{nowrap|O({{mvar|s}}×min({{mvar|m}},{{mvar|n}}))}}, where {{mvar|m}} and {{mvar|n}} are the lengths of the strings. Space complexity is {{nowrap|O({{mvar|s}}<sup>2</sup>)}} or {{nowrap|O({{mvar|s}})}}, depending on whether the edit sequence needs to be read off.<ref name="ukkonen83"/>

Further improvements by [[Gad Landau|Landau]], [[Eugene Myers|Myers]], and Schmidt [https://dblp.org/pers/hd/s/Schmidt:Jeanette_P=] give an {{nowrap|O({{mvar|s}}{{sup|2}} + max({{mvar|m}},{{mvar|n}}))}} time algorithm.<ref>{{cite journal |year=1998 |last1=Landau |last2=Myers |last3=Schmidt |citeseerx=10.1.1.38.1766 |title=Incremental String Comparison |journal=SIAM Journal on Computing |volume=27 |issue=2 |pages=557–582 |doi=10.1137/S0097539794264810}}</ref>

For a finite alphabet and edit costs which are multiples of each other, the fastest known exact algorithm is of Masek and Paterson<ref>{{Cite journal|last1=Masek|first1=William J.|last2=Paterson|first2=Michael S.|date=February 1980|title=A faster algorithm computing string edit distances|journal=Journal of Computer and System Sciences|volume=20|issue=1|pages=18–31|doi=10.1016/0022-0000(80)90002-1|issn=0022-0000|doi-access=free|hdl=1721.1/148933|hdl-access=free}}</ref> having worst case runtime of O(nm/logn).

==Applications==
Edit distance finds applications in [[computational biology]] and natural language processing, e.g. the correction of spelling mistakes or OCR errors, and [[approximate string matching]], where the objective is to find matches for short strings in many longer texts, in situations where a small number of differences is to be expected.

Various algorithms exist that solve problems beside the computation of distance between a pair of strings, to solve related types of problems.

* [[Hirschberg's algorithm]] computes the optimal [[Sequence alignment|alignment]] of two strings, where optimality is defined as minimizing edit distance.
* [[Approximate string matching]] can be formulated in terms of edit distance. Ukkonen's 1985 algorithm takes a string {{mvar|p}}, called the pattern, and a constant {{mvar|k}}; it then builds a [[deterministic finite state automaton]] that finds, in an arbitrary string {{mvar|s}}, a substring whose edit distance to {{mvar|p}} is at most {{mvar|k}}<ref>{{cite journal |author=Esko Ukkonen |title=Finding approximate patterns in strings |journal=J. Algorithms |volume=6 |pages=132–137 |year=1985 |doi=10.1016/0196-6774(85)90023-9}}</ref> (cf. the [[Aho–Corasick string matching algorithm|Aho–Corasick algorithm]], which similarly constructs an automaton to search for any of a number of patterns, but without allowing edit operations). A similar algorithm for approximate string matching is the [[bitap algorithm]], also defined in terms of edit distance.
* [[Levenshtein automaton|Levenshtein automata]] are finite-state machines that recognize a set of strings within bounded edit distance of a fixed reference string.<ref name="ssm"/>

== Language edit distance ==
A generalization of the edit distance between strings is the language edit distance between a string and a language, usually a [[formal language]]. Instead of considering the edit distance between one string and another, the language edit distance is the minimum edit distance that can be attained between a fixed string and ''any'' string taken from a set of strings. More formally, for any language ''L'' and string ''x'' over an alphabet {{math|Σ}}, the ''language edit distance'' d(''L'', ''x'') is given by<ref name=":0">{{cite book|doi=10.1109/focs.2016.48|chapter=Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product|chapter-url=https://theory.stanford.edu/~virgi/RNAfold.pdf|title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)|pages=375–384|year=2016|last1=Bringmann|first1=Karl|last2=Grandoni|first2=Fabrizio|last3=Saha|first3=Barna|author3-link=Barna Saha|last4=Williams|first4=Virginia Vassilevska|author-link4=Virginia Vassilevska Williams|isbn=978-1-5090-3933-3|arxiv=1707.05095|s2cid=17064578 }}</ref><math>d(L,x) = \min_{y \in L} d(x,y)

</math>, where <math>d(x,y)</math> is the string edit distance. When the language ''L'' is [[Context-free language|context free]], there is a cubic time dynamic programming algorithm proposed by Aho and Peterson in 1972 which computes the language edit distance.<ref>{{Cite journal|last1=Aho|first1=A.|last2=Peterson|first2=T.|date=1972-12-01|title=A Minimum Distance Error-Correcting Parser for Context-Free Languages|journal=SIAM Journal on Computing|volume=1|issue=4|pages=305–312|doi=10.1137/0201022|issn=0097-5397}}</ref> For less expressive families of grammars, such as the [[regular grammar]]s, faster algorithms exist for computing the edit distance.<ref>{{cite journal|doi=10.1145/360980.360995|title=Order-n correction for regular languages|journal=Communications of the ACM|volume=17|issue=5|pages=265–268|year=1974|last1=Wagner|first1=Robert A.|s2cid=11063282|doi-access=free}}</ref>

Language edit distance has found many diverse applications, such as RNA folding, error correction, and solutions to the Optimum Stack Generation problem.<ref name=":0" /><ref>{{Cite conference|last=Saha|first=B.|author-link=Barna Saha|s2cid=14806359|date=2014-10-01|title=The Dyck Language Edit Distance Problem in Near-Linear Time|conference=2014 IEEE 55th Annual Symposium on Foundations of Computer Science|pages=611–620|doi=10.1109/FOCS.2014.71|isbn=978-1-4799-6517-5}}</ref>

== See also ==
*[[Graph edit distance]]
*[[String-to-string correction problem]]
*[[String metric]]
*[[Time Warp Edit Distance]]

==References==
{{reflist|30em}}

{{Strings}}

[[Category:String metrics]]