yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->5.6. АТД с операторами MERGE и SPLIT

Алгоритмы и структуры данных

5.6. АТД с операторами MERGE и SPLIT

Пусть S — множество, элементы которого упорядочены посредством отношения "<". Оператор разбиения SPLIT(S, S1( 82, х) разделяет множество S на два множества: Si = {а | а є S и а < х} и S2 = {a|ae S и а > х}. Множество S после разбиения не определено (если не оговорено, что оно принимает значение S1 или S2). Можно привести много различных ситуаций, когда необходимо разделить множество путем сравнения всех его элементов с одним заданным значением. Одна из таких ситуаций рассмотрена ниже.

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

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

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

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

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

Алгоритм, использующий команду diff для поиска НОП, можно применить в эффективной реализации множеств с операторами MERGE и SPLIT. В этом случае время выполнения алгоритма поиска НОП составит О(р logn), где п — максимальное число строк в файле, а р — число пар позиций с совпадающими строками, когда одна позиция из одного файла, а другая из другого. Например, для последовательностей из рис. 5.14 число р равно 12. Две единицы в каждой последовательности образуют 4 пары, три двойки в верхней последовательности и две в нижней дадут 6 пар, а тройки и четверки — еще 2 пары. В самом худшем случае р может иметь порядок n2, тогда алгоритм поиска НОП будет выполняться за время О(n2 logra). На практике р обычно близко к п, поэтому можно ожидать время выполнения порядка О(п logn).

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

Имея построенные множества PLACES(a) для каждого элемента а последовательности А, можно приступать непосредственно к нахождению НОП. Упрощая изложение материала, мы покажем только, как определить длину НОП, оставляя в качестве упражнения построение конкретных НОП. Алгоритм будет по очереди просматривать все bj, где j пробегает значения 1, 2, ..., т. После обработки очередного b; мы должны для каждого і от О до n знать длину НОП для последовательностей а1, ..., ai и b1, ..., bj.

Значения позиций группируются в множества St (k = О, 1, ..., n), состоящие из всех целых чисел (позиций) і таких, что существует НОП длины k для последовательностей a1, .... aj и b1, ..., bj. Отметим, St всегда являются множествами последовательных целых чисел и для любого k числа в Sk+1 больше, чем в Sk.

Пример 5.8. Вернемся к последовательностям рис. 5.14, и пусть у = 5. Очевидно, что множество sq состоит только из 0 (т.е. никакой элемент из первой последовательности не сравнивается с первыми пятью элементами (24312) из второй последовательности, поэтому НОП имеет длину 0). Если мы возьмем первый элемент из первой последовательности и сравним его с пятью элементами 24312 второй последовательности, то получим НОП длины 1. Если возьмем первые два элемента 12 из первой последовательности, то получим НОП длины 2. Но первые три элемента 123 при сравнении с элементами 24312 все равно дадут НОП длины 2. Продолжая этот процесс, получим S0 = {0}, $! = {!}, S2 = {2, 3}, S3 = {4, 5, 6} и S4 = {7}.

Предположим, что мы имеем множества Sk для (j - 1)-й позиции второй последовательности и теперь хотим изменить их для позиции j. Рассмотрим множество PLACES(bj). Для каждого r из PLACES(bj) определим, можно ли построить какую-либо НОП путем добавления совпадения аr с bj к ранее построенным НОП для п1, ..., ar-1 и b1, ..., bj. Если оба числа r - 1 и r входят в множество Sk, тогда все числа s, s ≥ r из Sk, перейдут в множество Sk+1 при добавлении bj. Это следует из того, что если есть k совпадений между подпоследовательностями а1 ..., аr-1 и b1 ..., bj-1, то добавление совпадения между аr и bj увеличит общее число совпадений на единицу. Таким образом, для преобразования множеств Sk и Sk+1 следует выполнить такие действия.

1.    Применить оператор FIND(r) для нахождения множества Sk.

2.    Если FIND(r - 1) ≠ Sk, тогда при добавлении совпадения bj и аr новые НОП не образуют, множества Sk и Sk+1 не изменяются, и надо пропустить следующие шаги.

3.   Если FIND(r - 1) = Sk, то применяется оператор SPLIT(Sk, Sk, S'k, r) для отделения от множества Sk тех чисел, которые больше или равны r.

4.   Для перемещения "отделенных" элементов в множество Sk+1 применяется оператор MERGE(S'k, Sk+1, Sk+1).

Следует первыми рассмотреть большие позиции из множества PLACES(bj). Чтобы увидеть, почему надо это делать, предположим, например, что множество PLACES(bj) содержит числа 7 и 9 и до ввода в рассмотрение элемента bj имеем S3 = {6„ 7, 8, 9} и S4={10, 11}.

Если мы сначала рассмотрим позицию 7 перед позицией 9, то множество S3 надо будет разбить на множества S3 = {6} и S'3 = {7, 8, 9}, затем преобразовать множество S4: S4 = (7, 8, 9, 10, 11}. Если затем рассмотреть позицию 9, то множество S4 разбиваем на множества S4 = {7, 8} и S'4 = {9, 10, 11}, последнее множество сливается с множеством S5. Таким образом, позиция 9 переместилась из множества S3 в множество S5 только при рассмотрении одного элемента из второй последовательности, что невозможно. Это означает, что в созданную НОП длины 5 включены совпадения bj и с a7, и с а9 одновременно, что является безусловной ошибкой.

В листинге 5.15 показан эскиз алгоритма построения множеств Sk при прохождении по элементам второй последовательности. Для нахождения длины НОП после выполнения этого алгоритма надо выполнить FIND(n).

 

Листинг 5.15. Программа нахождения НОП

procedure НОП;

begin

(1)    инициализация So= {О, 1, ..., n} и Sk= 0 для k от 1 до n;

(2)    for j:= 1 to n do { вычисление всех Sk для позиции j }

(3)        for наибольшее число r є PLACES (bj) do begin

(4)            k:= FIND(r);

(5)            if k:= FIND(r-l) then begin

(6)                 SPLIT (Sk, Sk, S'k, r);

(7)                 MERGE (S'k, S'k+1, S'k+1)

end

end

end; { НОП }

Анализ времени выполнения алгоритма нахождения НОП

Как упоминалось ранее, описываемый алгоритм целесообразно применять тогда, когда между элементами рассматриваемых последовательностей не очень много совпадений. Число совпадений можно подсчитать по формуле |PLACES(bj) |, где |PLACES(bj)| обозначает число элементов в множестве PLACES(bj). Другими словами, р — это сумма по всем bt количества позиций в первой последовательности, совпадающих c--bj. Напомним, что при сравнении файлов мы ожидали, что р имеет такой порядок, как длины сравниваемых последовательностей (файлов) тип.

Оказывается, что 2-3 деревья*— подходящая структура для множеств Sk. Мы можем инициализировать эти множества (строка (1) в листинге 5.15) за О(п) шагов. Для реализации функции FIND необходим массив, осуществляющий отображение из множества позиций в множество листьев дерева, а также указатели на родителей узлов в 2-3 дереве. Имя множества, т.е. k для множества Sk, можно хранить в корне дерева. В этом случае оператор FIND можно выполнить за время O(logn), следуя за указателями от листа дерева к его корню. Поэтому все выполнения строк (4) и (5) в листинге 5.15 в совокупности требуют времени порядка О(р logn.).

Выполняемый в строке (5) оператор MERGE обладает тем свойством, что каждый элемент в множестве S'k меньше, чем любой элемент в множестве Sk+1, и мы можем воспользоваться этим, применяя 2-3 деревьев для реализации данного оператора1. Вначале оператор MERGE помещает 2-3 дерево множества S'k слева от дерева множества k+1. Если оба дерева имеют одинаковую высоту, то создается новый корень, сыновьями которого являются корни этих MERGE деревьев. Если дерево множества S'k короче дерева множества Sk+1, то корень дерева множества S'k становится самым левым сыном самого левого узла.на соответствующем уровне дерева множества Sk+1. Если после этого узел будет иметь четырех сыновей, то дерево модифицируется точно так же, как и при выполнении процедуры INSERT из листинга 5.11. Пример подобного объединения деревьев показан на рис. 5.15. Аналогично, если дерево множества Sk+1короче дерева множества S'k, то корень дерева множества Sk+1 становится самым правым сыном самого правого узла на соответствующем уровне дерева множества S'k.

Оператор SPLIT, разбивающий множество по элементу r, осуществляет проход по дереву от листа, содержащего г, к корню дерева, дублируя по пути все внутренние узлы, расположенные на пути, и отдавая эти копии узлов двум результирующим деревьям. Узлы, не имеющие сыновей, исключаются из дерева, а узлы, имеющие по одному сыну, удаляются, вставляя своего сына на соответствующий уровень дерева.

Пример 5.9. Предположим, необходимо разбить дерево, изображенное на рис. 5.15,6, по узлу 9. Два дерева с дубликатами узлов, расположенных на пути от листа 9 к корню, показаны на рис. 5.16,а. На дереве слева родитель листа 8 имеет только одного сына, поэтому лист 8 становится сыном родителя узлов 6 и 7. Этот родитель теперь имеет трех сыновей, поэтому все в порядке. Если бы он имел четырех сыновей, то потребовалось бы создать новый узел и вставить его в дерево. Теперь надо удалить узлы без сыновей (старый родитель листа 8) и цепочку из узлов с одним сыном, ведущую к корню дерева. После этих удалений родитель листьев 6, 7 и 8 становится корнем дерева, как показано на рис. 5.16,6. Аналогично, на правом дереве рис. 5.16,а лист 9 становится левым братом листьев 10 и 11, лишние узлы удаляются, в результате получаем дерево, показанное на рис. 5.16,6.

Если операция разбиения деревьев и последующая их реорганизация происходят так, как описано выше, то можно показать, что в большинстве случаев для выполнения оператора SPLIT потребуется не более O(logn) шагов. Таким образом, общее время выполнения строк (6) и (7) в листинге 5.15 требует О(р logra) шагов. Еще необходимо учесть время, затрачиваемое перед выполнением процедуры НОП на вычисление и сортировку множеств PLACES(a) для всех элементов а. Как уже упоминалось, если элементы а — "большие" объекты (например, текстовые строки), то это время может быть больше времени, необходимого на реализацию любой части описываемого алгоритма.

Как будет показано в главе 8, если манипулирование и сравнение элементов можно "уложить" в единичные "шаги", то на сортировку первой последовательности a1a2...ап потребуется порядка О(п logn) таких шагов, после чего PLACES(a) может быть считан из списка за время О(n). В итоге получаем, что длину НОП можно подсчитать за время порядка О(тах(n, р) logn), которое (поскольку обычно р ≥ п) можно принять как О(р logn).

 

 

51