Editing Edit distance (section)

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