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

дерева. Заметим, что позиционное дерево для ai. . .a„a„+i может содержать 0{п) узлов. Например, позиционное дерево для a"b"a"b"$) содержит п+6п+2 узлов, в чем легко убедиться самим. Но при разумных предположениях о том, что такое "случайная" цепочка (например, символы выбираются из алфавита с равной вероятностью и независимо), можно показать, что "среднее" позиционное дерево для цепочки длины п содержит 0{п) узлов. Мы не будем показывать это здесь. Отметим лишь, что существует алгоритм сложности 0{п) в худшем случае, который строит компактную форму позиционного дерева прямо по данной цепочке. Работы, обсуждающие этот алгоритм, указаны в замечаниях по литературе.

Рассмотрим различия между множествами Sj и Sj+i идентификаторов для Xi и Xt+i соответственно, поскольку в алгоритме, описываемом ниже. Si строится из Sj+i. Одно очевидное различие состоит в том, что Si содержит идентификатор Si{i) первой позиции в Xi. Из-за того, что Sj содержит эту дополнительную цепочку, может оказаться, что идентификатор некоторой позиции k, содержащийся в Sj+i, не является идентификатором позиции k в Si. Это происходит тогда и только тогда, когда идентификатор Si+i(k) позиции k в Sj+i служит префиксом для s,-(i)- В этой ситуации надо удлинить цепочку Si+i{k), чтобы сделать из нее Si(k), т. е. идентификатор позиции k в Sj. Два идентификатора из Si+i удлинять не придется. В самом деле, если бы надо было удлинять цепочки S(+i(i) и St+iikt), то они обе были бы префиксами цепочки Si{i) и, значит, одна из них была бы префиксом другой вопреки лемме 9.3(6).

Пример 9.20. Пусть ai. . .anan+i=abbabb$. Идентификаторы для Xi=abb$, Хз=ЬаЬЬ$, Xi=bbabb$ и Xi=abbabb% приведены на рис. 9.21. Заметим, что Ss получается из S4 добавлением одной цепочки 8з{Ъ)=Ьа. С другой стороны, для построения S из Sg потребовалось два изменения. Мы добавили St{2)=bba к Sa и дописали $ к концу 8з(5), чтобы получить Sa(5)=ftft$. Чтобы построить Si, добавили Si,(\)=abba к Sa и дописали bb% к Sa(4), чтобы получить Si(4)= =abb%. □

Рассмотрим, что же нужно для построения позиционного дерева Ti, представляющего Sj, по позиционному дереву 7(+i, представляющему Sj+i. Пусть Tj+i построено. Надо добавить к Tj+i лист с меткой i, соответствующий цепочкеSi(i). Если для некоторого, t< <.kn, цепочка Si+i() служит префиксом цепочки Si{i), то надо также удлинить путь в Tj+i, идущий из корня в лист с меткой k, чтобы новый лист с меткой k в Ti соответствовал цепочке Si{k). Таким образом, ключом к эффективному построению по Tj+i позиционного дерева Г; для Xt является умение быстро находить такую цепочку у, что flji/ - самый длинный префикс цепочки Xi, входящий также в

) а" обозначает л-кратную конкатенацию символа а.



Позиция

S, (р)

Ss(P)

h iP)

а66$

abba

Рис. 9.21. Идентификаторы некоторых суффиксов цепочки abbabb%.

Xi+u И, кроме того, умение узнавать, служит ли аху префиксом идентификатора из Ti+i.

Такое построение требует добавления к позиционному дереву трех новых структур. Первая из них - двоичный вектор (массив), который приписывается каждому узлу позиционного дерева Ti. Вектор, приписываемый узлу v, будет обозначаться В,. Для каждого символа из / в этом векторе будет своя компонента. Если v - узел в Ти соответствующий цепочке г/, и а g /, то В,[а]=1, если ау - подцепочка в Xi. В противном случае В,[а]=0.

Далее каждому узлу приписывается его глубина в позиционном дереве. Эту информацию легко корректировать по мере роста дерева, и впредь мы будем предполагать, не оговаривая это особо, что она вычисляется.

Последнее добавление к позиционному дереву - новая древовидная структура, расположенная на его узлах. Мы будем называть ее "вспомогательным деревом", но на самом деле это будет всего лишь другое множество ребер, соединяющих узлы нашего позиционного дерева.

Определение. Пусть Г< - позиционное дерево для ;сг=агаг+1. . . . . .а„$. Вспомогательным деревом для позиционного дерева Ti назовем (/и {$})-дерево Ai, обладающее следующими свойствами:

1) Ai имеет то же множество узлов, что и Ti,

2) узел W является а-сыном узла v в Ai, если ау - цепочка, соответствующая wBTi,Hy - цепочка, соответствующая w в . Таким образом, пути в At, идущему из корня в ш, приписана цепочка уа, а пути в Tf, идущему из корня в w, приписана цепочка ау.




© ©

Рис. 9.22. Позиционное (а) и вспомогательное (б) деревья для ЬЪаЬЬ%.

Пример 9.21. Позиционное и вспомогательное деревья для X2=bbabb$ изображены на рис. 9.22. (Числа на листьях указывают позиции относительно x=abbabb$.) Заметим, что листья вспомогательного дерева не обязательно являются листьями позиционного дерева, хотя множество узлов у обоих деревьев одно и то же. □

Из определения не видно, всегда ли у позиционного дерева есть вспомогательное; действительно, произвольное /-дерево может не иметь вспомогательного. В следующей теореме сформулированы условия, при которых /-дерево имеет вспомогательное дерево.

Теорема 9.11. Для того чтобы у данного I-дерева Т было вспомогательное дерево, необходимо и достаточно, чтобы Т обладало таким свойством: если в Т есть узел, соответствуюиий цепочке ах, где а1 и x£l*, тов нем есть также узел, соответствуюиий цепочке х.

Доказательство. Упражнение. □

Следствие. Всякое позиционное дерево имеет вспомогательное дерево.

Доказательство. Если ах - префикс идентификатора позиции I, то в силу леммы 9.3(a) х - префикс идентификатора позиции i+l. □

Теперь мы готовы описать алгоритм, который строит позиционное дерево Ti для Xi из позиционного дерева 7j+i для jCj+f.

Алгоритм 9.5. Построение 7, из

Вход. Цепочка а . Лпал-и позиционное Tj+i и вспомогательное i4j+i деревья для ;Cj+i=fl!j+i. . .a„a„+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 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