ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->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).

 

 

82