19
правок
Изменения
Добавил рекурсивный алгоритм поиска редакционного предписания с линейным использованием памяти
вернуть D(M, N)
</code>
== Рекурсивный алгоритм ==
Для того, чтобы обеспечить время <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>.
* Для вычислим последнюю строку матрицы D для строк <math>S_1^-</math> и <math>S_2</math>, последнюю строку матрицы E для строк <math>S_1^+</math> и <math>S_2</math>.
* Найдём 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>S_2[1...i]</math>)
* Рекурсивно ищем редакционное предписание, превращающее <math>S_1^+</math> в правую часть <math>S_2</math> (то есть в подстроку <math>S_2[i+1...N]</math>).
* Объединяем оба редакционных предписания.
В псевдокоде:
<code>
String levensteinInstruction(String s1, String s2){
if ( s1.length() <= 1 || s2.length() <= 1 )
{Решаем тривиально, возвращаем редакционное предписание}
//Иначе:
String s1l,s1r,s2l,s2r;
if ( s2.length() < s1.length() ){
s1l = s1.substring(0, s1.length() / 2); //<math>S_1^-</math>
s1r = s1.substring(s1.length() / 2, s1.length()); //<math>S_1^+</math>
int [] d = calcD(s1l, s2); //Вычисляем последнюю строку матрицы D для <math>S_1^-</math> и <math>S_2</math>
int [] e = calcE(s1r, s2); //Вычисляем последнюю строку матрицы E для <math>S_1^+</math> и <math>S_2</math>
int k = 0;
for (int i = 1; i <= s2.length(); i++) {
if (d[i] + e[s2.length() - i] < d[k] + e[s2.length() - k]) {
k = i;
}
}
s2l = s2.substring(0, k);
s2r = s2.substring(k, s2.length());
} else {
//s1 - меньшая строка
s2l = s2.substring(0, s2.length() / 2); //<math>S_2^-</math>
s2r = s2.substring(s2.length() / 2, s2.length()); //<math>S_2^+</math>
int [] d = calcD(s2l, s1); //Вычисляем последнюю строку матрицы D для <math>S_2^-</math> и <math>S_1</math>
int [] e = calcE(s2r, s1); //Вычисляем последнюю строку матрицы E для <math>S_2^+</math> и <math>S_1</math>
int k = 0;
for (int i = 1; i <= s1.length(); i++) {
if (d[i] + e[s1.length() - i] < d[k] + e[s1.length() - k]) {
k = i;
}
}
s1l = s1.substring(0, k);
s1r = s1.substring(k, s1.length());
}
return levensteinInstruction(s1l, s2l) + levensteinInstruction(s1r, s2r);
}
</code>
Время выполнения удовлетворяет (с точностью до умножения на константу) условию
: <math>T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\le N'\le N</math>,
Докажем:
: <math>T(M,N) \le 2MN</math>
База индукции очевидна
: <math>T(1,N) = N \le 2N</math>
Пусть для всех <math>M' < M</math> выполнено <math>T(M',N') \le 2M'N'</math>.
Тогда учитывая <math>T(M/2,N') \le 2(M/2)N'</math>, <math>T(M/2,N-N') \le 2(M/2)(N-N')</math>, получим:
: <math>T(M,N)=MN+T(M/2,N')+T(M/2,N-N') \le</math> <math> MN+2(M/2)N'+2(M/2)(N-N')=2MN</math>
следовательно
: <math>T(M,N) = \Theta(M \cdot N)</math>
Для вычисления последних строк матриц D, E можно использовать два глобальных двумерных массива размера <math>2 \times (min(M, N)+1)</math>.
Т.к. мы вычисляем функцию рекурсивно, требуемый размер стека тоже следует учесть. На стек вызовов потребуется <math>\Theta(log(max(M,N))</math> памяти, потому общая оценка использования памяти будет <math> \Theta(min(M,N)) </math>
== Редакционное предписание ==
== Литература ==
[http://en.wikipedia.org/wiki/Levenshtein_distance Wikipedia - Levenshtein distance]
[http://pastie.org/5574488 Реализация рекурсивного алгоритма поиска редакционного предписания на языке Java]
Романовский И.В. "Дискретный анализ". Третье издание. Стр. 103 - 105
