Изменения
→Свойства
где <tex>\rm{d}(S_1,S_2)</tex> — расстояние Левенштейна между строками <tex>S_1</tex> и <tex>S_2</tex>, а <tex>|S|</tex> — длина строки <tex>S</tex>.
Расстояние Левенштейна является [[Метрическое пространство|метрикой]], так как для него выполняются свойства.Для того чтобы доказать это достаточно доказать что выполняется неравенство треугольника:* <tex>\rm{d}(S_1,S_2) = \rm{d}(S_2,S_1)</tex> (аксиома симметрии)* <tex>\rm{d}(S_1,S_3) \leqslant \rm{d}(S_1,S_2) + \rm{d}(S_2,S_3)</tex> (аксиома треугольника или неравенство треугольника)
Пусть <tex>\rm{d}(S_1,S_3) = x</tex>, <tex>\rm{d}(S_1,S_2) = y</tex>, <tex>\rm{d}(S_2,S_3) = z</tex>. <tex>x</tex> — кратчайшее редакционное расстояние от <tex>S_1</tex> до <tex>S_3</tex>, <tex>y</tex> — кратчайшее редакционное расстояние от <tex>S_1</tex> до <tex>S_2</tex>, а <tex>z</tex> — кратчайшее редакционное расстояние от <tex>S_2</tex> до <tex>S_3</tex>. <tex>y + z</tex> — какое-то расстояние от <tex>S_1</tex> до <tex>S_3</tex>, которое зависит от <tex>S_2</tex>. <tex>\rm{d}(S_1,S_3) = \rm{d}(S_1,S_2) + \rm{d}(S_2,S_3)</tex> только в тех случаях когда <tex>S_2 = S_1</tex> или <tex>S_2 = S_3</tex>. В других случаях <tex>\rm{d}(S_1,S_3) < \rm{d}(S_1,S_2) + \rm{d}(S_2,S_3)</tex>. Следовательно, выполняется неравенство треугольника.
