Odległość Levenshteina – miara różnicy między dwoma napisami lub, szerzej, skończonymi ciągami symboli. Jest równa najmniejszej liczbie operacji wstawienia, usunięcia i zamiany pojedynczego symbolu potrzebnych do przekształcenia jednego ciągu w drugi. W klasycznej definicji każda z tych operacji ma koszt równy 1V. I. Levenshtein, „Binary codes capable of correcting deletions, insertions, and reversals”, Doklady Akademii Nauk SSSR, t. 163, nr 4, 1965, s. 845–848; przekład angielski: Soviet Physics Doklady, t. 10, nr 8, 1966, s. 707–710. Math-Net..
Nazwa pochodzi od nazwiska radzieckiego matematyka Władimira Lewensztejna, który wprowadził tę miarę w 1965 roku w kontekście kodów korygujących błędy. Odległość Levenshteina jest jednym z podstawowych rodzajów odległości edycyjnej. Określenie „odległość edycyjna” bywa używane także szerzej, dla modeli, w których zmienia się zbiór dopuszczalnych operacji lub ich kosztyGonzalo Navarro, „A guided tour to approximate string matching”, ACM Computing Surveys, t. 33, nr 1, 2001, s. 31–88, doi:10.1145/375360.375365..
Definicja Niech
oraz
będą dwoma ciągami.