Изменения
→Доказательство
## Если <math>a=b</math>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <math>D(i-1,\ j-1)</math> операций.
## Если <math>a\ne b</math>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <math>D(i-1,\ j-1)</math> операций, значит, всего потребуется <math>D(i-1,\ j-1)+1</math> операций.
== Алгоритм Вагнера — Фишера ==
Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
Псевдокод алгоритма? написанный при произвольных ценах замен, вставок и удалений(важно помнить, что элементы нумеруются с 1):
<code>
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)
</code>
=== Память ===
Алгоритм в виде, описанном выше, требует <math>\Theta(M \cdot N)</math> операций и такую же память. Последнее может быть неприятным: так, для сравнения файлов длиной в 10<sup>5</sup> строк потребуется около 40 гигабайт памяти.
Если требуется только расстояние, легко уменьшить требуемую память до <math>\Theta(\min(M,N))</math>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как
<code>
для всех i от 0 до M
для всех j от 0 до N
вычислить D(i, j)
если i>0 и j>0
стереть D(i-1, j-1)
вернуть D(M, N)
</code>
