9.5. ПОЗИЦИОННЫЕ ДЕРЕВЬЯ И ИДЕНТИФИКАТОРЫ ПОЗИЦИЙ

В предыдущем разделе мы показали, что если задачу идентификации образов можно сформулировать как задачу распознавания языка, для которой можно найти решающий ее 2ДМА, то исходную задачу идентификации образов можно решить за линейное время. Можно было бы взять прямо алгоритм 9.4 как алгоритм линейной сложности, решающий исходную задачу. Но мультипликативная постоянная, возникающая при таком моделировании, сделала бы этот подход в лучшем случае непривлекательным. В настоящем разделе мы изучим структуру данных, которую можно использовать для идентификации образов с помощью более практичных алгоритмов, работающих линейное время. Эта структура данных применима, в частности, к следующим задачам.

1. По данным цепочке-тексту х и цепочке-образу у найти все вхождения у в х.

2. По данной цепочке-тексту х найти самую длинную повторяющуюся подцепочку в х.

3. По данным двум цепочкам х и у найти самую длинную подцепочку, входящую как в х, так

Определение. Позицией в цепочке длины считается любое число от 1 до Говорят, что символ а входит в цепочку х в позиции если Говорят, что подцепочка и идентифицирует позицию в цепочке х, если где и цепочку х можно представить в виде только при т. е. в позиции начинается единственное вхождение цепочки и в х. Например, подцепочка идентифицирует позицию 2 в цепочке Подцепочка не идентифицирует позицию 2.

В оставшейся части этой главы положим цепочка в некотором алфавите Тогда каждая позиция цепочки идентифицируется по крайней мере одной цепочкой, а именно Кратчайшая цепочка, идентифицирующая позицию называется идентификатором (для) позиции и обозначается через

Пример 9.16. Рассмотрим цепочку Идентификаторы позиций от 1 до 7 приведены на рис. 9.19.

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

Определение. -деревом называют помеченное дерево ребра которого, выходящие из любого внутреннего узла, помечены различными символами из Если ребро помечено символом а, то называют -сыном узла

Рис. 9.19. Идентификаторы для

Деревом позиций (или позиционным деревом) (для) цепочки где называют дерево, для которого выполнены следующие условия.

1) имеет листьев, помеченных числами Листья дерева взаимно однозначно соответствуют позициям в

2) Последовательность реберных меток, стоящих на пути из корня в лист с меткой служит идентификатором позиции

Пример 9.17. Позиционное дерево для цепочки изображено на рис. 9.20. Например, путь из корня в лист с меткой 2 помечен цепочкой являющейся идентификатором позиции 2.

Сформулируем некоторые основные свойства идентификаторов.

Лемма 9.3. Пусть идентификатор позиции цепочки Если имеет длину то длина подцепочки не превосходит

Никакой идентификатор не является собственным префиксом другого.

Доказательство, Если длина подцепочки больше то найдется такая позиция что Поэтому не идентифицирует позицию получили противоречие.

(б) Легкое упражнение.

Лемма гарантирует, что для каждой цепочки действительно существует позиционное дерево.

Рис. 9.20. Позиционное дерево.

С помощью позиционных деревьев можно решить многие задачи идентификации образов, включая те, что были упомянуты в начале раздела.

Пример 9.18. Исследуем основную задачу идентификации образов: "Является ли подцепочкой цепочки Допустим, что мы уже построили для позиционное дерево Чтобы узнать, входит ли рассмотрим его как граф переходов некоторого детерминированного конечного автомата. Иными словами, отправляясь из корня дерева проследим максимально длинный возможный путь в позиционном дереве, которому приписана цепочка для некоторого Пусть этот путь оканчивается в узле Возможны несколько случаев.

1. Если не лист, то ответом будет "нет". В этом случае подцепочка цепочки нет.

2. Если лист с меткой то совпадает с символами цепочки х, начиная с позиции Тогда надо сравнить Если они не совпадают, то ответом будет "нет"; в противном случае "да", причем у входит в х, начиная с позиции

3. Если не лист, то ответом будет "да". В этом случае у — подцепочка с двумя или более вхождениями в х. Начальные позиции этих вхождений — метки листьев, принадлежащих поддереву узла позиционного дерева.

Пример 9.19. С помощью позиционного дерева можно найти самую длинную повторяющуюся подцепочку данной цепочки (два вхождения этой подцепочки могут перекрываться). Длиннейшая повторяющаяся подцепочка соответствует внутреннему узлу позиционного дерева с наибольшей глубиной. Такой узел можно обнаружить очевидным способом.

Рассмотрим нахождение длиннейшей повторяющейся подцепочки в В позиционном дереве для (рис. 9.20) есть один внутренний узел глубины 3 и ни одного внутреннего узла большей глубины. Поэтому соответствующая этому узлу цепочка самая длинная повторяющаяся подцепочка в Узлы с метками 1 и 4 указывают, где начинаются два вхождения цепочки В нашем случае они не перекрываются.

Изучим подробно задачу построения позиционного дерева. В оставшейся части этой главы будет цепочкой где единственный правый концевой маркер Через будем обозначать суффикс а через идентификатор позиции Все позиции нумеруются по исходной цепочке

Мы изложим алгоритм построения позиционного дерева для за время, пропорциональное числу узлов окончательного

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

Рассмотрим различия между множествами идентификаторов для соответственно, поскольку в алгоритме, описываемом ниже, строится из Одно очевидное различие состоит в том, что содержит идентификатор первой позиции в Из-за того, что содержит эту дополнительную цепочку, может оказаться, что идентификатор некоторой позиции содержащийся в не является идентификатором позиции Это происходит тогда и только тогда, когда идентификатор позиции служит префиксом для В этой ситуации надо удлинить цепочку чтобы сделать из нее т. е. идентификатор позиции Два идентификатора из удлинять не придется. В самом деле, если бы надо было удлинять цепочки то они обе были бы префиксами цепочки значит, одна из них была бы префиксом другой вопреки лемме

Пример 9.20. Пусть Идентификаторы для приведены на рис. 9.21. Заметим, что получается из добавлением одной цепочки . С другой стороны, для построения из потребовалось два изменения. Мы добавили и дописали к концу чтобы получить Чтобы построить добавили и дописали чтобы получить

Рассмотрим, что же нужно для построения позиционного дерева Тпредставляющего по позиционному дереву представляющему Пусть построено. Надо добавить к лист с меткой соответствующий цепочке Если для некоторого цепочка служит префиксом цепочки то надо также удлинить путь в идущий из корня в лист с меткой чтобы новый лист с меткой соответствовал цепочке Таким образом, ключом к эффективному построению по позиционного дерева для является умение быстро находить такую цепочку у, что самый длинный префикс цепочки входящий также в

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

и, кроме того, умение узнавать, служит ли префиксом идентификатора из

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

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

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

Определение. Пусть позиционное дерево для Вспомогательным деревом для позиционного дерева назовем и -дерево обладающее следующими свойствами:

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

2) узел является -сыном узла если цепочка, соответствующая — цепочка, соответствующая Таким образом, пути в идущему из корня в приписана цепочка а пути в идущему из корня в приписана цепочка

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

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

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

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

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

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

Доказательство. Если префикс идентификатора позиции то в силу леммы префикс идентификатора позиции

Теперь мы готовы описать алгоритм, который строит позиционное дерево для из позиционного дерева для

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

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

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

Метод.

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

2. Проходим по пути, ведущему из этого листа в корень дерева до такого узла что (Узел соответствует такой самой длинной цепочке у, что префикс цепочки и подцепочка в начинающаяся в некоторой позиции Если такого узла нет, доходим до корня.

3. Полагаем для каждого узла на пути, идущем из узла с меткой в сына узла расположенного на том же пути, или в корень, если такого нет. (Каждый узел на этом пути соответствует некоторому префиксу цепочки Поэтому ясно, что подцепочка цепочки

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

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

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

Случай символ, не входящий в Тогда идентификатором позиции и будет Чтобы построить из выполняем следующее:

(а) образуем новый лист с меткой являющийся -сыном корня дерева

полагаем для всех а

Чтобы построить из делаем новый узел с меткой сыном корня дерева

Случай входит в но в есть лишь собственный префикс цепочки (приписанный пути из корня дерева в некоторый лист Эта ситуация возникает тогда, когда нужно удлинять идентификатор некоторой позиции чтобы он стал идентификатором позиции Допустим, что и узел соответствует цепочке для некоторого Тогда метка листа и идентификатор позиции (т. е.

Чтобы построить из добавляем к узлу поддерево с двумя новыми листьями, помеченными числами Пути, идущему из в этом добавленном поддереве, приписана цепочка а пути из цепочка при этом Таким образом, пути из корня дерева в лист будет приписана цепочка являющаяся новым идентификатором позиции а пути из корня в

Рис. 9.23. (см. скан) Части дерева важные для случая 2. Штриховыми линиями изображены ребра дерева

лист цепочка являющаяся идентификатором позиции

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

1) Двигаясь по пути в идущему из в корень, находим узел являющийся для узла первым предком с агсыном в Пусть этот агсын. В узел — лист с меткой для некоторого Стираем у метку

2) Пусть последовательность узлов на пути в идущем из Предположим, что ребро из помечено символом а ребро из ичвиу — символом как показано на рис. 9.23 , где символы те же, что и выше).

3) В T образуем новых узлов Делаем -сыном узла для Делаем -сыном узла

4) Пусть глубина узла глубина узла Добавляем к два новых узла с метками Лист делаем -сыном узла а лист делаем -сыном узла

б) Для всех полагаем для каждого

6) Полагаем для всех

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

7) Делаем узла

8) Пусть и будет -сыном узла Новый лист с меткой делаем агсыном узла и в

9) Пусть будет -сыном узла Новый лист с меткой делаем агсыном узла в

10) Делаем узла для

Случай 3. Узел имеет В этом случае надо рассмотреть две ситуации.

(а) - лист с меткой Такая ситуация возникает, когда причем

это частный вид случая 2, когда Чтобы построить из удаляем метку из узла и образуем для узла -сына с меткой и -сына с меткой Детали этого построения те же, что и в случае 2 (без шагов 3, 7 и 10).

(б) - внутренний узел дерева Такая ситуация возникает, когда Чтобы построить из просто образуем для узла -сына (которого у него нет) и помечаем этот лист меткой Подробный алгоритм таков:

1 Пусть глубина узла

2. Новый узел с меткой делаем -сыном узла (Заметим, что не может быть -сына в в силу максимальности у.)

3. Полагаем для всех Поскольку не является подцепочкой цепочки то, разумеется, не является подцепочкой цепочки ни для какого а.

4. Чтобы построить из берем узел и, являющийся -сыном узла узел и соответствует Новый узел делаем -сыном узла и в узел будет соответствовать цепочке

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

Пример 9.22. Пусть и деревья с рис. 9.22. Алгоритмом 9.5 строим из Здесь

Прежде всего отыскиваем лист с меткой 2 и, поскольку полагаем и поднимаемся в узел, обозначенный и на рис.

Рис. 9.24. Части дерева важные для случая Двумя штриховыми линиями с метками изображены ребра дерева А

9.22. В узле и находим, что поскольку подцепочка цепочки Таким образом, узел и — это Теперь ищем узел т. е. -сына узла и в А 2. Узла нет, так что здесь подходит случай 2.

Узел т. е. отец узла и в не имеет -сына в А 2. Но узел отец узла имеет. Им будет узел 4. Поэтому на шаге 1 случая 2 мы находим, что — узел с меткой 4 в и . На шаге 2 находим, что Кроме того, Поэтому на шаге 3 образуем узел являющийся -сыном узла с меткой 4 в он утратил свою метку). Образуем также узел и делаем его -сыном узла

На шаге 4 получаем Поскольку бывшая метка узла равна 4, заключаем, что Находим Поэтому новые узлы с метками 1 и 4 становятся соответственно -сыном и -сыном узла Дерево изображено на рис. 9.25. Остальные шаги оставляем в качестве упражнения.

Лемма 9.4. Если позиционное и вспомогательное деревья для то деревья построенные алгоритмом позиционное и вспомогательное деревья для

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

Рис. 9.25. Окончательное позиционное дерево

Первая возможность покрывается случаями алгоритма 9.5, вторая — случаями Рассуждения, необходимые для доказательства корректности алгоритма 9.5 в случаях 1—3, включены в его описание.

Таким образом, позиционное дерево для произвольной цепочки можно построить следующим алгоритмом.

Алгоритм 9.6. Построение позиционного дерева

Вход. Цепочка где для и

Выход. Позиционное дерево для

Метод.

1. Пусть позиционное дерево на рис. для всех

2. Пусть вспомогательное дерево, совпадающее с деревом на рис. 9.26.

3. for алгоритм 9.5 для построения из

Теорема 9.12. Алгоритм 9.6 строит позиционное дерево для цепочки за время, пропорциональное числу узлов в окончательном позиционном дереве

Рис. 9.26. Начальное позиционное дерево.

Доказательство. На шаге 1 алгоритма 9.5 можно найти лист за фиксированное время с помощью указателя на этот лист, установленного в момент добавления листа к Когда к добавляется этот указатель переводится на

Работа, производимая при каждом выполнении шагов 2 и 3, очевидно, пропорциональна длине пути из а при каждом выполнении шага 1 постоянна. Легко проверить, что время, затрачиваемое на выполнение любого из случаев 1—3 алгоритма 9.5, пропорционально числу узлов, добавляемых к дереву. Таким образом, общее время, которое тратится всеми частями алгоритма 9.5, кроме шагов 2 и 3, пропорционально размеру дерева

Осталось показать, что сумма расстояний между узлами (или корнем, если узла нет) в для не превосходит размера дерева Обозначим эти расстояния через и пусть глубина узла Простой анализ случаев 1—3 показывает, что

Просуммируем обе части неравенства (9.1) по от 1 до

Из (9.2) непосредственно следует, что время, затрачиваемое шагами 2 и 3 алгоритма 9.5, составляет значит, по порядку не превосходит размера дерева

Как уже отмечалось, позиционное дерево для цепочки длины может содержать узлов. Поэтому любой алгоритм идентификации, в котором строится такое дерево, должен иметь временную сложность Однако можно "уплотнить" позиционное и вспомогательное деревья, сжав все цепи в позиционном дереве в один узел. Цепью называется путь, каждый узел которого обладает в точности одним сыном. Нетрудно показать, что уплотненное позиционное дерево для цепочек длины содержит не более узлов.

Уплотненное дерево может давать ту же информацию, что и исходное позиционное дерево, и потому его можно использовать в тех же алгоритмах идентификации.

Алгоритм 9.5 можно модифицировать так, чтобы он строил уплотненные позиционное и вспомогательное деревья за линейное время. Мы не приводим здесь этот модифицированный алгоритм потому, что он аналогичен алгоритму 9.5, а также потому, что во многих приложениях можно ожидать, что размер позиционного дерева будет пропорционален длине входной цепочки. В замечаниях по литературе указаны работы, в которых излагается алгоритм с уплотнением позиционного дерева и другие его приложения.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Замечания по литературе

Эквивалеитиость конечных автоматов и регулярных выражений установлена Клини [1956]. Недетерминированные конечные автоматы изучались Рабиным, Скоттом [1959], которые доказали их эквивалентность детерминированным. Алгоритм идентификации цепочек, задаваемых регулярным выражением (алгоритм 9.1), построен на основе алгоритма Томпсона [1968]. Эренфойхт, Цайгер [1974] обсуждают сложность НКА как устройства для классификации образов. Распознавание вхождения одной цепочки в другую за линейное время (алгоритм 9.3) взято у Морриса, Пратта [1970]. Моделирование 2ДМА за линейное время, а также обобщение в упр. 9.21 принадлежат Куку [1971а]. Свойства 2ДМА изучали Грей, Харрисон, Ибарра [1967]. Моделирование 2НМА за время (упр. 9.24) описано Хопкрофта, Ульмана [1968]. Упр. 9.15(6) принадлежит Честеру, а упр. 9.19(b) - Пратту. Решение упр. 9.19(b) приведено в работе Кнута, Пратта [1971].

Материал разд. 9.5, касающийся позиционных деревьев, а также понятие уплотненного позиционного дерева можно найти у Вайнера [1973]. Там же содержатся решения упр. 9.20 и 9.31-9.36 вместе с некоторыми другими приложениями; см. также Киут [19736]. Карп, Миллер, Розенберг [1972] дают несколько алгоритмов идентификации, касающихся повторяющихся цепочек. Упр. 9.9 и 9.10 о совпадении цепочек с несущественными символами принадлежат Фишеру, Патерсону [1974]. Вагнер, Фишер [1974] приводят решение упр. 9.38. В их статье и статье Хиршберга [1973] обсуждаются алгоритмы для задачи об общей подпоследовательности (см. упр. 9.37).