Editing Edit distance (section)

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