1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 78

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 78)

Возможны несколько случаев. 1. Если )(р и о не лист, то ответом будет "нет". В этом случае Ь,Ь,...Ь~ — подцепочка цепочки х, а Ь,Ь,...Ь~Ь~„нет, 2. Если 1(р и о — лист с меткой 1, то Ь,Ь,...Ь~ совпадает с 1 символами цепочки х, начиная с позиции Е Тогда надо сравнить Ьг,,Ь~,...Ьр с а~~,а, ~~ь ..а;+г,. Если они не совпадают, то ответом будет "нет"; в противном случае "да", причем у входит в х, начиная с позиции 1. 3. Если )=р и о не лист, то ответом будет "да". В этом случае у— подцепочка с двумя или более вхождениями в х. Начальные позиции этих вхождений — метки листьев, принадлежащих поддереву узла о позиционного дерева.

П Пример 9.19. С помощью позиционного дерева можно найти самую длинную повторяющуюся подцепочку данной цепочки х= =а,а,...а„(два вхождения этой подцепочки могут перекрываться). Длиннейшая повторяющаяся подцепочка соответствует внутреннему узлу позиционного дерева с наибольшей глубиной. Такой узел можно обнаружить очевидным способом. Рассмотрим нахождение длиннейшей повторяющейся подцепочки в аЬЬаЬЬ. В позиционном дереве для аЬЬаЬЬ9 (рис. 9.20) есть один внутренний узел глубины 3 и ни одного внутреннего узла большей глубины. Поэтому соответствующая этому узлу цепочка аЬЬ вЂ” самая длинная повторяющаяся подцепочка в аЬЬаЬЬ.

Узлы с метками 1 и 4 указывают, где начинаются два вхождения цепочки аЬЬ. В нашем случае они не перекрываются. П Изучим подробно задачу построения позиционного дерева. В оставшейся части этой главы х$ будет цепочкой а,...а„а„~п где а„+, — единственный правый концевой маркер $. Через х„ 1(1( (и+1, будем обозначать суффикс аь ..а„а„~ь а через зф) — идентификатор позиции1в хо Все позиции нумеруются по исходной цепочке а,...а„а„ь Мы изложим алгоритм построения позиционного дерева для а,...а„~, за время, пропорциональное числу узлов окончательного 9.9. ПОЗИЦИОННЫЕ ДЕРЕВЬЯ дерева.

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

Работы, обсуждающие этот алгоритм, указаны в замечаниях по литературе. Рассмотрим различия между множествами 5, и 5,~т идентификаторов для х, и х~+т соответственно, поскольку в алгоритме, описываемом ниже, 59 строится нз 5;+,. Одно Очевидное различие состоит в том, что 5~ содержит идентификатор з~(1) первой позиции в хь Из-за того, что 5~ содержит эту дополнительную цепочку, может оказаться, что идентификатор некоторой позиции Ь, содержащийся в 5;+„ не является идентификатором позиции й в 5П Это происходит тогда и только тогда, когда идентификатор з,,(й) позиции й в 5;„служит префиксом для зк(1). В втой ситуации надо удлинить цепочку зс т(й), чтобы сделать из нее з;(й), т.

е. идентификатор псвиции Е в 5;. Два идентификатора из 5Р9т удлинять не придется. В самом деле, если бы надо было удлинять цепочки з,~т(йт) и з„,(й,), то они обе были бы префиксами цепочки з~(1) и, значит, одна из них была бы префиксом другой вопреки лемме 9.3(б). Пример 9.20. Пусть а,...а„а„+,— — аЬЬа66$. Идентификаторы для х,=аЬЬ~, хе=ЬаЬЬЯ, х,=ЬЬаЬЬ$ и хт=аЬЬа66$ приведены на рис.

9.21. Заметим, что 5, получается нз 5, добавлением одной цепочки з,(3)=Ьа. С другой стороны, для построения 5, из 5, потребо. валось два изменения. Мы добавили з,(2)=ЬЬа к 5, и дописали 3 к концу зз(б), чтобы получить з,(б)=ЬЬЭ. Чтобы построить 5„добавили з,(1)=аЬЬа к 5, и дописали 663 к з,(4), чтобы получить з,(4)= =а665. С) Рассмотрим, что же нужно для построения позиционного дерева Ть представляющего 5„по позиционному дереву Т„„представляющему 5~+9. Пусть Т,~, построено.

Надо добавить к ТР9, лист с меткой 1, соответствующий цепочке з,(с). Если для некоторого й, с (Ь(п, цепочка з,+т(й) служит префиксом цепочки з,(1), то надо также удлинить путь в Т, „идущий из корня в лист с меткой Ь, чтобы новый лист с меткой Ь в Т, соответствовал цепочке з1(й). Таким образом, ключом к эффективному построению по Т,е, позиционного дерева Т, для х; является умение быстро находитьтакую цепочку у, что апу — самый длинный префикс цепочки хн входящий также в т) а" обозначает п.кратную конкнтенанню символа а. гл. е. ллгоиитмы идвнтианкдции з*(р) з, (р) зе (Р) з (р) Позиция ЬЭ ЬЬ а Ьа Э Ьь ЬЬч аЬЬ3 Ьа ЬЬа аЬЬа 3 ЬЭ ЬЬЭ а Ьа ЬЬа 3 Ьф ЬЬ Рнс. 9.2К Идентификаторы некоторых суффиксов цепочки аЬЬаЬЬЯ.

Определение. Пусть Т, — позиционное дерево для к~=а;а ео .. ...а„Ч. Вспомогательным деревом для позиционного дерева Т, назовем (10($))-дерево А„обладающее следующими свойствами: 1) А~ имеет то же множество узлов, что и Т„ 2) узел св является а-сыном узла и в А„если ау — цепочка, соответствующая ш в Ть и у — цепочка, соответствующая и в То Таким образом, пути в А„идущему из корня в еи, приписана цепочка ула, а пути в Т» идущему из корня в гэ, приписана цепочка ау. х,еы и, кроме того, умение узнавать, служит ли ацу префиксом идентификатора из Т„,.

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

Далее каждому узлу приписывается его глубина в позиционном дереве. Эту информацию легко корректировать по мере роста дерева, н впредь мы будем предполагать, не оговаривая это особо, что она вычисляется. Последнее добавление к позиционному дереву — новая древовидная структура, расположенная на его узлах. Мы будем называть ее "вспомогательным деревом", но на самом деле это будет всего лишь другое множество ребер, соединяющих узлы нашего позиционного дерева. а.а. позиционнын д» навья а Рнс. 9.22. Поанпнонное (о) н вспомогательное (б) деревья для Ььаььф. Пример 9.21. Позиционное и вспомогательное деревья для ха=ЬЬаЬЬ9 изображены на рис. 9.22.

(Числа на листьях указывают позиции относительно х=аЬЬаЬЬ3.) Заметим, что листья вспомогательного дерева не обязательно явлшогся листьями позиционного дерева, хотя множество узлов у обоих деревьев одно и то же. П Из определения не видно, всегда ли у позиционного дерева есть вспомогательное; действительно, произвольное 7-дерево может не иметь вспомогательного. В следующей теореме сформулированы условия, при которых»-дерево имеет вспомогательное дерево.

Теорема 9.! 1. Для того чтобы у данного 1-дерева Т было вспомогательное дерево, необходимо и достаточно, чтобы Т обладало такал» свойством: если в Т есть узел, соответствующий цепочке ах, где а Е 1 и х Е Та, то в нем есть также узел, соответствующий цепочке х. Доказательство. Упражнение. П Следствие. Всякое позиционное дерево имеет вспомогательное дерево. До к аз а тел ь с тв о.

Если ах — префикс идентификатора позиции», то в силу леммы 9,3(а) х — префикс идентификатора позиции»+1. П Теперь мы готовы описать алгоритм, который строит позицион- ное дерево Т» для х» из позиционного дерева Т,+, для х»+,. Алгоритм 9.5. Построение Т, из Т».. Вход. Цепочка а,,а„а ем позиционное Т„., и вспомогательное А»„деревья длн х»+,— — а,„,...а„а,+,. 391 гл а ллгоентмы ндантненклции Выход. Позиционное Т~ н вспомогательное А~ деревья для хь Метод.

1. Находим лист с меткой 1+1 в Т„,. (Это последний добавленный к Т~~, лист,) 2. Проходим по пути, ведущему нз этого листа в корень дерева Т,„, до такого узла и, что В„(а~(=1. (Узел и„соответствует тат кой самой длинной цепочке у, что а,у — префикс цепочки х, н подцепочка в х,+„начннаюшаяся в некоторой позиции й, 1<й(л.) Если такого узла нет, доходим до корня. 3.

Полагаем В,(а,)=1 для каждого узла и на пути, ндушем нз узла с меткой 1+1 в сына узла и„, расположенного на том же пути, нлн в корень, если такого и нет. (Каждый узел и на этом пути соответствует некоторому префиксу г цепочки х,~,. Поэтому ясно, что а,г — подцепочка цепочки а;х,+,.) 4. 1) Если узла и„нет, переходим к случаю 1 (ннже). 2) Если узел и„существует, но у него нет а„сына во вспомогательном дереве Аы м переходнм к случаю 2. 3) Если у и есть а,-сын и во вспомогательном дереве, переходим к случаю 3. Узел и соответствует цепочке а~у в познцнонном дереве Т~+ь Случай 1.

а, — символ, не входящий в х,~ь Тогда ндентнфнкатором позиции 1 н будет а,. Чтобы построить Т~ нз Тг,ь выполняем следующее: (а) образуем новый лист с меткой 1, являющийся а,-сыном корня дерева Т,+„ (б) полагаем В (а)=0 для всех а Е 1. Чтобы построить А1 нз А~ „ делаем новый узел с меткой 1 а,- сыном корня дерева Ам.ь Случай 2. а, входит в х,+„но в Т,+, есть лишь собственный префикс цепочки а,у (прнпнсанный пути нз корня дерева Тг,, в некоторый лист и,). Эта ситуация возникает тогда, когда нужно удлинять идентификатор некоторой позиции й, 1(йе=л, чтобы он стал идентнфнкатором позиции й в То Допустим, что у=а;„,а,+,...а~ н узел и, соответствует цепочке а,а;+, а для некоторого р(1. Тогда й — метка листа и, н а,а,,...а — идентификатор позиции й в + р Т„., (т. е.

а,а,+,...а =а„а„+,...а,). Чтобы построить 7, нз Т,+„добавляем к узлу и, поддерево с дву- '''Р мя новыми листьями, помеченными числами 1 н й. Пути, ндушему нз о, в й в этом добавленном поддереве, приписана цепочка а,+,а, ,... ...а„+„ а пути нз и, в 1 — цепочка а +,ае ,...ат+ь прн этом а,+,а,~,...а„=а +,а +,...ар Таким образом, пути нз корня дерева 'Т1 'в лист й 8удетппрнпнсана цепочка а аь г ..а а„+„ являющаяся новым идентификатором позиции й в х1, а пути нз корня в 9 В.

Характеристики

Список файлов книги