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

Выход. Позиционное Ti и вспомогательное Ai деревья для Xi. Метод.

1. Находим лист с меткой i+l в Tj+i. (Это последний добавленный к Ti+i лист.)

2. Проходим по пути, ведущему из этого листа в корень дерева Ti+i, до такого узла Uy, что Ва [аг]=1. (Узел Uy соответствует такой самой длинной цепочке у, что аг/ - префикс цепочки Xi и подцепочка в ;С(+1, начинающаяся в некоторой позиции k, iKZkn.) Если такого узла нет, доходим до корня.

3. Полагаем В,[аг] = 1 для каждого узла v на пути, идущем из узла с меткой t+1 в сына узла Uy, расположенного на том же пути, или в корень, если такого Uy нет. (Каждый узел v на этом пути соответствует некоторому префиксу z цепочки Xt+i. Поэтому ясно, что utz - подцепочка цепочки UiXi+i.)

4. 1) Если узла Uy нет, переходим к случаю 1 (ниже).

2) Если узел Uy существует, но у него нет а-сына во вспомогательном дереве Ai+i, переходим к случаю 2.

3) Если у Uy есть щ-сын Vy во вспомогательном дереве, переходим к случаю 3. Узел Vy соответствует цепочке aty в позиционном дереве Ti+i.

Случай 1. Ui - символ, не входящий в ;С{+1. Тогда идентификатором позиции i и будет а. Чтобы построить Ti из Tj+i, выполняем следующее:

(а) образуем новый лист с меткой i, являющийся агсыном корня дерева Tj+j,

(б) полагаем Вг[а]=0 для всех ag/.

Чтобы построить Ai из Л1+1, делаем новый узел с меткой i Ui-сыном корня дерева Ai+i.

Случай 2. Ui входит в Xi+i, но в Ti+i есть лишь собственный префикс цепочки а,г/ (приписанный пути из корня дерева в некоторый лист Vl). Эта ситуация возникает тогда, когда нужно удлинять идентификатор некоторой позиции k, Kkn, чтобы он стал идентификатором позиции k в Ti. Допустим, что y=at+iai+i. . .Uj и узел Vl соответствует цепочке UiUi+i. . а для некоторого р</. Тогда ft - метка листа Vi и UtUi+i. . .а,-идентификатор позиции k в Ti+i (т. е. UiUi+i. . .а =аа+1. . .а,).

Чтобы построить 7 i из добавляем к узлу Vi поддерево с двумя новыми листьями, помеченными числами i и k. Пути, идущему из ViB k в этом добавленном поддереве, приписана цепочка ai+A+a- • . . .a„+i, а пути из Vi в i - цепочка a+iap.. . .Uj+i, при этом о«+А+2- • mp+ip+t- • -l- Таким образом, пути из корня дерева Ti в лист й будет приписана цепочка 00+,. . amdm+i, являющаяся новым идентификатором позиции k в Xi, а пути из корня в




Рис. 9.23. Части дерева Г,-, важные для случая 2. Штриховыми линиями изображены ребра дерева Л,-.

ЛИСТ i - цепочка ajflj+i. . Mjaj+u являющаяся идентификатором позиции i в Xi.

Точнее, для построения Ti из 7j+i выполняем следующее.

1) Двигаясь по пути в 7, идущему из Uy в корень, находим узел «1, являющийся для узла Uy первым предком с aj-сыном в Ai+i. Пусть - этот flj-cbiH. В Tt+i узел Wi - лист с меткой k для некоторого Kkn. Стираем у Vi метку k.

2) Пусть «1, «2. • . Uy - последовательность узлов на пути в Ti+i, идущем из щ в Uy. Предположим, что ребро из и,, в Ыу+] помечено символом с,,, lhKZq, а ребро из в и -

символом Сд, как показано на рис. 9.23 (ciCa-

.aj=a,+ia,.2. . .a„, где символы те же, что и выше).

3) В Ti образуем q новых узлов v, Va, . . .и,, Vy. Делаем Vf,+ Сд-сыном узла v,, для lh<.q. Делаем Vy с,-сыном узла v.

4) Пусть j=i+ глубина узла Uy и m=k-\- глубина узла Ыу. Добавляем к Ti два новых узла с метками i и k. Лист i делаем а;+1-сыном узла Vy, а лист k делаем а+-съшом узла Vy.



б) Для всех ag/ полагаем В„[а]=В„,[а] для каждого {v,, Va.....w,, Vy, k}.

6) Полагаем ВДа]=0 для всех а g /.

Чтобы построить At из выполняем следующее.

7) Делаем у, а-сыном узла Uy в Л.

8) Пусть и будет aj+i-сыном узла Uy в Tj+j. Новый лист с меткой i делаем а-сыном узла и в At.

9) Пусть и" будет а„+1-сыном узла Uy в Tt+i. Новый лист с меткой k делаем арсыном узла и" в Л,.

10) Делаем а;-сыном узла в Л; для 2hq.

Случай 3. Узел Uy имеет а(-сына Vy в At+i. В этом случае надо рассмотреть две ситуации.

(а) Vy - лист с меткой feBT+j. Такая ситуация возникает, когда Si(0=a<«i+i- -аЛч! и Si+i{k)=aa+i. . .а„, причем a+i... . . .a„=aiai+i. . .aj; это частный вид случая 2, когда Vi=Vy. Чтобы построить Ti из Ti+i, удаляем метку k из узла Vy и образуем для узла Vy a+i-сына с меткой i и а„+1-сына с меткой k. Детали этого построения те же, что и в случае 2 (без шагов 3, 7 и 10).

(б) Vy - внутренний узел дерева Такая ситуация возникает, когда Si=S,+i и {Si{i)}. Чтобы построить Tt из Ti+i, просто образуем для узла Vy ay+i-сьша (которого у него нет) и помечаем этот лист меткой i. Подробный алгоритм таков:

1 Пусть /=1+ глубина узла Uy.

2. Новый узел с меткой i делаем aj+i-сыном узла Vy в Tt. (Заметим, что у Vy не может быть a+i-сына в Tt+i в силу

максимальности у.)

3. Полагаем Bi[a]=0 для всех а1. Поскольку atyaj+i не является подцепочкой цепочки Xi+i, то, разумеется, aatyaj+i не является подцепочкой цепочки Xt ни для какого а.

4. Чтобы построить Л; из Лг+1, берем узел и, являющийся ау+1-сыном узла Uy в Tj+i. (В Tj+i узел и соответствует yaj+i.) Новый узел i делаем а-сыном узла и в At+i. (В Л,-узел i будет соответствовать цепочке aj+iyat.)

Связи между узлами, упомянутыми в случае 3(6), показаны на рис. 9.24.

Пример 9.22. Пусть а..anan+\=abbabb%, а Та и Л а -деревья с рис. 9.22. Алгоритмом 9.5 строим Ti и Л1 из Та и Л а. Здесь t = l и ау=а.

Прежде всего отыскиваем лист с меткой 2 и, поскольку Bi[d\=Q, полагаем Ва[а1=1 и поднимаемся в узел, обозначенный и на рис.





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 124 125 126 [127] 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.004