31. Задача наибольшей общей подпоследовательности

Подпоследовательность последовательности х получается в результате удаления нескольких элементов (не обязательно соседних) из последовательности х.

Имея две последовательности х и у, наибольшая общая подпоследовательность (НОП) определяется как самая длинная последовательность, являющаяся подпоследовательностью как х, так и у.

Например, для последовательностей

НОП составляет подпоследовательность 2, 3, 2, 1.

В этом примере существуют и другие НОП, в частности 2, 3, 1, 2, но нет ни одной общей подпоследовательности длиной 5.

Существует команда UNIX diff, которая, сравнивая файлы строка за строкой, находит наибольшую общую подпоследовательность, при этом рассматривая каждую строку файла как отдельный элемент подпоследовательности (т.е. здесь целая строка является аналогом целых чисел из примера). После выполнения команды diff строки, не вошедшие в НОП, могут быть удалены, изменены или перемещены из одного файла в другой. Например, если оба файла являются версиями одной и той же программы, выполненными с разницей в несколько дней, то оператор diff, скорее всего, найдет расхождения в этих версиях. Существуют различные способы решения задачи НОП, которые требуют выполнения порядка О(n²) шагов для последовательностей длиной n. Команда diff использует дифференцированную стратегию, которая работает хорошо, если файлы не имеют слишком больших повторений в строках. Например, в программах обычно много повторяющихся строк "begin" и "end", но другие строки не должны повторяться также часто. Алгоритм, использующий команду diff для поиска НОП, можно применить в эффективной реализации множеств с операторами MERGE и SPLIT.

В этом случае время выполнения алгоритма поиска НОП составит О(р logn), где n - максимальное число строк в файле, а р - число пар позиций с совпадающими строками, когда одна позиция из одного файла, а другая из другого. Например, для последовательностей из примера слайда 116 число р равно 12. Две единицы в каждой последовательности образуют 4 пары, три двойки в верхней последовательности и две в нижней дадут 6 пар, а тройки и четверки - еще 2 пары. В самом худшем случае р может иметь порядок n², тогда алгоритм поиска НОП будет выполняться за время О(n²logn). На практике р обычно близко к n, поэтому можно ожидать время выполнения порядка О(nlogn). Перед началом описания алгоритма предположим, что есть две строки (последовательности) элементов А=a₁a₂...a_n и В=b₁b₂...b_m, для которых ищется НОП.

Первым шагом алгоритма будет составление для каждого элемента а списка позиций строки A, на которых стоит этот элемент. Таким способом определяется множество PLACES(a) = { i | a=a_i }. Для вычисления множеств PLACES(a) можно создать отображение из множества элементов в заголовки списков позиций. При использовании хеш-таблиц можно вычислить множества PLACES(a) в среднем за О(n) "шагов", где "шаг" - это действия, выполняемые при обработке одного элемента. Время, затрачиваемое на выполнение одного "шага", будет константой, если элемент, например, является символом или числом. Но если элементы в последовательностях А и В являются текстовыми строками, то время выполнения "шага" будет зависеть от средней длины текстовых строк.Имея построенные множества PLACES(a) для каждого элемента а последовательности А, можно приступать к нахождению НОП. Упрощая изложение материала, мы покажем только, как определить длину НОП.

Алгоритм будет по очереди просматривать все b_j, где j=1, 2, ..., m. После обработки очередного b_j мы должны для каждого i от 0 до n знать длину НОП для последовательностей a₁, ..., a_i и b₁,..., b_j. Значения позиций группируются в множества S_k (k=0, 1, ..., n), состоящие из всех целых чисел (позиций) i таких, что существует НОП длины k для последовательностей a₁, ..., a_i и b₁,..., b_j. Отметим, S_k всегда являются множествами последовательных целых чисел и для любого k числа в S_k+1 больше, чем в S_k.