Главная Промышленная автоматика.

дерево, поэтому порядок, в котором применяется оператор FIND к элементам любого дерева при выполнении подряд л операторов FIND, несуществен. Но отметим, что существуют последовательности из операторов MERGE и FIND, которые требуют времени порядка П(п logn).



Рис. 5.13. Пример сжатия пути

Алгоритм, использующий как сжатие путей, так и слияние меньщих множеств в больщие, - асимптотически наиболее эффективный метод (из известных) реализации АТД MFSET. На практике л выполнений оператора поиска требует времени, не превыщающего 0(п а(п)), где а(л) - функция, которая при возрастании л растет значительно медленнее, чем logn. Мы определим функцию а(п) ниже, но анализ, который приводит к такой оценке, выходит за рамки этой книги.

Функция а(л)

Функция а(л) тесно связана с очень быстро растущей функцией А(х, у), известной как функция Аккермана. Эта функция рекуррентно определяется следующими соотношениями:

А(0, у) = 1 для любого у > О, А(1. 0) = 2,

Л(х, О) = X + 2 для любого х > 2,

Л(х, у) = Л(Л(х - 1, у), у - 1) для всех х, у > 1.

Фиксированное значение у определяет функцию одной переменной. Например, третье вышеприведенное соотношение для у = О определяет функцию "прибавить 2". Для у = 1 и X > 7 имеем ylfx, 1) = Л(Л(х - 1, 1), 0) = Л(х - 1. 1) -Ь 2 с начальным значением 7, 1) = А(А(0, 1), 0) = А(1, О) = 2. Отсюда следует, что Л(х, 1) = 2г для всех X > 1. Другими словами, Л(х, 1) - это "умножение на 2". Аналогично, для у = 2 п X > 1 получим Л(х, 2) = А{,А(х- 1, 2), 1) = 2Л(х - 1, 2) и А(1. 2) = А{А(0.2), 1) = Л(1, 1) = 2. Таким образом, Л(х, 2) = 2\ Подобным образом мокно показать, что

А(х, 3) = 2 ("этажерка" из х двоек). В свою очередь у1(х, 4) растет так быстро, что этот рост нельзя показать с помошью обычной математической записи.

Функцию Аккермана одной переменной можно таюке определить как А(х) - А(х, х). Тогда функция а(л) является псевдообратной к функции А(х). Точнее,



a(n) равна наименьшему х такому, что п <А(х). Например, Л<1) = 2, поэтому ос(1) = а(2) = 1. Аналогично, А(2) = 4, отсюда следует, что ot(3) = а(4) = 2. Далее, Л(3) = 8, поэтому а(5) = ... = а(8) = 3.

Может показаться, что ос(п) растет хоть и медленно, но все-таки заметно. Однако уже А{А) - это последовательное возведение числа 2 во вторую степень 65 536 раз (т.е. "этажерка" из 65 536 двоек). Поскольку log(A(4)) является "этажеркой" из 65 535 двоек, то мы не можем даже точно прочитать значение А(4) или определить, какова разрядность этого числа. Поэтому а{п) < 4 для всех "обозримых" целых и. И тем не менее ot(n), в принципе, может достигать значений 5, 6, 7, более того, а(п) невообразимо медленно, но все-таки стремится к бесконечности.

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

Пусть S - множество, элементы которого упорядочены посредством отношения "<". Оператор разбиения 8РЬП(8, Si, Sz, х) разделяет множество S на два множества: Si = {а I а е S и а < л} и S2 = {а \ а е S я а > х). Множество S после разбиения не определено (если не оговорено, что оно принимает значение Si или S2). Можно привести много различных ситуаций, когда необходимо разделить множество путем сравнения всех его элементов с одним заданным значением. Одна из таких ситуаций рассмотрена ниже.

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

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

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

1 2 3 2 4 1 2

/ \\\

2 4 3 1 2 1

Рис. 5.14. Наибольшая общая подпоследовательность

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

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



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

Перед началом описания алгоритма предположим, что есть две строки (последовательности) элементов у1 = aia2...a„ и 5 = Ьф-.-Ьщ Для которых ищется НОП. Первым шагом алгоритма будет составление для каждого элемента а списка позиций строки А, на которых стоит этот эдемент. Таким способом определяется множество PLACES(a) = { i \ а = щ }. Для вычисления множеств PLACES(a) можно создать отображение из множества элементов в заголовки списков позиций. При использовании хеш-таблиц можно вычислить множества PLACES(a) в среднем за 0(п) "шагов", где "шаг" - это действия, выполняемые при обработке одного элемента. Время, затрачиваемое на выполнение одного "шага", будет константой, если эдемент, например, является символом иди числом. Но если элементы в последовательностях А а В являются текстовыми строками, то время выполнения "шага" будет зависеть от средней длины текстовых строк.

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

Значения позиции группируются в мнолсества (к = О, 1, п), состоящие из всех целых чисел (позиций) i таких, что сушествует НОП длины к для последовательностей ai, ai и bi, bj. Отметим, всегда являются мнолсествами последовательных целых чисел и для любого к числа в S.i больше, чем в 5.

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

Предподолсим, что мы имеем мнолсества Sj для (j - 1)-й позиции второй последовательности и теперь хотим изменить их для позиции j. Рассмотрим мнолсество PLACES(6y). Для калсдого г из PLACES(6y) определим, молено ди построить какую-либо НОП путем добавления совпадения а,, с bj к ранее построенным НОП для ai Or-i и bi, bj. Если оба числа г - 1 и г входят в мнолсество Si, тогда все числа s, S > г из Sj перейдут в мнолсество Sjn при добавлении Ь,. Это следует из того, что если есть к совпадений мелсду подпоследовательностями ai, a,.i и hi, то добавление совпадения мелсду и Ь, увеличит общее число совпадений на единицу. Таким образом, для преобразования мнолсеств и Sj+i следует выполнить такие действия.

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

2. Если FIND(r - I) Ф Sj, тогда при добавлении совпадения и новые НОП не образуют, мнолсества S4 и S+i не изменяются, и надо пропустить следующие шаги.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 [54] 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002