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

Хант-Шиманский.

Метод выделения lcs для двух входных строк x и y Ханта и Шиманского (Hunt, Szymanski) эквивалентен нахождению максимального монотонно возрастающего пути в графе, состоящего из точек (i, j), таких, что x_i = y_j. Мы опишем этот метод, а затем проиллюстрируем его примером.

Для удобства будем считать, что длины входных строк равны, то есть |x| = |y| = n. Алгоритм легко изменить так, чтобы он подходил и для строк разной длины. Количество упорядоченных пар позиций совпадающих символов x и y, то есть мощность множества {(i,j) : x_i = y_j}, обозначим r.

Ключевым в методе является массив значений k_i,l, определяемых соотношением

где l_i,j определены в (14).

Таким образом, значение k_i,l дает длину самого короткого префикса y, имеющего общую с префиксом x длины i общую подпоследовательность длины s. Вот пример: если x = preterit и y = zeitgeist, то k_5,1 = 2, k_5,2 = 4, k_5,3 = 6, а k_5,4 и k_5,5 не определены.

Из того, что k_i,s по определению является минимальным значением, следует, что последний символ подпоследовательности длины s, общей для префиксов x(1, i) и y(1, k_i,j) равен . Итак, длина lcs для x(1, i) и y(1, k_i,s-1) равна s - 1. Следовательно, k_i,s-1 < k_i,s-1, то есть k_i,s-1 < k_i,s. Отсюда видно, что значения k_i,s в каждой строке массива должны монотонно возрастать.

Значения k можно итеративно вычислять по предыдущим значениям в массиве. В частности, значение k_i+1,s может быть выведено по k_i,s-1 и k_i,s. Перед тем, как продемонстрировать, как это делается, исследуем диапазон значений, в который должно попасть k_i+1,s.

Общая для x(1, i) и y(1, k_i,s) подпоследовательность длины s будет общей и для x(1, i+1) и y(1, k_i,s). Таким образом,

По определению, x(1, i+1) и y(1, k_i+1,s) имеют lcs длины s. Поэтому lcs, построенная для префиксов на один символ более коротких, а именно x(1,i) и y(1, k_i+1,s-1), будет короче ее не больше, чем на один символ. Таким образом,

Комбинируя (31) и (32), получаем следующие границы для k_i+1,s

Правило вычисления k_i+1,s по k_i,s-1 и k_i,s выглядит так:

(34)

Правильность этого выражения можно доказать следующим образом. Сначала рассмотрим случай, когда подходящих j не существует. Так как k_i+1,s является минимальным значением, последняя компонента любой общей для x(1, i+1) и y(1, k_i+1,s) подпоследовательности длины s должна быть равна . Из того, что k_i+1,s должно лежать внутри задаваемых (33) границ, следует, что , иначе требуемым значением j было бы k_i+1,s. Отсюда, в свою очередь, следует, что эта подпоследовательность длины s является общей для x(1,i) и y(1,k_i+1,s), откуда k_i,s < k_i+1,s. Комбинируя это с (33) получаем, что когда подходящих j не существует, k_i+1,s = k_i,s.

Теперь рассмотрим случай, когда существует j, при котором x_i+1 = y_j и k_i,s-1 < j < k_i,s. Префиксы x(1, i+1) и y(1, j) будут иметь общую подпоследовательность длины s, равную подпоследовательности длины s-1, общей для x(1,i) и y(1, k_i,s-1) с присоединенным на конце символом x_i+1 (так как x_i+1 = y_j). Таким образом, k_i+1,s < j. Теперь осталось узнать, достигнуто ли желаемое равенство, или k_i+1,s на самом деле меньше нашего значения j. Предположив последнее, и придя к противоречию, мы тем самым докажем, что выполняется первое. Итак, предположим, что k_i+1,s < j. И снова, последним символом общей для x(1, i+1) и y(1, k_i+1,s) последовательности длины s должен быть y_k+1,s. Так как k_i+1,j и j должны лежать в одном интервале (из (33) и (34)), мы знаем, что y_k+1,s =/=x_i+1, поскольку j является минимальным значением в разрешенном диапазоне, при котором y_j = x_i+1, а мы предполагаем, что k_i+1,s < j. Отсюда следует, что x(1,i) и y(1, k_i+1,s) также имеют общую подпоследовательность длины s, поэтому k_i,s < k_i+1,s. Вместе с (33) это означает, что k_i,s = k_i+1,s. Мы предположили, что k_i+1,s < j. Таким образом, из (34), k_i+1,s < k_i,s, что противоречит предыдущему результату. Это показывает, что на самом деле j равно требуемому k_i+1,s.

Алгоритм для определения |lcs(x,y)| с помощью k_i,s дан на рисунке 15. Вектор kk используется как i-я строка массива k. Таким образом, в начале i-й итерации kk_s = k_i-1,s для 0 < s < n, а по завершению итерации, kk_s = k_i,s при 0 < s < n. Обратите внимание, что kk₀ присваивается значение 0, а остальным kk – значение n+1, обозначая неопределенные значения k_i,s. Для вычислений требуется только одна строка, так как значения столбцом ниже остаются неизменными или уменьшаются, а значения вдоль строки остаются монотонно возрастающими.

- инициализация

kk0 = 0

for s = 1 to n

   kks = n + 1

- вычисление |lcs(x,y)|

for i = 1 to n

   for j = n downto 1

     if xi = yi

         найти s, для которого kks-1 < J < kks

         kks = j

print max s такое, что kks =/=n + 1

Важно, что в цикле по j идет уменьшение индекса с n до 1. Рассмотрим случай, когда x_i совпадает с несколькими символами в y, скажем, , , ... ,, такими, что k_i-1,s-1 < j₁ < j₂ < ... <j_p < k_i-1,s. Из (34) можно видеть, что правильным значением k_i,s является j₁. В процессе итераций, с уменьшением индекса j, k_i,s будут присваиваться все меньшие значения j_p, j_p-1, …, j₁, пока в конце не будет присвоено требуемое значение. Если, итерации по j проводить в противоположном направлении, то k_i,s сначала будет присвоено правильное значение, однако затем k_i,s+1 будет установлено равным j₂, k_i,s+2 равным j₃, и так до k_i,s+p-1, что правильным не является.

В конце процедуры значение |lcs(x,y)| задается максимальным s, для которого определено k_n,s. Так как значения kk монотонно возрастают, операция ‘найти’ может быть реализована за время O(log n) путем бинарного поиска. Из того, что инструкция if выполняется ровно n², следует, что алгоритм выполняется за время O(n² log n) в худшем случае. Заметим, что в случае строк разной длины граница для инициализации kk и внешнего цикла i будет равна m, а не n, где m < n. Ниже приведены результаты процедуры, где показаны значения k_i,s для x = preterit и y = zeitgeist. Из последней строки можно видеть, что |lcs(preterit, zeitgeist)| = 5.

Исчерпывающий поиск совпадающих символов в приведенном выше алгоритме довольно неэффективен, и его можно избежать, предварительно обработав строки, чтобы получить предварительную запись позиций, в которых они совпадают. Таким образом, можно построить массив указателей matchlist на связанные списки, в котором matchlist[i] дает связанный список позиций j, в которых x_i = y_j, идущих в порядке убывания. Для повторяющихся экземпляров символа в x можно использовать один и тот же список. Например, списки для x = preterit и y = zeitgeist будут следующими.

matchlist[1] = ()

matchlist[2] = ()

matchlist[3] = (6, 2)

matchlist[4] = (9, 4)

matchlist[5] = matchlist[3]

matchlist[6] = ()

matchlist[7] = (7, 3)

matchlist[8] = matchlist[4]

Окончательный алгоритм, включающий это улучшение, а также извлекающий lcs двух строк, представлен на рисунке 16. lcs воссоздается с помощью средства поиска с возвратами, используемого при вычислении значений kk. Когда определяется kk_j, link_s устанавливается указывающим на оглавление списка пар (i, j), определяющий общую подпоследовательность длины s. Это реализуется процедурой newnode, создающей узел, содержащий текущую пару (i, j) с указателем на предыдущий узел в списке и возвращающей указатель на только что созданный узел.

создать списки с использованием указателей

for i = 1 to n

   matchlist[i] = (j1, j2, . . . , jp) такие, что

                    j1 > j2 > … >jp и  для 1 < q < p

- инициализация

kk0 = 0

for s = 1 to n

   kkl = n + 1

link0 = null

- вычисление последовательных значений kk

for i = 1 to n

   for j in matchlist[i]

      найти s такое, что kks-1 < J < kks

      if j < KKs

         kks = j

         links = newnode(i, j, links-1)

- выделение lcs в обратном порядке

s = max s такое, что kks =/=n + 1

pointer = links

while pointer =/=null

   print (i,j) пара указана с помощью pointer

   продвинуть pointer

Предварительную обработку можно реализовать, сортируя символы каждой строки, записывая их исходные позиции, и сливая затем отсортированные строки для создания списков matchlist. С помощью алгоритма пирамидальной сортировки (heapsort) эту фазу можно выполнить за время O(n log n) с использованием O(n) памяти. Стадия инициализации занимает время O(n). Во время вычисления значений kk внутренний цикл выполняется r раз. Для каждой итерации выполняется бинарный поиск и несколько других операций с фиксированным временем. Таким образом, эта стадия занимает время O(r+r * log n) и включает создание r новых узлов. Наконец, фактическое выделение lcs занимает время O(|lcs(x,y)|), которое, разумеется, равно O(n). Таким образом, общие затраты времени и памяти у алгоритмы равны, соответственно, O((r+n) * log n) и O(r+n). И снова, более общий случай строк неравной длины легко реализуется установкой границ для инициализации kk и циклов i равными m вместо n.

В примере вычисления lcs(preterit, zeitgeist) описанная выше процедура выдает следующий список пар (i, j) для lcs (в обратном порядке):

(8, 9), (7, 7), (5, 6), (4, 4), (3, 2).

Это проиллюстрировано ниже, где узлы указывают точки (i, j), такие что x_i = x_j. lcs формируется символами в соответствии с заполненными узлами, а именно eteit, и, таким образом, эквивалентна максимальному монотонно возрастающему пути в графе.

	j	1	2	3	4	5	6	7	8	9
i		z	e	i	t	g	e	i	s	t
1	p
2	r
3	e
4	t
5	e
6	r
7	i
8	t

Апостолико и Гиерра [Apostolico, Guerra, 1987] разработали версию алгоритма Ханта-Шиманского, в которой удалось избежать снижения эффективности последнего до уровня ниже квадратичной в худшем случае. Вариант Апостолико и Гиерра имеет временную сложность O(m * log n + t * log(2mn/t)), что в худшем случае равно O(mn). Здесь t < r равняется числу доминантных совпадений между строками. k-доминантное совпадение является упорядоченной парой (i, j), такой, что x_i = y_j, l_i,j = k, и это первое появление такой точки в подматрице l_{(1,...,i),(1,...,j)} (l_i,j определяется в (14)). Сопоставление (i, j), таким образом, является доминантным, если вхождение в подходящей строке префиксов каждой lcs(x(1,i),y(1,j)) заканчивается символами x_i и y_j. Вариант Апостолико и Гиерра имеет эффективные средства нахождения доминантных сопоставлений и включает структуры данных, называемые характеристическими деревьями, для представления различных списков, требуемых алгоритмом.

Верхнюю границу (Джекобсон и Во [Jacobson, Vo, 1992]) для общего числа доминантных совпадений t между двумя строками получают следующим образом. k-доминантные совпадения можно отсортировать в порядке возрастания i, чтобы получить , где t_k есть число k-доминантных совпадений, и . Так как индексы i и j монотонно убывают и возрастают, соответственно, мы имеем следующие неравенства, где i < p < t_k:

(35)

Расстояние редактирования между префиксами x(1, i) и y(1, j) и длина их lcs связаны между собой следующим соотношением:

(36)

Так как сопоставление (i₁, j₁) является k-доминантным, мы имеем i₁ > k, а также, раз является k-доминантным, . Объединяя это с (36), получаем:

(37)

Пусть k'обозначает число, при котором имеется больше всего k-доминантных совпадений. lcs(x,y), построенная только по доминантным совпадениям, должна содержать одно из этих k'-доминантных совпадений, скажем, (i_p, j_p). Расстояние между полными строками x и y не может быть меньше расстояния между префиксами x(1, i) и y(1, j), то есть:

(38)

Так как является максимальным числом доминантных совпадений, то есть > t_l при 1 < l < l_m,n, имеем:

Комбинируя это с неравенством (38), получаем окончательный результат для верхней границы общего числа доминантных совпадений:

Число доминантных совпадений может быть гораздо меньше общего числа совпадений, особенно когда расстояние между строками мало. Граница для t в худшем случае выводится следующим образом. Подставляя вместо d_m,n выражение (16), получаем следующее:

Для строк равной длины, эта граница достигает максимального значения, равного (2n+1)²/8, при длине lcs, равной (2n+1)/4. Вспомним, что максимальное число совпадений равно n². Таким образом, можно видеть, что общее число совпадений асимптотически превышает число доминантных совпадений вдвое.

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