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