Просмотр кода страницы Расстояние Левенштейна

=== Память ===
Алгоритм в виде, описанном выше, требует <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). Поэтому алгоритм можно переписать как
<source lang="text">
 для всех i от 0 до M
   для всех j от 0 до N
     вычислить D(i, j)
   если i > 0
     стереть строку D(i - 1)
 вернуть D(M, N)
</source>
или даже
<source lang="text">
 для всех i от 0 до M
   для всех j от 0 до N
     вычислить D(i, j)
     если i > 0 и j > 0
       стереть D(i - 1, j - 1)
 вернуть D(M, N)
</source>
Если требуется редакционное предписание, экономия памяти усложняется.

Для того, чтобы обеспечить время <math>\Theta(M \cdot N)</math> при памяти <math>\Theta(\min\{\,M,N\,\})</math>, определим матрицу E минимальных расстояний между ''суффиксами'' строк, то есть E(i, j) — расстояние между последними i символами <math>S_1</math> и последними j символами <math>S_2</math>. Очевидно, матрицу E можно вычислить аналогично матрице D, и так же быстро.

Теперь опишем алгоритм, считая, что <math>S_2</math> — кратчайшая из двух строк.

* Если длина одной из строк (или обеих) не больше 1, задача тривиальна. Если нет, выполним следующие шаги.
* Разделим строку <math>S_1</math> на две подстроки длиной <math>M/2</math>. (Если M нечётно, то длины подстрок будут <math>(M-1)/2</math> и <math>(M+1)/2</math>.) Обозначим подстроки <math>S_1^-</math> и <math>S_1^+</math>.
* Для <math>S_1^-</math> вычислим последнюю строку матрицы D, а для <math>S_1^+</math> — последнюю строку матрицы E.
* Найдём i такое, что <math>D(|S_1^-|, i) + E(|S_1^+|, N-i)</math> минимально. Здесь D и Е — матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение <math>S_2</math> на две подстроки, минимизирующее сумму расстояния левой половины <math>S_1</math> до левой части <math>S_2</math> и расстояния правой половины <math>S_1</math> до правой части <math>S_2</math>. Следовательно, левая подстрока <math>S_2</math> соответствует левой половине <math>S_1</math>, а правая — правой.
* Рекурсивно ищем редакционное предписание, превращающее <math>S_1^-</math> в левую часть <math>S_2</math> (то есть в подстроку <math>S2[1...i]</math>)
* Рекурсивно ищем редакционное предписание, превращающее <math>S_1^+</math> в правую часть <math>S_2</math> (то есть в подстроку <math>S2[i+1...N]</math>).
* Объединяем оба редакционных предписания.<ref>При этом во втором редакционном предписании нужно увеличить номера символов первой строки на <math>|S_1^-|</math>, а второй строки на <math>i</math>, поскольку теперь они отсчитываются с начала строк, a не с их середины.</ref>

Время выполнения удовлетворяет (с точностью до умножения на константу) условию
: <math>T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\le N'\le N</math>,
откуда следует (доказывается индукцией по M)
: <math>T(M,N) \le 2MN</math>
следовательно
: <math>T(M,N) = \Theta(M \cdot N)</math>

Требуемая память пропорциональна <math>N+N/2+N/4+...=2N</math>

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