Co je to Levenshteinova vzdálenost?

Levenshteinova vzdálenost mezi dvěma řetezci se definuje jako minimální počet znaků, které musíte nahradit, vložit nebo smazat, abyste změnili řetezec1 na řetezec2.

Například Levenshteinova vzdálenost mezi řetězcem "KAMIL" a řetezcem "OMYL" je 3. (Změnilo se písmeno A a I a písmeno K bylo smazáno)

Levenshteinova vzdálenost tedy vyjadřuje podobnost (resp. rozdílnost) dvou řetězců.

Občas se nazývá "změnová vzdálenost" nebo také "editační vzdálenost" (edit distance)...