29
правок
Изменения
→Свойства
* <tex>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</tex>
где <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) = 0 \Leftrightarrow S_1 = S_2</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>S_1</tex> до <tex>S_2</tex> равно <tex>x</tex>. Значит, нам нужно проделать x операций со строкой <tex>S_1</tex> чтобы получить <tex>S_2</tex>. Значит, у нас есть последовательность из <tex>x</tex> операций. Заменим в этой последовательности <tex>delete(a)</tex> на <tex>insert(a)</tex>, <tex>insert(a)</tex> на <tex>delete(a)</tex>, а <tex>swap(a, b)</tex> на <tex>swap(b, a)</tex> и проделаем все действия, начиная с последнего со строкой <tex>S_2</tex>. Получим строку <tex>S_1</tex> за минимальное количество операций. Следовательно, выполняется аксиома симметрии.
<tex>insert(a)</tex> — вставка элемента <tex>a</tex>, <tex>delete(a)</tex> — удаление элемента <tex>a</tex>, <tex>swap(a, b)</tex> — замена <tex>a</tex> на <tex>b</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>. Следовательно, выполняется неравенство треугольника.
== Разные цены операций ==
