Машек и Патерсон [Masek, Paterson, 1980] применили к процедуре вычисления расстояния между строками Вагнера и Фишера подход 'четырех русских' (Арлазарова, Диница, Кронрода и Фараджева [Arlazarov, Dinic, Kronrod, Faradzev, 1970]) и получили алгоритм, выполняющийся за время O(n2/log n). Он и описан ниже. Матрица расстояний d разбивается на совокупность квадратных подматриц с перекрывающимися крайними векторами. Подматрица (i, j, p) определяется как подматрица размерности (p+1) * (p+1), левым верхним элементом которой является di,j. Из определения (11) входов матрицы d видно, что значения подматрицы (i, j, p) выводятся из ее соответствующих подстрок x(i+1, i+p) и y(j+1, j+p) и начальных векторов, то есть, ее верхней строки (di,j, di,j+1,: di,j+p) и левого столбца (di,j, di+1,j,...,di+p,j). На первом этапе алгоритма вычисляются значения конечных векторов, то есть нижней строки и правого столбца, для всех возможных подматриц (i, j, p) любой матрицы d для данных алфавита и функции цены. Это требует перечисления всех подматриц, для чего нужны списки всех комбинаций возможных подстрок и начальных векторов. Чтобы перечислить все возможные подстроки длины p, мы должны считать, что алфавит конечен. Кроме того, попытки перечислить все возможные начальные вектора могут быть запрещены. Однако, ограничение цен редактирования таким образом, чтобы они стали интегральными множителями некоторых действительных чисел приведет к тому, что они станут всего лишь конечным числом разностей между последовательными значениями d для всех матриц расстояний, использующих один и тот же алфавит и функцию цены. Гораздо практичнее использовать эти разности, чем абсолютные значения. Определяя шаг как разность между любыми двумя горизонтально или вертикально смежными элементами матриц, приходим к следующему следствию правила (11) вычисления di,j: (42) Каждую подматрицу можно, таким образом, вывести по соответствующим подстрокам x(i+1, i+p) и y(j+1, j+p), начальному значению di,j, и начальным векторам - верхней строке (di,j+1 - di,j, ... , di,j+p - di,j+p-1) и первому столбцу (di+1,j - di,j, :, di+p,j - di+p-1,j). Перечисление всех возможных подматриц может быть достигнуто перечислением всех пар строк длины p над конечным алфавитом C, и всех пар векторов шага длины p. Алгоритм для вычисления всех подматриц приведен на рисунке 17. Строки длины p и вектора шага длины p перечисляются в алфавитном порядке, предполагая фиксированное упорядочение на C и на конечном множестве возможных значений шага. Подматрица шага вычисляется для каждой пары строк u и v, и каждой пары векторов начального шага T и L, в соответствии с (42). Чтобы облегчить последующее продвижение, процедура store сохраняет векторы конечного шага B и R, подматрицы, определенной u, v. T и L. В процедуре вычисляются две матрицы шагов: V содержит значения вертикального шага, а H - горизонтального. for каждой пары строк u, vCp for каждой пары векторов шага длины p T, L - инициализация векторов начального шага for i = 1 to p Vi,0 = Li H0,i = Ti - вычислить входы матриц шага for i = 1 to p for j = 1 to p -сохранение результатов R = (V1,p, V2,p, ... , Vp,p) B = (Hp,1, Hp,2, ... , Hp,p) store(R, B, L, T, u, v) Рисунок 17: Вычисление подматрицы в методе Машека-Патерсона Так как самый внутренний цикл выполняется постоянное время и повторяется ровно p2 раз для каждой пары строк и векторов шага, каждая подматрица вычисляется за время O(p2). Число пар строк длины p над алфавитом равно 2p. Если s - мощность этого множества возможных значений шага, которое мы будем считать конечным, то всего имеется s2p различных пар векторов шага длины p. Таким образом, всего имеется (s * )2p различных подматриц, что в общей сложности дает время обработки O(p2(s * 2p). Ранее мы объявили, что при ограничениях на функцию цены множество возможных значений шага является конечным. Рассмотрим это утверждение поближе. Из правила для di,j и граничных условий (11)-(12) можно видеть, что значения шага ограничены, вне зависимости от того, какие строки рассматриваются: -I < (di,j - di-1,j) < D -D < (di,j - di,j-1) < I где D = max{w(a,) : aC} I = max{w(,b) : bC} (43) Функцию цены называют разреженной, если каждый член множества ценовых весов, а именно {w(a, ) : a} {w(b, ) : b} {w(a, b) : a, b}, является целым множителем некоторой константы r. Для конечных алфавитов можно показать, что, если функция цены является разреженной, то множество полученных в матрице значений шага является конечным независимо от конкретных строк, что подтверждает сделанное ранее утверждение. - инициализация первого столбца крайних левых подматриц шага for i = 1 to m/p Pi,0 = (w(x(i-1)p+1, e), w(x(i-1)p+2, e), . . . , w(xip, e)) - инициализация верхней строки самых верхних подматриц for j = 1 to n/p Q0,j = (w(e, y(j-1)p+1), w(e, y(j-1)p+2), . . . , w(e, yjp)) - поиск конечных векторов шага для подматриц for i = 1 to m/p for j = 1 to n/p Pi,j,Qi,j = fetch(Pi,j-1,Qi-1,j,x((i-1)p+1,ip),y((j-1)p+1,jp)) - суммирование приращений расстояния для получения dm,n d = 0 for i = 1 to m/p d = d + sum(Pi,0) for j = 1 to n/p d = d + sum(Qm/p,j) Рисунок 18: Вычисление расстояния по Машеку-Патерсону Алгоритм для вычисления расстояния между строками по подматрицам приведен на рисунке 18. Пусть m mod p = n mod p = 0, i и j горизонтальный и вертикальный шаги через подматрицы, соответственно. P - это подматрица векторов столбцов подматрицы шага длины p, таких, что Pi,j является самым правым столбцом подматрицы (i, j), совпадающим с левым столбцом подматрицы (i, j + 1), так как смежные подматрицы (p + 1) * (p + 1) имеют общий столбец. Аналогично, Q - это матрица векторов строк подматрицы шага длины p, такая, что Qi,j является нижней строкой подматрицы (i, j), совпадающей с верхней строкой подматрицы (i + 1, j). Нулевые столбец и строка, соответственно, P и Q, инициализируются с шагами, соответствующими граничным условиям массива расстояний, задаваемыми (12). Процедура fetch возвращает самый правый столбец и нижнюю строку подматрицы (i, j), выбирая вычисленные значения, адресуемые самым левым столбцом и верхней строкой подматрицы вместе с соответствующими подстроками. Наконец, расстояние dm,n между двумя входными строками вычисляется суммированием разностных расстояний вдоль пути из d0,0 в dm,n. Функция sum, применяемая на этом этапе, возвращает сумму своих векторных аргументов. Инициализация в этом алгоритме выполняется за линейное время, как и конечное суммирование для получения требуемого расстояния. Стадия основных вычислений включает 2mn/p2 просмотров и перекодировок p-мерных векторов, и, таким образом, требует время O(mn/p). Как уже говорилось, предварительные вычисления подматриц требуют время O(p2c2p), где c = s * |C|. Если p берется равным min[{logc m, n}/2], то время предварительных вычислений асимптотически меньше времени основных. Таким образом, если учитывать время предварительных вычислений, расстояние определяется за время O(mn/p). Эта граница сохраняется, даже когда m и n не кратны p. В этом случае в конец строк x и y приписывают вспомогательные символы, не встречающиеся них, например, , чтобы длины строк стали интегральными множителями p. Цены редактирования для будут следующими: w(,) = 0w(, ) = 0w(a, ) = w(a, )   aw(, b) = w(, b))   b     (44) Фактическую последовательность редактирования минимальной цены можно получить с помощью метода, близкому к перебору с возвратами Вагнера и Фишера. Требуемые для этого расстояния редактирования можно получить либо перевычисляя подматрицы, через которые проходит путь оптимального редактирования, либо сохраняя заполненные подматрицы во время предварительных вычислений. Последний подход позволяет определять последовательность редактирования по заполненным матрицам P и Q и заранее вычисленным подматрицам за линейное время и требует O(n log2n) памяти для хранения подматриц. Обратите внимание, что матрицы P и Q требуют по (1 + m/p) * (1 + n/p) * p ячеек каждая, что составляет O(n2/log n). Таким образом, всего при этом методе требуется O(n2/log n) памяти. Этот алгоритм можно также применить к задаче нахождения lcs(x, y), используя функцию цены, задаваемую (15). Взаимосвязь между d(x, y) и |l(x, y)|, задаваемая выражением (16), позволяет затем вычислить длину lcs за время O(n2 * log n). Саму lcs можно получить с помощью метода, похожего на используемый для получения оптимальной последовательности редактирования. Было показано, что вычисление расстояний между строками с помощью этого метода асимптотически быстрее, чем квадратичный метод Вагнера и Фишера. Однако, на практике реальный выигрыш можно получить только для очень длинных строк. Чтобы проиллюстрировать это, Машек и Патерсон [Masek, Patterson, 1983] вычислили, что для бинарного алфавита и ценовой функции расстояния редактирования, лучшая эффективность достигается только для строк, длина которых превышает 262418.  8  Комментарии к статье  8 8  Обсудить в чате