'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа#перенаправление [[Задача о редакционном расстоянии, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. == Свойства == Для расстояния Левенштейна справедливы следующие утверждения:* <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''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение. Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований: {| border="1"|'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''|-|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' |||-|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4''' |алгоритм Вагнера-}Фишера]]
