дерева. Заметим, что позиционное дерево для 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, входящий также в

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

Рис. 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.