Поиск в строках, массивах, последовательностях:
Общие подпоследовательности, дистанция.

Укконен.

Метод вычисления расстояния между двумя строками и получения минимальной последовательности операций редактирования Укконена [Ukkonen, 1985] основан на подходе динамического программирования, однако требует O(dm) времени и памяти, где d – это расстояние между строками x и y, а m – меньшая из длин двух строк. Таким образом, этот метод эффективен, когда расстояния между строками малы, то есть когда строки похожи. Основная идея алгоритма состоит в нахождении самого дешевого пути в направленном графе в матрице d_i,j, в процессе чего избегаются ненужные вычисления d_i,j.

Как и ранее, будем считать, что m < n. Вспомним, что в методе динамического программирования d_i,j получают, выбирая минимальное из полученных с учетом предварительно вычисленных для соседей значений согласно формуле (11). По завершении вычисления d_m,n, последовательность операций редактирования минимальной цены получают прослеживанием пути через матрицу, состоящего из переходов, дающих минимальные d_i,j.

Зависимости между элементами матрицы d можно представить направленными дугами – дуга из (i, j) в (i', j') существует только если d_i'j' получено из d_i,j. Полученный в результате граф зависимостей является подграфом графа, состоящего из всех узлов (i, j) и вертикальных, горизонтальных и диагональных (от верхнего левого к нижнему правому) дуг, соединяющих смежные узлы. Эти дуги означают, соответственно, удаления, вставки, а также замены и сопоставления. Поэтому с дугами можно сопоставить цены этих операций, и значение d_i,j будет, таким образом, задаваться суммой весов по любом пути из (0, 0) в (i, j). Взаимосвязь между дугами и ценами следующая.

d_i-1,jd_i,j   w(x_i,)

d_i,j-1d_i,j   w(, y_j)

d_i-1,j-1d_i,j   w(x_i,y_j)

Конечные значения на пути из (i,j) в (i', j') в графе зависимостей связаны следующим соотношением, где d – сумма цен всех дуг в пути:

Расстояние d_i,j между двумя строками является, таким образом, минимальной общей ценой пути из d_0,0 в d_m,n в графе зависимости.

Для определения самого дешевого пути в графе (Ахо, Хопкрофт и Ульман [Aho, Hopcroft, Ullman, 1974]) можно использовать алгоритм Дийкстры (Dijkstra), который сделает это за время O(mn log mn). Однако, топология графа позволяет найти и более эффективное решение, например, метод динамического программирования. Ниже будет показано, как можно сократить число входов массива d, которые нужно вычислить.

Значение d_m,n вычисляется только по входам d_i,j на некотором пути из (0,0) в (m,n). Обратите внимание, что его вычисление требует времени O(n), так как любой такой путь содержит не больше m+n дуг. Рассмотрим задачу выяснения, превосходит ли d_m,n некоторый порог, скажем, h. Из 11 можно видеть, что значения d_ij монотонно возрастают вдоль любого пути в графе зависимости. Таким образом, если d_m,n < h, а некоторое d_i,j > h, то это d_i,j не может являться частью пути в (m, n).

Обозначим через w_min минимальную цену всех вставок и удалений, то есть

wmin = min{w(a, ), w(, a) : a}

(46)

для алфавита . Для ненулевых положительных весов w_min > 0. Кроме того, пронумеруем диагонали матрицы расстояний целыми числами k[-m, n] таким образом, чтобы диагональ k состояла из элементов (i, j), у которых j - i = k.

Рассмотрим произвольный путь из (i, j) в (i', j') в графе зависимости. Элемент (i, j) лежит на диагонали k = j - i, а (i', j') – на диагонали k' = j' - i'. Если k' - k < 0, то путь содержит не меньше |k' - k| удалений (вертикальных дуг), а если k' - k > 0, не меньше |k' - k| вставок (горизонтальных дуг). Из (45) мы имеем следующее:

Таким образом, d_i,j > |j - i|*w_min для каждого (i, j) на пути из (0,0) в (m, n). Кроме того, так как d_i,j < d_m,n для любого (i, j) в пути, мы имеем следующее:

Для вычисления d_m,n достаточно рассмотреть элементы на диагональной ленте d_m,n/w_min < j - i < d_m,n/w_min. На самом деле, эту ленту можно сузить еще больше, что и будет показано ниже.

Рассмотрим путь из (0, 0) в (m, n) в графе зависимости. Его можно разложить на два пути: из (0, 0) в (i, j) и из (i, j) в (m, n). Из (47) мы имеем следующее:

dm,n > d0,0 + |j - i|*wmin + |(n - m) - (j - i)| * wmindm,n > (|j - i| + |(n - m) - (j - i)| * wmin

(49)

Рассмотрим два случая: первый, когда j < i, а второй, когда j > i. В первом случае (49) принимает вид

dm,n > (-(j - i) + n - m - (j - i))wmindm,n/wmin - (n - m) > -2(j - i)

(50)

С учетом того, что j - i целое число!!!!!!!!!!!!!!!!Ј 0, отсюда вытекает

(51)

Для случая, когда j > i, рассмотрим две возможности, а именно, n - m > j - i, и n - m < j - i. В первом случае (49) принимает вид

dm,n > (j - i + n - m - (j - i))wmindm,n/wmin > n - m

(52)

а во втором

dm,n > (j - i + j - i - (n - m))wmin dm,n/wmin - (n - m) > 2(j - i) - 2(n - m)

(53)

С учетом того факта, что в данном случае j - i является целым числом > 0, получаем

(54)

Объединяя (51) и (54), получаем следующие ограничения на j - i для точек (i, j), лежащих на некотором пути из (0,0) в (m, n) в графе зависимости:

-p < j - i < n - m + p, где

(55)

Следствием из (55) является то, что для проверки выполнения неравенства d(x, y) < h можно ограничиться вычислением d_i,j, лежащих на ленте между диагоналями -p и n-m+p, где p = [(h/w_min - (n - m))/2].

Алгоритм для реализации этого порогового критерия приведен на рисунке (19). Проверка возвращает отрицательное значение, если критерий не выполнился, и значение d_m,n, если оно меньше или равно пороговому. Критерий не выполняется в тривиальном случае, задаваемом выражением (52), так как расстояние должно быть по меньшей мере равно разности длин строк умножить на минимальную стоимость вставок и удалений. В не тривиальном случае вычисляются значения d_i,j на диагональной ленте, задаваемой (55). По завершении этих вычислений окончательное значение d_m,n сравнивается с пороговым.

distance_test(h)

   if h/wmin < N - M

      - ТРИВИАЛЬНЫЙ СЛУЧАЙ

      RETURN(-1)

   else

      - ИНИЦИАЛИЗАЦИЯ

      P = INT((H/Wmin - (n - m))/2)

      d0,0 = 0

      for j = 1 to min{n, n - m + p}

         d0,j = d0,j-1 + w(, yj)

      - вычислить dm,n

      for i = 1 to m

         for j = max{0, i - p} to min{n, i + n - m + p}

            if j = 0

               di,0 = di-1,0 + w(xi,)

            else

               di,j = min{di-1,j + w(xi,*),

                         di,j-1 + w(,yj), di-1,j-1 + w(xi,yj)}

      if dm,n > h

         return(dm,n)

      else

         return(-1)

h = (n - m + 1)wmin

while (d = distance_test(h)) < 0

   H = 2H

Для каждой из m+1 строк количество вычисляемых элементов матрицы не превосходит n-m+2p+1, что является O(h), как показано ниже.

p = [(h/wmin - (n - m))/2] 2p < h/wmin - (n - m) n - m + 2p + 1 < 1 + h/wmin= O(h)

(56)

Таким образом, пороговый критерий выполняется за время O(hm), и требует O(hm) памяти, если сохраняются только значения на диагональной ленте. Обратите внимание, что если требуется только значение расстояния между строками, то требования к памяти можно сократить до O(h) ячеек, так как для вычисления текущей строки требуются только значения предыдущей строки (алгоритм Хиршберга с линейным временем).

Чтобы найти фактическое расстояние между двумя строками, можно вызывать процедуру порогового критерия с последовательно возрастающими значениями h, пока критерий не выполнится. Алгоритм для этого приведен на рисунке 20. В начале порогу присваивается минимальное из возможных значений расстояния плюс w_min, которое затем последовательно удваивается. По завершении d равняется расстоянию между двумя строками.

Обозначим начальное пороговое значение h₀, следующее, равное 2h₀, h₁, следующее, равное 2²h₀, h₂, и т.д. Таким образом, r-е значение h_r равно 2^rh₀. Если для определения d(x, y) требуется r вызовов distance_test, то всего требуется время , то есть O(m(2hr - 1)), что равно O(mh_r). Однако, так как d > h_r/2, общая временная сложность равна O(dm). Фактическая последовательность редактирования может быть вычислена по завершению как в методе Вагнера-Фишера.

Укконен рассмотрел также частный случай, когда цены всех операций редактирования равны (то есть вычисление расстояния Левенштейна), для которого можно сократить требования к памяти и применить более эффективный, со временем O(dm), прямой метод вычисления d(x, y).

Вверх по странице, к оглавлению и навигации.