9.2. РАСПОЗНАВАНИЕ ОБРАЗОВ, ЗАДАВАЕМЫХ РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ

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

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

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

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

Один из способов моделирования поведения НКА М на цепочке-тексте превратить в детерминированный конечный автомат, как в теореме 9.3. Но такой путь может оказаться слишком дорогим, поскольку от регулярного выражения можно перейти к состояниями, а затем к ДКА с почти состояниями. Уже само построение ДКА может вызвать непреодолимые трудности.

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

Применяя эту технику, можно не строить автомат а вычислить только те его состояния, которые появляются при обработке цепочки х. Чтобы объяснить, как найти множество надо показать, как построить по Легко видеть, что

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

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

Рис. 9.11. (см. скан) Моделирование недетерминированного конечного автомата.

Решающее свойство в теореме 9.2 заключалось в том, что на графе переходов из каждого состояния автомата выходит не более двух ребер. Это свойство позволяет показать, что на входной цепочке алгоритм 9.1 (см. ниже) тратит на моделирование НКА, построенного из шагов.

Алгоритм 9.1. Моделирование недетерминированного конечного автомата

Вход. и цепочка из

Выход. Последовательность где

Метод. Чтобы получить сначала найдем множество состояний содержит для некоторого Затем

вычислим "замыкание" множества добавив к все такие состояния и, что содержит и для некоторого ранее оказавшегося в Это замыкание (оно и будет множеством строится с помощью очереди состояний для которых множество еще не рассматривалось. Алгоритм приведен на рис. 9.11.

Пример 9.6. Пусть изображенный на рис. 9.6, в. Допустим, что на вход подана цепочка Тогда в строке 2. В строках 9—12 рассмотрение состояния приводит к добавлению в ОЧЕРЕДЬ и в Рассмотрение не добавляет ничего, поэтому Затем в строке Рассмотрение добавляет а рассмотрение добавляет Рассмотрение не добавляет ничего, а рассмотрение добавляет Таким образом, Затем в строке Рассмотрение добавляет Рассмотрение добавляет Итак,

Теорема 9.4. Алгоритм 9.1 правильно вычисляет последовательность где

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

Теорема 9.5. Пусть в диаграмме автомата состояниями из каждого узла выходит не более ребер. Тогда на входной цепочке длины алгоритм 9.1 тратит шагов.

Доказательство. Исследуем построение множества для одного конкретного значения Строки 8—12 на рис. 9.11 занимают шагов. Поскольку для данного никакое состояние не попадает в ОЧЕРЕДЬ дважды, то цикл в строках 7—12 требует времени. Поэтому легко показать, что тело основного цикла, т. е. строки 2—12, занимает времени. Таким образом, весь алгоритм занимает времени.

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

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

Доказательство. По теореме 9.2 можно построить автомат которого не более состояний и из каждого из них выходит не более двух ребер. Поэтому в теореме 9.5 не превосходит 2.

Исходя из алгоритма 9.1, можно построить различные алгоритмы распознавания образов. Например, пусть даны регулярное выражение а и цепочка-текст и надо найти наименьшее число для которого существует такое что принадлежит множеству, представленному выражением а. С помощью теоремы 9.2 можно построить по а НКА М, допускающий язык Чтобы найти наименьшее число для которого принадлежит можно после блока, состоящего из строк 2—12 на рис. 9.11, вставить тест, проверяющий, содержит ли множество состояние из . В силу теоремы 9.2 можно сделать одноэлементным, так что такой текст не займет много времени; достаточно шагов, где число состояний в Если содержит состояние из то прерываем основной цикл, поскольку обнаружено, что кратчайший префикс цепочки х, который входит в

Алгоритм 9.1 можно модифицировать и так, чтобы он для каждого упомянутого находил такое наибольшее (или наименьшее что входит в множество, представленное выражением а. Это делается приписыванием целого числа каждому состоянию из множеств Число, приписанное состоянию указывает такое наибольшее (или наименьшее) что Детали приписывания этих целых чисел с помощью алгоритма 9.1 оставляем в качестве упражнения.