'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа#перенаправление [[Задача о редакционном расстоянии, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. == Свойства == Для расстояния Левенштейна справедливы следующие утверждения:* <math>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</math>* <math>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</math>* <math>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</math>где <math>\rm{d}(S_1,S_2)</math> — расстояние Левенштейна между строками <math>S_1</math> и <math>S_2</math>, а |S| - длина строки S. == Редакционное предписание == ''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' ({{lang-en|delete}}) — удалить, '''I''' (англ. insert) — вставить, '''R''' ({{lang-en2|replace}}) — заменить, '''M''' ({{lang-en2|match}}) — совпадение. Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований: {| class="wikitable"!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''|-|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' |||алгоритм Вагнера-|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''|}Фишера]]
