Расстояние Левенштейна

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность мутаций в биологии[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 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}$ операций.

Алгоритм в виде, описанном выше, требует ${\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}$

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