Расстояние Левенштейна — edit-distance метрика, которая определяет минимальное число односимвольных вставок, удалений или замен, необходимых для преобразования одной строки в другую. Она широко используется в исправлении орфографии, fuzzy matching, связывании записей и других задачах, где нужна приблизительная текстовая близость.
An edit distance metric that calculates the fewest delete, insert, and substitute operations required to change one word to another. For example, the Levenshtein distance between the words "heart" and "darts" is three because the following three edits are the fewest changes to turn one word into the other: 1. heart deart (substitute "h" with "d") 2. deart dart (delete "e") 3. dart darts (insert "s") Note that the preceding sequence isn't the only path of three edits.