Levenshteintávolság

Levenshteintávolság, often referred to as edit distance, is a metric for measuring the difference between two sequences. It is defined as the minimum number of single-character edits—insertions, deletions, or substitutions—required to change one word into the other. For example, the Levenshteintávolság between "kitten" and "sitting" is 3 because you can change "kitten" to "sitting" by: 1. substituting 'k' with 's', 2. substituting 'e' with 'i', and 3. appending 'g'.

The concept was introduced by Vladimir Levenshtein in 1965. The algorithm to calculate Levenshteintávolság typically uses dynamic programming. A matrix is constructed where each cell (i, j) represents the Levenshteintávolság between the first i characters of the first string and the first j characters of the second string. The value of each cell is computed based on the values of its neighboring cells, considering the cost of insertion, deletion, and substitution.

Levenshteintávolság has numerous applications in fields such as natural language processing, spell checking, DNA sequencing, and plagiarism detection. In spell checkers, it helps identify misspelled words by finding dictionary words with a small edit distance to the user's input. In bioinformatics, it is used to compare DNA or protein sequences to identify similarities and evolutionary relationships. The calculation can be computationally intensive for very long sequences, but optimized algorithms exist.