Editing Edit distance (section)

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