1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 79
Текст из файла (страница 79)
ПОЗИЦИОННЫЕ ДЕРЕВЬЯ Рнс. 9.23. Части дерева Ть важные для случая 2. Штриховыми линиями наоб- ражены ребра дерева АР лист с — цепочка а,а,~т...аяа,+и являющаяся идентификатором позиции 1 в хь Точнее, для построении Т, из Т,+, выполняем следующее. 1) Двигаясь по пути в Ть идущему из и в корень, находим узел и„являющийся для узла и первым предком с апсыном в А,+,. Пусть о, — этот апсын. В Т;+, узел и, — лист с меткой й для некоторого 1(й<л. Стираем у о, метку й. 2) Пусть ии и„..., и, и„— последовательность узлов на пути в Т,+„идущем из и, в и .
Предположим„что ребро из ил в ил+, помечено символом сл, 1 =й<д, а ребро из ир в и,— сймволом с, как показано на рис. 9.23 (енса...ср=-аре,ар~в .. ...ат — — а,+,а,+,...а, где символы а, те же, что й выше). 3) В Т; образуем д новых узлов о„ о,„ ...о,, и . Делаем о„„ с„-сыном узла о„для 1~3(д.
Делаем и„ср-сыном узла ер. 4) Пусть 1=1+ глубина узла и и лр=й+ глубйна узла и . Добавляем к Т, два новых узла с метками 1 и е. Лист 1 делаем атч.,-сыном узла о, а лист й делаем а„+,-сыном узла о„. 393 гл. з. ллгогитмы идвнтичиклции б) Для всех аЕ! полагаем В„[а]=В„,(а) для каждого пЕ (и„ Ом °, пч, О, й). 6) Полагаем В,(а)=0 для всех аЕ1.
Чтобы построить А, из А,+„выполняем следующее. 7) Делаем о, а,-сыном узла и„в Аь 8) Пусть и' будет а~+,-сыном узла и, в Т,~,. Новый лист с меткой 1 делаем апсыном узла и' в Аь 9) Пусть и" будет а„„-сыном узла и в Т;~,. Новый лист с меткой й делаем апсыном узла и" в Аь 1О) Делаем пь а,-сыном узла и„в А~ для 2(й(д. Случай 3. Узел и имеет ансына о в А„,. В этом случае надо рассмотреть две ситуации. (а) и„ вЂ” листе меткой й в Т,~,. Такая ситуация возникает, когда зЯ=а,а,~ь ..а,а~,, и з;~,(й)=а„аь,...а„, причем а а ...а„=а,а,+,...ад это частный вид случая 2, когда п,=о„, Чтобы построить Т, из Т,~ь удаляем метку Й из узла п и образуем для узла о„ аг,,-сына с меткой 1 и а ,-сына с меткой й.
Детали этого построения те же, что и в случае 2 (без шагов 3, 7 и 10). (б) о — внутренний узел дерева Т;~,. Такая ситуация возникает, когда Я~ — — Я~+,(1(з~(1)). Чтобы построить Т; из Т;+,, просто образуем для узла п„ат+мсына (которого у него нет) и помечаем этот лист меткой 1.
Подробный алгоритм таков: 1 Пусть 1=1+ глубина узла и„. 2. Новый узел с меткой 1 делаем а~+,-сыном узла и в Т,. (Заметим, что у п не может быть а~+,-сына в Т,~, в силу максимальности у.) 3. Полагаем В;(а)=0 для всех аЕ 7. Поскольку аиуазэ, не является подцепочкой цепочки х„„то, разумеется, аа,да~+, не является подцепочкой цепочки х, ни для какого а. 4. Чтобы построить А~ из А~ „берем узел и', являющийся а,~;сыном узла и„в Тщ. (В Т~,, узел и' соответствует уа~+,.) Новый узел 1 делаем а;-сыном узла и' в А,+,.
(В А; узел 1 будет соответствовать цепочке ат,.,улан) Связи между узлами, упомянутыми в случае 3(б), показаны на рис. 9.24. Пример 9.22. Пусть аь...а„а„,,=аббай63 а Т, и А, — деревья с рис. 9.22. Алгоритмом 9.5 строим Т, и А, из Т, и А,. Здесь 1=1 и а,=а. Прежде всего отыскиваем лист с меткой 2 и, поскольку В,(а)=0, полагаем В,[а)=1 и поднимаемся в узел, обозначенный и на рис. зэа З.В. ПОЗИЦИОННЫЕ ДЕРЕВЬЯ Рис. 9.24.
Части дерева Ть важные для случая 3 (б). Двумя штриховыми линиямн с метками а; изображены ребра дерева Аь 9.22. В узле и находим, что В,!а]=1, поскольку аЬЬ вЂ” подцепочка цепочки ЬЬаЬЬ9. Таким образом, узел и — это и . Теперь ищем узел о, т. е.
а-сына узла и в А,. Узла о„нет, так что здесь подходит случай 2. Узел ш, т. е. отец узла и в Т„не имеет а-сына в А,. Но узел г, отец узла в, имеет. Им будет узел 4. Поэтому на шаге 1 случая 2 мы находим, что о, — узел с меткой 4 в Т, и А,. На шаге 2 находим, что 4=2, и,=г и из=в. Кроме того, с,=с,=Ь. Поэтому на шаге 3 образуем узел о, являющийся Ь-сыном узла с меткой 4 в Т, (в Т, он утратил свою метку). Образуем также узел о„и делаем его Ь-сыном узла о. На шаге 4 получаем /=-3.
Поскольку бывшая метка й узла о, равна 4, заключаем, что т=б. Находим а)е,=а и а е,=9. Поэтому новые узлы с метками 1 и 4 становятся соответственно а-сыном и 9- сыном узла о„. Дерево Т, изображено на рис. 9.25. Остальные шаги оставляем в качестве упражнения. О) Лемма 9.4. Если Т,+, и А,е, — позиционное и вспомогательное деревья для х~ „то деревья Тз и А и построенные алгоритмом 9.5,— позиционное и вспомогательное деревья для х,. Д о к а з а т ел ь с т в о. Допустим, что Те, представляет множество 5,+, идентификаторов позиций в х,+„а А;+, — вспомогательное дерево для Т„,. Здесь могут быть две возможности: 1) Вз=Быз О (зг(1)), 2) Яз=(5з+з — (зз,з(я))) 0 (зз(й), з~(1)) для некоторого((Ь<п.
39$ ГЛ. З. АЛГОРИТМЫ ИДЕНТИФИКАЦИИ Рис. 9.2о. Окончательное позиционное дерево Ти Первая возможность покрывается случаями 1 и 3(б) алгоритма 9.5, вторая — случаями 2 и 3(а). Рассуждения, необходимые для доказательства корректности алгоритма 9.5 в случаях 1 — 3, включены в его описание. П Таким образом, позиционное дерево для произвольной цепочки можно построить следующим алгоритмом. Алгоритм 9.6. Построение позициоииого дерева Вход.
Цепочка хф =а,...а„а„„где а, Е 1 для 1«=1~а и а„+,—— Выход. Позиционное дерево Т, для х6. Метод. 1. Пусть Т„т, — позиционное дерево иа рис. 9.26 и В,(а)= .В„~1(а1=0 для всех а Е 1. 2. Пусть А +, — вспомогательное дерево, совпадающее с деревом иа рис. 9.26.
3. 1ог 1 «-и з(ер — 1 ипбП 1 бо алгоритм 9.5 для построения Тз и А~ из Тьь, и А~+И (:1 Теорема 9.12. Алгоритм 9.6 строит позиционное дерево для цепочки х6 за время, пропорциональное числу умов в окончательном позиционном дереве Т,. в.в. позиционные дннввья Рнс. 9.26. Начальное позиционное дерева.
Д о к а з а т ел ь от в о. На шаге 1 алгоритма 9.5 можно найти лист 1+! за фиксированное время с помощью указателя на этот лист, установленного в момент добавления листа к Тс„. Когда к Т, добавляется с, этот указатель переводится на 1. Работа, производимая при каждом выполнении шагов 2 и 3, очевидно, пропорциональна длине пути из 1+1 в и, а при каждом выполнении шага 1 постоянна. Легко проверить, что время, затрачиваемое на выполнение любого из случаев 1 — 3 алгоритма 9.5, пропорционально числу узлов, добавляемых к дереву. Таким образом, общее время, которое тратится всеми частями алгоритма 9.5, кроме шагов 2 и 3, пропорционально размеру дерева Т,.
Осталось показать, что сумма расстояний между узлами 1+1 и и (или корнем, если узла ид нет) в Т,, для 1<1<л не превосходит размера дерева Т,. Обозначим эти расстояния через с(„ да, ... ..., й„+и и пусть е,, 1<1<л+1„— глубина узла 1 в Т,. Простой анализ случаев 1 — 3 показывает, что е, < е,е, — Ис+с+ 2.
(9.1) Просуммируем обе части неравенства (9.1) по ! от 1 до л: ее! '~,' с(с<2л+е„+,— е,. (9.2) с=в Из (9.2) непосредственно следует, что время, затрачиваемое шагами 2 и 3 алгоритма 9.5, составляет 0(л) и, значит, по порядку не превосходит размера дерева Т,. П Как уже отмечалось, позиционное дерево для цепочки длины л может содержать 0(п') узлов. Поэтому любой алгоритм идентификации, в котором строится такое дерево, должен иметь временную сложность 0(л'). Однако можно "уплотнить" позиционное и вспомогательное деревья, сжав все цепи в позиционном дереве в один узел. Целью называется путь, каждый узел которого обладает в точности одним сыном.
Нетрудно показать, что уплотненное позиционное дерево для цепочек длины л содержит не более 4п — 2 узлов. Уплот- 337 ГЛ. 9. АЛГОРИТМЫ ИДЕНТИФИКАЦИИ ненное дерево может давать ту же информацию, что и исходное позиционное дерево, и потому его можно использовать в тех же алгоритмах идентификации. Алгоритм 9.5 можно модифицировать так, чтобы он строил уплотненные позиционное и вспомогательное деревья за линейное время.
Мы не приводим здесь этот модифицированный алгоритм потому, что он аналогичен алгоритму 9.5, а также потому, что во многих приложениях можно ожидать, что размер позиционного дерева будет пропорционален длине входной цепочки, В замечаниях по литературе указаны работы, в которых излагается алгоритм с уплотнением позиционного дерева и другие его приложения. УПРАЖНЕНИЯ 9.1. Постройте регулярные выражения и графы переходов ко- нечных автоматов для следующих регулярных множеств цепочек в алфавите 7=(а, Ь).
(а) Все цепочки, начинающиеся и кончающиеся символом а. (б) Все цепочки, не содержащие двух символов а подряд. *(в) Все цепочки, содержащие нечетное число символов а и четное число символов Ь. *(г) Все цепочки, не содержащие подцепочки аЬа. 9.2. Докажите, что множество, допускаемое НКА на рис. 9.1, имеет вид (а+Ь)*аЬа. 9,3. Постройте НКА, допускающие регулярные множества (а) (а+Ь)*(аа+ЬЬ), (б) а*Ь*+Ь*а*, (в) (а+е) (Ь+е) (с+в). 9.4. Покажите, что дополнение регулярного множества регу- лярно. *9.5.
Покажите, что множества цепочек (а) (акЬП1п~~в1) (б) (вв1в~(а, Ь)*), (в) (в!в~ (а, Ь)* и в=вл) (т. е. множество палиндромов) не регулярны. 9.6. Пусть х=а,а,...а„ вЂ” данная цепочка и а — регулярное выражение. Модифицируйте алгоритм 9.1 так, чтобы он находил наименьшее число й, а по нему (а) наименьшее 1 н (б) наибольшее 1, такое, что акт~ Р ..ак принадлежит множеству, представленному выражением гх. Указание: Каждому состоянию из Я, поставьте в со- ответствие целое число 1. *9.7. Пусть х и а те же, что и в упр. 9.6.
Модифицируйте алго- ритм 9.1 так, чтобы он находил такое наименьшее 1 и по нему наи- 39$ УПРАЖНЕНИЯ большее й, что аяая~о ..аь пРинадлежит множествУ, пРедставлен- ному выражением а. 9.8. Пусть х и а те же, что и в упр. 9.6. Постройте алгоритм, ко- торый находил бы все подцепочки в х, принадлежащие множеству, представленному выражением а. Какова временная сложность ва- шего алгоритма? *9.9. Пусть 1 — алфавит и Я вЂ” символ, не принадлежащий ).
Целочкой с несущественными символами (ЦСНС) назовем цепочку в алфавите! 11 (8). Будем говорить, что ЦСНС Ь,Ь,...Ь„идентифи- цируется с ЦСНС а,а,...а„в позиции 1, если для всех /, ((~(н, либо ая=Ь,, „либо один из символов ая или Ь|,+, есть 16. Пока- жите, что для фиксированного алфавита ) проблема определения позиций, в которых одна ЦСНС идентифицируется с другой, экви- валентна по асимптотической временной сложности (и!или)-умноже- нию, т.
е. операции вида ся=Ус(, Ле~ „.„где все сн д; и е; булевы ! 3 **9.10. Покажите, что можно определить позиции, в которых одна ЦСНС идентифицируется с другой, за время ОА(л!ой' л 1оя 1оя и). Указание: Используйте упр. 9.9 и алгоритм Шенхаге — Штрас- сена для умножения целых чисел. 9.11. Напишите алгоритм сложности 0(н), который по данным цепочкам а,а,...а„и Ь,Ь,...Ь„узнавал бы, существует ли такое й, что а,=Ь,А~П „„для 1 =Ы и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
