Изменения
Нет описания правки
Для расстояния Левенштейна справедливы следующие утверждения:
* <mathtex>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</mathtex>* <mathtex>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</mathtex>* <mathtex>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</mathtex>где <mathtex>\rm{d}(S_1,S_2)</mathtex> — расстояние Левенштейна между строками <mathtex>S_1</mathtex> и <mathtex>S_2</mathtex>, а |S| - длина строки S.
== Редакционное предписание ==
Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.
Пусть <mathtex>S_1</mathtex> и <mathtex>S_2</mathtex> — две строки (длиной <mathtex>M</mathtex> и <mathtex>N</mathtex> соответственно) над некоторым алфавитом, тогда редакционное расстояние <mathtex>\rm{d}(S_1, S_2)</mathtex> можно подсчитать по следующей рекуррентной формуле:
<mathtex>\ \rm{d}(S_1, S_2) = \rm{D}(M,N)</mathtex> , где
<mathtex>\rm{D}(i, j) = \left\{\begin{array}{llcl}
0&&;&i = 0,\ j = 0\\
i&&;&j = 0,\ i > 0\\
)
\end{array}\right.
</mathtex>,
где <mathtex>\rm{m}(a,b)</mathtex> равна нулю, если <mathtex>a = b</mathtex> и единице в противном случае; <mathtex>\min(a, b, c)</mathtex> возвращает наименьший из аргументов.
=== Доказательство ===
Рассмотрим формулу более подробно. Здесь <mathtex>D(i, j)</mathtex> — расстояние между префиксами строк: первыми i символами строки <mathtex>S_1</mathtex> и первыми j символами строки <mathtex>S_2</mathtex>. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <mathtex>i</mathtex>, нужно совершить <mathtex>i</mathtex> операций удаления, а чтобы получить строку длиной <mathtex>j</mathtex> из пустой, нужно произвести <mathtex>j</mathtex> операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.
Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
* Стирание символа и замена другого символа меняются местами
Пускай <mathtex>S_1</mathtex> кончается на символ «a», <mathtex>S_2</mathtex> кончается на символ «b». Есть три варианта:# Символ «а», на который кончается <mathtex>S_1</mathtex>, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые <mathtex>i-1</mathtex> символов <mathtex>S_1</mathtex> в <mathtex>S_2</mathtex> (на что потребовалось <mathtex>D(i-1,\ j)</mathtex> операций), значит, всего потребовалось <mathtex>D(i-1,\ j)+1</mathtex> операций# Символ «b», на который кончается <mathtex>S_2</mathtex>, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили <mathtex>S_1</mathtex> в первые <mathtex>j-1</mathtex> символов <mathtex>S_2</mathtex>, после чего добавили «b». Аналогично предыдущему случаю, потребовалось <mathtex>D(i,\ j-1)+1</mathtex> операций.
# Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
## Если <mathtex>a=b</mathtex>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <mathtex>D(i-1,\ j-1)</mathtex> операций.## Если <mathtex>a\ne b</mathtex>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <mathtex>D(i-1,\ j-1)</mathtex> операций, значит, всего потребуется <mathtex>D(i-1,\ j-1)+1</mathtex> операций.
== Алгоритм Вагнера — Фишера ==
=== Память ===
Алгоритм в виде, описанном выше, требует <mathtex>\Theta(M \cdot N)</mathtex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <mathtex>\Theta(\min(M,N))</mathtex>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как
<code>
для всех i от 0 до M
