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

Метод динамического программирования Вагнера и Фишера.

В методе динамического программирования последовательно, по предыдущим значениям, вычисляются расстояния между все более и более длинными префиксами двух строк – до получения окончательного результата. Опишем этот процесс более подробно.

Пусть d_i,j есть расстояние между префиксами строк x и y, длины которых равны, соответственно, i и j, то есть

Цену преобразования символа a в символ b обозначим через w(a,b). Таким образом, w(a,b) – это цена замены одного символа на другой, когда a =/= b, w(a,) – цена удаления a, а w(, b) – цена вставки b. Заметим, что в случае, когда выполнены нижеследующие условия, d является расстоянием Левенштейна:

w(a,) = 1 w(, b) = 1 w(a, b) = 1, если a =/=b, w(a, b) = 0, если a=b

(10)

В процессе вычислений значения d_i,j записываются в массив (m+1) * (n+1), а вычисляются они с помощью следующего рекуррентного соотношения.

di,j = min{di-1,j + w(xi,), di,j-1 + w(, yj), di-1,j-1 + w(xi, yi)}

(11)

Оно выводится следующим образом. Если предположить, что известна цена преобразования x(1, i-1) в y(1, j), то цену преобразования x(1, i) в y(1,j) мы получим, добавив к ней цену удаления x_i. Аналогично, цену преобразования x(1, i) в y(1, j) можно получить, прибавив цену вставки y_j к цене преобразования x(1, i) в y(1, j-1). Наконец, зная цену преобразования x(1, i-1) в y(1, j-1), цену преобразования x(1, i) в y(1, j) мы получим, прибавив к ней цену замены x_i на y_j. Вспомним, что расстояние d_i,j является минимальной ценой преобразования x(1,j) в y(1,j), поэтому из трех указанных выше операций надо выбрать самую дешевую.

Перед тем, как начать вычислять d_i,j, надо установить граничные значения массива. Что касается первого столбца массива, то значение d_i,0 равно сумме цен удаления первых i символов x. Аналогично, значения d_0,j первой строки задаются суммой цен вставки первых j символов y. Итак, имеем следующее:

d0,0 = 0   для 1 < i < m   для 1 < j < n

(12)

Для расстояния Левенштейна d_i,0 = i и d_0,j = j. Ниже приведен массив, полученный при вычислении расстояния Левенштейна между строками preterit и zeitgeist. Из него видно, что расстояние между этими строками, то есть d_8,9, равно 6.

Алгоритм вычисления массива расстояний, разработанный Вагнером и Фишером (Wagner, Fisher), приведен на рисунке 10. Можно видеть, что стадия инициализации границ включает 1+m+n, а основной цикл повторяется mn раз. Таким образом, временная сложность этого алгоритма есть O(mn).

- инициализация границ массива

d0,0 = 0

for i = 1 to m

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

for j = 1 to n

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

- вычисление di,j

for i = 1 to m

for j = 1 to n

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

Рис. 10. Вычисление расстояния между строками по Вагнеру и Фишеру

Последовательность операций редактирования для преобразования x в y можно получить с помощью структуры, называемой след. След из x в y можно описать как соединение символов строки x с символами помещенной под ней строки y ребрами, причем каждый из символов соприкасается не больше чем с одним ребром, и никакие два ребра не пересекаются. Представляя ребро из x_i в y_j как упорядоченной парой целых чисел (i, j), след из x в y можно формально определить как множество упорядоченных пар, удовлетворяющих следующим условиям:

Последовательность операций редактирования можно получить из следа следующим образом. Все не касающиеся ребер символы x надо удалить, а аналогичные символы y вставить. Для каждого ребра (i, j) в следе, x_i заменить на y_j, если x_i =/=y_j, если же x_i = y_j, то редактирование не требуется. Вернемся к предыдущему примеру: вот как выглядит след с наименьшей ценой от preterit к zeitgeist.

i       1 2 3 4 5 6 7 8

xi      p r e t e r i t

        |  /  |  \  |  \ 

yj      z e i t g e i s t

j       1 2 3 4 5 6 7 8 9

След наименьшей цены, и, таким образом, последовательность операций редактирования наименьшей цены, переводящую x в y, можно получить из заполненного массива расстояний. Алгоритм для выдачи упорядоченных пар следа вы найдете на рисунке 11. Процедура начинает работу с d_m,n, и идет обратно, пока оба индекса i и j больше 0. Надо определить, по которому из соседей было выведено d_i,j, и перейти к этой позиции в массиве. Если d_i,j выведено из d_i-1,j-1, то выходом будет упорядоченная пара (i,j), соответствующая ребру в следе, то есть замене или сопоставлению, в зависимости от того, равны x_i и y_j или нет. Если d_i,j выведено из d_i-1,j или d_i,j-1, ничего не выдается, так как удаление и вставка соответствуют символам, не соприкасающимся с ребрами. Так как при каждом проходе цикла уменьшается либо i, либо j, либо оба индекса, максимальное число итераций равно m+n. Таким образом, след наименьшей цены определяется за время O(m+n).

i = m

j = n

while(i > 0) and (j > 0)

   if di,j = di-1,j + w(xi,)

      i = i - 1

   else if di,j = di,j-1 + w(,yj)

      j = j - 1

   else

      print('(i,j)')

   i = i - 1

   j = j - 1

Для предыдущего примера данная процедура дает следующий след T (в порядке, обратном тому, в котором эти пары выдаются алгоритмом).

T = {(1,1), (3,2), (4,4), (5,6), (7,7), (8,9)}

Теперь совершенно очевидно, как получить lcs(x,y) по следу наименьшей цены из x в y. Компонентами lcs(x, y) являются символы x_i, или, что эквивалентно, символы y_j, такие, что (i, j)T и x_i = y_j. Таким образом, для нашего примера мы имеем:

lcs(x, y) = x₃x₄x₅x₇x₈ = y₂y₄y₆y₇y₉ = eteit

И наконец, следует упомянуть, что, как указывают Вагнер и Фишер, в некоторых приложениях, скажем, при проверке правописания, может быть полезна весовая функция цены редактирования ab, w(a,b), зависящая от символов a и b. Например, при стандартной клавиатуре qwerty букву e легче перепутать с w, чем с p. Согласно этому критерию wast, например, будет ближе к east чем к past.

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