Editing Edit distance (section)

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