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

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

4. Для перемешения "отделенных" элементов в множество S+i применяется оператор MERGE(St, St+i, Sm).

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

S4 = {10, 11}.

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

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

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

procedure ноп; begin

(1) инициализация 5ц= (0,1, ...,п)и Sif= О для от 1 до п;

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

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

(4) ;::= FIND(r) ;

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

(6) SPLIT (sjt, S, S4, r);

(7) MERGE (s%, si+i, si.i) end

end; { НОП }

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

Как упоминалось ранее, описываемый алгоритм целесообразно применять тогда, когда мевду элементами рассматриваемых последовательностей не очень много совпадений. Число совпадений можно подсчитать по формуле р = j Р1АСЕ8(6у) , где

PLACES(6) обозначает число элементов в множестве PLACES(6y). Другими словами, р - это сумма по всем bj количества позиций в первой последовательности, совпа-даюших с bj. Напомним, что при сравнении файлов мы ожидали, что р имеет такой порядок, как длины сравниваемых последовательностей (файлов) т я п.

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

Выполняемый в строке (5) оператор MERGE обладает тем свойством, что каждый элемент в множестве S\ меньше, чем любой элемент в множестве Sj-ц, и мы можем



воспользоваться этим, применяя 2-3 деревьев для реализации данного оператора. Вначале оператор MERGE помещает 2-3 дерево множества S\ слева от дерева множества Sj+j. Если оба дерева имеют одинаковую высоту, то создается новый корень, сыновьями которого являются корни этих MERGE деревьев. Если дерево множества Sj короче дерева множества S+i, то корень дерева множества S\ становится самым левым сыном самого левого узла на соответствующем уровне дерева множества S+j. Если после этого узел будет иметь четырех сыновей, то дерево модифицируется точно также, как и при выполнении процедуры INSERT из листинга 5.11. Пример подобного объединения деревьев показан на рис. 5.15. Аналогично, если дерево множества Sim короче дерева множества Sk, то корень дерева множества S+i становится самым правым сыном самого правого узла на соответствующем уровне дерева множества S\.

А"

6 7


10 11 12 13 14


а. До реструктуризации

9 10 11 12 13 14 б. После реструктуризации

Рис. 5.15. Пример выполнения оператора MERGE

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

Пример 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 требует 0(plogn) щагов. Еще необходимо учесть время, затрачиваемое перед выполнением процедуры НОП на вычисление и сортировку множеств PLACES(o) для всех элементов а. Как уже упоминалось, если элементы а - "больщие" объекты (например, текстовые строки), то это время может быть больще времени, необходимого на реализацию любой части описываемо-

Строго говоря, мы должны дать другое название этому оператору, поскольку в данном случае он не объединяет непересекающиеся множества, а работает с деревьями, т.е. не соответствует названию MERGE.



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



6 7 8 9 10 11 12 13 14

а. Разделенныедеревья

6 7 8


9 10 11 12 13 14

б. Результат реструктуризации

Рис. 5.16. Пример выполнения оператора SPLIT

Упражнения

5.1. Нарисуйте все возможные деревья двоичного поиска для четырех элементов 1, 2, 3 и 4.

5.2. Вставьте целые числа 7, 2, 9, О, 5, 6, 8, 1 в пустое дерево двоичного поиска, повторив действия процедуры INSERT из листинга 5.2.

5.3. Покаките результат удаления числа 7, а затем числа 2 из дерева, полученного в упражнении 5.2.

*5.4. Если для удаления двух элементов из дерева двоичного поиска используется процедура из листинга 5.4, то зависит ли вид конечного дерева от порядка, в котором удаляются элементы?

5.5. Вы хотите, используя нагруженное дерево, отследить все 5-символьные последовательности, имеюшиеся в данной строке. Покажите нагруженное дерево, полученное для 14 последовательностей длины 5, извлеченных из строки ABCDABACDEBACADEBA.

*5.6. Для выполнения примера 5.5 надо в каждом листе, который представляет, например, строку abcde, хранить указатель на внутренний узел, представляю-ший (в данном случае) суффикс bcde. В этом случае, если, например, следую-





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.0019