Відстань Левенштейна: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Panas (обговорення | внесок) |
Panas (обговорення | внесок) м →Межі |
||
Рядок 66:
==Межі==
Для відстані Левенштейна існують такі верхня і нижня межі:
* Дистанція Левенштейна не
* Вона не
* Вона дорівнює 0
Мід відстанню Левенштайна та [[відстань Гемінга|відстанню Гемінга]] існують такі взаємозв'язки:
* Якщо довжина рядків різна, то верхньою межею є [[відстань Гемінга]] плюс різниця довжини рядків▼
* Для рядків однакової довжини відстань Левенштайна рівна відстані Гемінга, оскільки відстань Гемінга користується лише операцією заміни одного символу на інший і не дозволяє вставки та вилучення символів
▲* Якщо
==Подібні методи==
|