9.3. РАСПОЗНАВАНИЕ ПОДЦЕПОЧЕК

Важным частным случаем общей проблемы, описанной в предыдущем разделе, является случай, когда регулярное выражение а имеет вид где каждый член цепочка в алфавите Из следствия теоремы 9.5 вытекает, что первое вхождение цепочки-образа в цепочку-текст можно найти за шагов, где I — сумма длин цепочек i Однако возможно решение и сложности Сначала рассмотрим случай, когда дана только одна цепочка-образ где каждый символ принадлежит

По цепочке у построим детерминированную машину для идентификации цепочек, которая распознает кратчайшую цепочку из входящую в х. Чтобы построить построим сначала скелетный состояниями который переходит из состояния в состояние на входном символе как показано на рис. 9.12. Состояние имеет также переход в себя при всех Состояние I можно считать указателем на позицию цепочки-образа у.

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

Рис. 9.12. Скелетная машина.

(изменений состояния). имеет то же множество состояний, что и скелетная машина. Поэтому состояние машины соответствует префиксу цепочки-образа у.

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

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

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

Пример 9.7. Пусть Функция принимает значения

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

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

Иными словами, эта та же функция примененная раз к (В примере )

Снова предположим, что после прочтения находится в состоянии В этот момент итерирует

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

Таким образом, движется назад через состояния до тех пор, пока не встретит такое что условие 1 или 2 будет выполнено для но не для Если выполнилось условие 2, то переходит в состояние 0. В любом случае входной указатель сдвигается на

В случае 1 легко проверить, что поскольку самый длинный префикс цепочки у, который являлся суффиксом цепочки то самый длинный префикс цепочки у, который является суффиксом цепочки В случае 2 никакой префикс цепочки у не является суффиксом цепочки ахаг.

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

Пример 9.8. Пусть Машина идентификации цепочек изображена на рис. 9.13. Штриховые стрелки указывают значения функции отказов для всех состояний. На входе машина пройдет через такую последовательность состояний:

Например, вначале машина находится в состоянии 0. Прочитав первый символ из х, она переходит в состояние 1. Так как из состояния 1 нет перехода по второму входному символу то переходит в состояние 0, т. е. в значение функции отказов для состояния 1, при этом входной указатель не сдвигается. Так как первый символ в у отличен от то выполнено условие 2, и остается в состоянии и сдвигает входной указатель на позицию 3.

Рис. 9.13. Машина идентификации цепочек.

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

Функцию можно итеративно вычислить почти по той же схеме, по какой работает По определению Допустим, что вычислены Пусть Чтобы вычислить исследуем Если то поскольку

Если то находим наименьшее для которого либо

В случае 1 полагаем В случае 2 полагаем Детали даны в следующем алгоритме.

Алгоритм 9.2. Вычисление функции отказов

Вход. Цепочка-образ

Выход. Функция отказов для у.

Метод. Выполнение программы на рис. 9.14.

Пример 9.9. Рассмотрим поведение алгоритма 9.2 на входе Формирование начальных данных дает Поскольку то Но так Продолжая в том же духе, получаем значения указанные в примере 9.7.

Докажем, что алгоритм 9.2 правильно вычисляет за время Сначала докажем корректность алгоритма.

Рис. 9.14. Вычисление функции отказов.

Теорема 9.6. Алгоритм 9.2 вычисляет

Доказательство. Докажем индукцией по что такое наибольшее целое что Если такого нет, то

По определению Допустим, что предположение индукции верно для всех При вычислении алгоритм 9.2, выполняя строку 4, сравнивает с

Случай 1. Пусть Поскольку это такое наибольшее что равенство выполняется. Таким образом, в строках вычисляется правильно.

Случай 2. Пусть Тогда надо найти наибольшее значение для которого если такое существует. Если такого нет, то очевидно, что правильно вычисляется в строке 5. Пусть наибольшее, второе по величине и т. д. значения для которых

С помощью простой индукции убеждаемся, что поскольку по величине значение для которого наибольшее значение Для которого Строка по очереди, пока не найдет такое что если такое существует. По окончании выполнения -оператора будет если такое существует, и, значит, правильно вычисляется в строке 5.

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

Теорема 9.7. Алгоритм 9.2 вычисляет за шагов.

Доказательство. Строки 3 и 5 имеют фиксированную сложность. Сложность -оператора пропорциональна числу уменьшений значения оператором который стоит после в строке 4. Единственный способ увеличить это присвоить в строке 6, затем увеличить на 1 в строке 2 и положить в строке 3. Поскольку вначале а строка 6 выполняется не более раз, заключаем, что -оператор в строке 4 не может выполняться более I раз. Поэтому строка 4 требует времени. Остальная часть алгоритма, очевидно, имеет сложность и потому весь алгоритм тратит времени.

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

правильно находит самое левое вхождение цепочки у в цепочку-текст

С помощью тех же рассуждений, что и в теореме 9.7, можно доказать, что при обработке входной цепочки х машина изменит свое состояние не более раз. Поэтому можно узнать, является ли у подцепочкой цепочки х, проследив изменения состояния машины на входе х Для этого надо лишь знать значение функции отказов на у. По теореме 9.7 эти значения функции можно найти за время Следовательно, узнать, является ли у подцепочкой цепочки х, можно за время не зависящее от размера алфавита. Если же алфавит цепочки-образа мал, а цепочка-текст значительно длиннее образа, то можно смоделировать некоторый допускающий язык Этот ДКА в точности один раз меняет состояние на каждом входном символе.

Алгоритм 9.3. Построение ДКА для

Вход. Цепочка-образ в алфавите Для удобства вводим новый символ

Выход. для которого

Метод.

1. Алгоритмом 9.2 строим функцию отказов для у.

2. Пусть где а 6 определяется так:

Теорема 9.8. Алгоритм 9.3 строит такой что

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

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

Пример для построенный алгоритмом 9.3, изображен на рис. 9.15.

На входе автомат делает такие переходы:

Рис. 9.15. Детерминированный конечный автомат, допускающий

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

Основные результаты раздела суммируем в следующей теореме.

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

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