9. АЛГОРИТМЫ ИДЕНТИФИКАЦИИ

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

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

9.1. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ

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

Определение. Алфавитом называется конечное множество символов. Цепочка в алфавите I — это конечная последовательность символов из Пустая цепочка это цепочка, не содержащая символов. Конкатенацией цепочек х и у называется цепочка Если цепочка имеет вид то ее префикс (начало), у — подцепочка, суффикс (конец). Длиной цепочки х называется число различных вхождений символов в х. Например, длина цепочки равна имеет длину 0.

Языком над алфавитом называют произвольное множество цепочек в Пусть и -Два языка. Язык называемый конкатенацией есть множество

Пусть язык. Тогда положим при

Замыканием Клини (итерацией) языка называют язык а позитивной итерацией язык

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

Определение. Пусть алфавит. Регулярные выражения над I и языки, представляемые ими, рекурсивно определяются следующим образом.

1. является регулярным выражением и представляет пустое множество.

2. является регулярным выражением и представляет множество

3. Для каждого а символ а является регулярным выражением и представляет множество

4. Если регулярные выражения, представляющие множества соответственно, то являются регулярными выражениями и представляют множества и соответственно.

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

Пример 9.1.

1. - регулярное выражение, представляющее множество .

2. представляет .

3. представляет множество всех цепочек, начинающихся и кончающихся символом

Язык называется регулярным, если его можно представить регулярным выражением. Два регулярных выражения называют эквивалентными (и пишут если они представляют одно и то же множество. Например,

Понятие детерминированного конечного автомата было введено в гл. 4. Его можно воспринимать как устройство, состоящее из блока управления, который всегда находится в одном из конечного числа состояний, и входной ленты, которая просматривается слева направо своей головкой (входной головкой). Детерминированный конечный автомат выполняет "шаги", определяемые текущим состоянием его блока управления и входным символом, обозреваемым входной головкой. Каждый шаг состоит из перехода в новое состояние и сдвига входной головки на одну клетку вправо. Оказывается, что язык представим регулярным выражением тогда и только тогда, когда он допускается некоторым конечным автоматом.

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

Определение. Недетерминированным конечным автоматом (НКА) называется пятерка где

1) S - конечное множество состояний устройства управления;

2) - алфавит входных символов;

3) S - функция переходов, отображающая в множество подмножеств множества S;

4) — начальное состояние устройства управления;

5) - множество заключительных (допускающих) состояний.

Мгновенным описанием (МО) НКА М называется пара где состояние блока управления и неиспользованная часть входной цепочки (т. е. символ, обозреваемый входной головкой, и все символы справа от него). Начальным МО автомата называется МО, у которого первой компонентой служит начальное состояние, а второй — распознаваемая цепочка, т. е. для некоторой цепочки Допускающие МО - это МО вида где

Представим шаги НКА бинарным отношением на множестве мгновенных описаний. Если содержит то пишут для всех Заметим, что а — это или или символ из Если то состояние изменяется независимо от обозреваемого входного символа. Если то символ а должен стоять в очередной клетке входной ленты, а входная головка сдвигается на одну клетку вправо.

Рис. 9.1. Функция переходов .

Рефлексивное и транзитивное замыкание отношения обозначается через Говорят, что цепочка до допускается автоматом если для некоторого Иными словами, входная цепочка до допускается автоматом если найдется последовательность из нуля или более шагов, переводящая из начального в допускающее Множество цепочек допускаемых автоматом называют языком, допускаемым автоматом

Пример 9.2. Рассмотрим недетерминированный конечный автомат допускающий все те цепочки из символов которые оканчиваются цепочкой т. е. Пусть где функция определена на рис. 9.1. (Здесь без е-переходов можно обойтись.)

Пусть на вход автомата подается цепочка Тогда может сработать в соответствии с последовательностями МО, показанными на рис. 9.2. Так как и заключительное состояние, то цепочка допускается автоматом

С каждым НКА связан ориентированный граф, естественным образом представляющий функцию переходов этого автомата.

Определение. Пусть Графом переходов (или диаграммой) автомата называют ориентированный граф с помеченными ребрами. Множество ребер и метки определяются следующим образом. Если содержит для некоторого то ребро принадлежит Меткой ребра

Рис. 9.2. Последовательность МО для входа

Рис. 9.3. Граф переходов для примера 9.2.

служит множество тех для которых содержит

Пример 9.3. Граф переходов для НКА М из примера 9.2 изображен на рис. 9.3. Заключительное состояние обведено двойным кружком.

Диаграммы НКА и задачи о путях на графах можно связать с помощью определенного замкнутого полукольца. Пусть I — алфавит; положим Из разд. 5.6 известно, что замкнутое полукольцо, в котором — множество всех языков над 1,0 — единичный элемент относительно объединения единичный элемент относительно конкатенации

Теорема 9.1. Всякий язык, допускаемый недетерминированным конечным автоматом, регулярен.

Доказательство. Пусть и его диаграмма. Алгоритм 5.5 может найти для каждой пары узлов диаграммы язык являющийся множеством всех цепочек, помечающих пути из Метка каждого ребра диаграммы является регулярным выражением. Более того, если множества вычисленные алгоритмом 5.5, представимы регулярными выражениями, то в силу строки 5 этого алгоритма множества также представимы регулярными выражениями. Следовательно, каждый язык можно представить регулярным выражением, а потому он регулярен. Тогда регулярное множество, ибо по определению объединение регулярных множеств регулярно.

Теорема, обратная к теореме 9.1, также верна. Иными словами, для данного регулярного выражения найдется НКА, допускающий язык, представленный этим регулярным выражением.

Рис. 9.4. Конечные автоматы, допускающие языки, представленные регулярными выражениями длины

С точки зрения сложности вычислений наиболее важно, что можно найти НКА, у которого число состояний не больше удвоенной длины данного регулярного выражения и который из каждого своего состояния может перейти не более чем в два других.

Теорема 9.2. Пусть а — регулярное выражение. Тогда найдется допускающий язык, представленный а, и обладающий такими свойствами:

1) , где длина выражения а,

2) для каждого а множество пусто,

3) для каждого сумма чисел по всем а из не превосходит 2.

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

Для шага индукции рассмотрим четыре возможных вида где и — регулярные выражения. В случае представляют один и тот же язык, так что индукция очевидна. Рассмотрим другие случаи. Пусть допускающие языки, представленные выражениями соответственно, причем их множества состояний не пересекаются. Пусть начальные состояния этих автоматов, а их заключительные состояния. Графы переходов для случаев показаны на рис. 9.5.

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

Рис. 9.5. Графы переходов автоматов, допускающие языки, представленные регулярными выражениями

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

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

Пример 9.4. Построим НКА для регулярного выражения длина которого равна для и с изображены на рис. 9.4, в. С помощью конструкции рис. 9.5, в построим автомат для как показано на рис. 9.6, а. Затем с помощью конструкции рис. построим автомат для как показано на рис. Наконец, с помощью конструкции рис. 9.5, а построим НКА для Этот автомат, имеющий 10 состояний, изображен на рис. 9.6, в.

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

Рис. 9.6. Построение НКА для

оказываются полезными в распознавании образов, и сейчас мы напомним их определение.

Определение. Детерминированным конечным автоматом (ДКА) называется недетерминированный конечный автомат в котором

Теорема 9.3. Если регулярное множество, оно допускается некоторым ДКА.

Доказательство. По теореме допускается некоторым Превратим в ДКА следующим образом. Сначала найдем такие пары состояний что Чтобы сделать это, построим ориентированный граф которого тогда и только тогда, когда содержит Затем вычислим рефлексивное и транзитивное замыкание графа Мы утверждаем, что тогда и только тогда, когда принадлежит

Теперь построим такой что и в нет -переходов.

1) содержит для некоторого и некоторого а

2) Для каждого и каждого

Рис. из примера 9.5.

В качестве упражнения предлагаем доказать, что Разумеется, в нет переходов по

Далее по построим состояния которого образуют множество-степень для Другими словами, где

1) для каждого подмножества множества и каждого а содержит для некоторого

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

Пример 9.5. Рассмотрим НКА М на рис. 9.7. Из начального состояния можно достичь и заключительное состояние по путям, помеченным символом Поэтому для вычисления рефлексивного и транзитивного замыкания ориентированного графа о котором шла речь в доказательстве теоремы 9.3, надо добавить ребро Весь граф изображен на рис. 9.8. По построим НКА М (рис. 9.9). Так как в узел входят ребра из всех узлов графа объявляем все состояния в заключительными. Так как

Рис. 9.8. Граф G.

Рис. 9.9. НКА

Рис. 9.10. ДКА

единственное ребро, входящее в узел в диаграмме для помечено символом то не входит в

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