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