Levenshtein distance

The Levenshtein distance is a string metric used in information theory, linguistics, and computer science to quantify the difference between two sequences by counting the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one word into the other. Named after Vladimir Levenshtein, who defined it in 1965, it is also known as edit distance. The article provides a recursive definition, an example using "kitten" and "sitting", and discusses its upper and lower bounds. It highlights applications in approximate string matching (e.g., spell checkers, OCR, translation memory), linguistics for quantifying language differences, speech-identification tests, and bioinformatics for comparing biological sequences like DNA and proteins. Various computational methods, including iterative dynamic programming algorithms (like Wagner–Fischer), automata, and approximation techniques, are detailed, along with its computational complexity.