Расстояние Левенштейна (редакционное расстояние, дистанция редактирования) — метрика, измеряющая по модулю разность между двумя последовательностями символов. Она определяется как минимальное количество односимвольных операций (а именно вставки, удаления, замены), необходимых для превращения одной последовательности символов в другую. В общем случае, операциям, используемым в этом преобразовании, можно назначить разные цены. Широко используется в теории информации и компьютерной лингвистике.

Впервые задачу поставил в 1965 году советский математик Владимир Левенштейн при изучении последовательностей ${\displaystyle 0-1}$^[1], впоследствии более общую задачу для произвольного алфавита связали с его именем. Большой вклад в изучение вопроса внёс Дэн Гасфилд^[2].

Расстояние Левенштейна и его обобщения активно применяется:

• для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированного текста или речи).
• для сравнения текстовых файлов утилитой diff и ей подобными. Здесь роль «символов» играют строки, а роль «строк» — файлы.
• в биоинформатике для сравнения генов, хромосом и белков.

С точки зрения приложений определение расстояния между словами или текстовыми полями по Левенштейну обладает следующими недостатками:

1. При перестановке местами слов или частей слов получаются сравнительно большие расстояния;
2. Расстояния между совершенно разными короткими словами оказываются небольшими, в то время как расстояния между очень похожими длинными словами оказываются значительными.

Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) — удалить, I (англ. insert) — вставить, R (replace) — заменить, M (match) — совпадение.

Например, для 2 строк «CONNECT» и «CONEHEAD» можно построить следующую таблицу преобразований:

Найти только расстояние Левенштейна — более простая задача, чем найти ещё и редакционное предписание (подробнее см. ниже).

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность мутаций в биологии^[3], разную вероятность разных ошибок при вводе текста и т. д. В общем случае:

• w(a, b) — цена замены символа a на символ b
• w(ε, b) — цена вставки символа b
• w(a, ε) — цена удаления символа a

Необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при

• w(a, а) = 0
• w(a, b) = 1 при a≠b
• w(ε, b) = 1
• w(a, ε) = 1

Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует неравенство треугольника: замена двух последовательных операций одной не увеличит общую цену (например, замена символа x на y, а потом y на z не лучше, чем сразу x на z).

Если к списку разрешённых операций добавить транспозицию (два соседних символа меняются местами), получается расстояние Дамерау — Левенштейна. Для неё также существует алгоритм, требующий O(MN) операций. Дамерау показал, что 80 % ошибок при наборе текста человеком являются транспозициями. Кроме того, расстояние Дамерау — Левенштейна используется и в биоинформатике.

Здесь и далее считается, что элементы строк нумеруются с первого, как принято в математике, а не с нулевого, как принято во многих языках программирования.

Пусть ${\displaystyle S_{1}}$ и ${\displaystyle S_{2}}$ — две строки (длиной ${\displaystyle M}$ и ${\displaystyle N}$ соответственно) над некоторым алфавитом, тогда редакционное расстояние (расстояние Левенштейна) ${\displaystyle {\rm {d}}(S_{1},S_{2})}$ можно подсчитать по следующей рекуррентной формуле

${\displaystyle \ {\rm {d}}(S_{1},S_{2})=D(M,N)}$ , где

${\displaystyle D(i,j)=\left\{{\begin{array}{llcl}0,&&&i=0,\ j=0\\i,&&&j=0,\ i>0\\j,&&&i=0,\ j>0\\\min\{\\&D(i,j-1)+1,\\&D(i-1,j)+1,&&j>0,\ i>0\\&D(i-1,j-1)+{\rm {m}}(S_{1}[i],S_{2}[j])\\\}\end{array}}\right.}$,

где ${\displaystyle {\rm {m}}(a,b)}$ равна нулю, если ${\displaystyle a=b}$ и единице в противном случае; ${\displaystyle \min\{\,a,b,c\,\}}$ возвращает наименьший из аргументов.

Здесь шаг по ${\displaystyle i}$ символизирует удаление (D) из первой строки, по ${\displaystyle j}$ — вставку (I) в первую строку, а шаг по обоим индексам символизирует замену символа (R) или отсутствие изменений (M).

Очевидно, справедливы следующие утверждения:

• ${\displaystyle {\rm {d}}(S_{1},S_{2})\geqslant {\bigl |}|S_{1}|-|S_{2}|{\bigr |}}$
• ${\displaystyle {\rm {d}}(S_{1},S_{2})\leqslant \max {\bigl (}|S_{1}|,|S_{2}|{\bigr )}}$
• ${\displaystyle \mathop {\rm {d}} (S_{1},S_{2})=0\Leftrightarrow S_{1}=S_{2}}$

Рассмотрим формулу более подробно. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной ${\displaystyle i}$, нужно совершить ${\displaystyle i}$ операций удаления, а чтобы получить строку длиной ${\displaystyle j}$ из пустой, нужно произвести ${\displaystyle j}$ операций вставки.

Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:

• Две замены одного и того же символа — неоптимально (если мы заменили x на y, потом — y на z, выгоднее было сразу заменить x на z).
• Две замены разных символов можно менять местами
• Два стирания или две вставки можно менять местами
• Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
• Стирание и вставку разных символов можно менять местами
• Вставка символа с его последующей заменой — неоптимально (излишняя замена)
• Вставка символа и замена другого символа меняются местами
• Замена символа с его последующим стиранием — неоптимально (излишняя замена)
• Стирание символа и замена другого символа меняются местами

Пусть ${\displaystyle S_{1}}$ кончается на символ «a», ${\displaystyle S_{2}}$ кончается на символ «b». Есть три варианта:

1. Символ «а», на который кончается ${\displaystyle S_{1}}$, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые ${\displaystyle i-1}$ символов ${\displaystyle S_{1}}$ в ${\displaystyle S_{2}}$ (на что потребовалось ${\displaystyle D(i-1,\ j)}$ операций), значит, всего потребовалось ${\displaystyle D(i-1,\ j)+1}$ операций
2. Символ «b», на который кончается ${\displaystyle S_{2}}$, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили ${\displaystyle S_{1}}$ в первые ${\displaystyle j-1}$ символов ${\displaystyle S_{2}}$, после чего добавили «b». Аналогично предыдущему случаю, потребовалось ${\displaystyle D(i,\ j-1)+1}$ операций.
3. Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то, чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
   1. Если ${\displaystyle a=b}$, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили ${\displaystyle D(i-1,\ j-1)}$ операций.
   2. Если ${\displaystyle a\neq b}$, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить ${\displaystyle D(i-1,\ j-1)}$ операций, значит, всего потребуется ${\displaystyle D(i-1,\ j-1)+1}$ операций.

Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя вышеприведённую формулу. Её можно вычислять как по строкам, так и по столбцам. Псевдокод алгоритма:

 для всех i от 0 до M
   для всех j от 0 до N
     вычислить D(i, j)
 вернуть D(M, N)

Или в более развёрнутом виде, и при произвольных ценах замен, вставок и удалений:

 D(0, 0) = 0
 для всех j от 1 до N
   D(0, j) = D(0, j - 1) + цена вставки символа S2[j]
 для всех i от 1 до M
   D(i, 0) = D(i - 1, 0) + цена удаления символа S1[i]
 для всех j от 1 до N
   D(i, j) = min{
     D(i - 1, j) + цена удаления символа S1[i],
     D(i, j - 1) + цена вставки символа S2[j],
     D(i - 1, j - 1) + цена замены символа S1[i] на символ S2[j]
   }
 вернуть D(M, N)

(Напоминаем, что элементы строк нумеруются с первого, а не с нулевого.)

Для восстановления редакционного предписания требуется вычислить матрицу D, после чего идти из правого нижнего угла (M,N) в левый верхний, на каждом шаге ища минимальное из трёх значений:

• если минимально (${\displaystyle D(i-1,j)}$+ цена удаления символа S1[i]), добавляем удаление символа S1[i] и идём в (i-1, j)
• если минимально (${\displaystyle D(i,j-1)}$+ цена вставки символа S2[j]), добавляем вставку символа S2[j] и идём в (i, j-1)
• если минимально (${\displaystyle D(i-1,j-1)}$+ цена замены символа S1[i] на символ S2[j]), добавляем замену S1[i] на S2[j] (если они не равны; иначе ничего не добавляем), после чего идём в (i-1, j-1)

Здесь (i, j) — клетка матрицы, в которой мы находимся на данном шаге. Если минимальны два из трёх значений (или равны все три), это означает, что есть 2 или 3 равноценных редакционных предписания.

Этот алгоритм называется алгоритмом Вагнера — Фишера. Он предложен Р. Вагнером (R. A. Wagner) и М. Фишером (M. J. Fischer) в 1974 году.^[4]

Алгоритм в виде, описанном выше, требует ${\displaystyle \Theta (M\cdot N)}$ операций и такую же память. Последнее может быть неприятным: так, для сравнения файлов длиной в 10⁵ строк потребуется около 40 гигабайт памяти.

Если требуется только расстояние, легко уменьшить требуемую память до ${\displaystyle \Theta (\min\{\,M,N\,\})}$. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как

 для всех i от 0 до M
   для всех j от 0 до N
     вычислить D(i, j)
   если i > 0
     стереть строку D(i - 1)
 вернуть D(M, N)

или даже

 для всех i от 0 до M
   для всех j от 0 до N
     вычислить D(i, j)
     если i > 0 и j > 0
       стереть D(i - 1, j - 1)
 вернуть D(M, N)

Если требуется редакционное предписание, экономия памяти усложняется.

Для того, чтобы обеспечить время ${\displaystyle \Theta (M\cdot N)}$ при памяти ${\displaystyle \Theta (\min\{\,M,N\,\})}$, определим матрицу E минимальных расстояний между суффиксами строк, то есть E(i, j) — расстояние между последними i символами ${\displaystyle S_{1}}$ и последними j символами ${\displaystyle S_{2}}$. Очевидно, матрицу E можно вычислить аналогично матрице D, и так же быстро.

Теперь опишем алгоритм, считая, что ${\displaystyle S_{2}}$ — кратчайшая из двух строк.

• Если длина одной из строк (или обеих) не больше 1, задача тривиальна. Если нет, выполним следующие шаги.
• Разделим строку ${\displaystyle S_{1}}$ на две подстроки длиной ${\displaystyle M/2}$. (Если M нечётно, то длины подстрок будут ${\displaystyle (M-1)/2}$ и ${\displaystyle (M+1)/2}$.) Обозначим подстроки ${\displaystyle S_{1}^{-}}$ и ${\displaystyle S_{1}^{+}}$.
• Для ${\displaystyle S_{1}^{-}}$ вычислим последнюю строку матрицы D, а для ${\displaystyle S_{1}^{+}}$ — последнюю строку матрицы E.
• Найдём i такое, что ${\displaystyle D(|S_{1}^{-}|,i)+E(|S_{1}^{+}|,N-i)}$ минимально. Здесь D и Е — матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение ${\displaystyle S_{2}}$ на две подстроки, минимизирующее сумму расстояния левой половины ${\displaystyle S_{1}}$ до левой части ${\displaystyle S_{2}}$ и расстояния правой половины ${\displaystyle S_{1}}$ до правой части ${\displaystyle S_{2}}$. Следовательно, левая подстрока ${\displaystyle S_{2}}$ соответствует левой половине ${\displaystyle S_{1}}$, а правая — правой.
• Рекурсивно ищем редакционное предписание, превращающее ${\displaystyle S_{1}^{-}}$ в левую часть ${\displaystyle S_{2}}$ (то есть в подстроку ${\displaystyle S2[1...i]}$)
• Рекурсивно ищем редакционное предписание, превращающее ${\displaystyle S_{1}^{+}}$ в правую часть ${\displaystyle S_{2}}$ (то есть в подстроку ${\displaystyle S2[i+1...N]}$).
• Объединяем оба редакционных предписания.^[5]

Время выполнения удовлетворяет (с точностью до умножения на константу) условию

${\displaystyle T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\leq N'\leq N}$,

откуда следует (доказывается индукцией по M)

${\displaystyle T(M,N)\leq 2MN}$

следовательно

${\displaystyle T(M,N)=\Theta (M\cdot N)}$

Требуемая память пропорциональна ${\displaystyle N+N/2+N/4+...=2N}$

Кроме того, есть алгоритмы, экономящие память за счёт существенного замедления, например, время становится кубическим, а не квадратичным, по длине строк.

	Имеется викиучебник по теме «Реализации алгоритмов/Расстояние Левенштейна»

Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Оформить математические формулы Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.