1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 77
Текст из файла (страница 77)
Легко показать индукцией по числу шагов работы алгоритма 9.4, что 1) если ТЕРМ[С1 полагается равным Р, то ]л — терминатор для С, 2) если С добавляется к ПРЕД[Р[, то С=~О, 3) если (С, О) помещается в НОВ, то ТЕРМ[С]=]У. Таким образом, если алгоритм 9.4 обнаруживает, что ТЕРМ[С,]— заключительная конфигурация, то в силу леммы 9А утверждение "вЕ Е(Р)" верно. Кроме того, надо показать, что если ]л — терминатор для С, то ТЕРМ[С] в конце концов становится равным П. Доказательство ') Для простоты мы считаем, что Р ае делает шагов, которые ае следуют яа рас.
9.!7. звэ гл. к ллгогитмы идантификлции проводится индукцией по числу шагов в последовательности С [ — ' 0. Базис, т. е. случай нулевого числа шагов, тривиален, поскольку С=0 и ТЕРМ[С] делается равным 0 на шаге 2 алгоритма 9.4. Для шага индукции предположим, что С 1- Е [-* О, и рассмотрим отдельно два случая. Случай 1. Š— конфигурация, т, е. шаг С [- Е не является ни шагом рпзп, ни шагом рор. Тогда на шаге 3 вызывается КОРРЕКТИР(С, Е). Если к этому моменту ТЕРМ[Е1 было присвоено значение 0, то конфигурация С будет помещена в список ВРЕМ в строке 2 и в конце концов значение ТЕРМ[С] сделается равным 0 в строке 5. Если значение ТЕРМ1Е] еще не равно О, то добавляем С к ПРЕД[Е) в строке 1 процедуры КОРРЕКТИР(С, Е).
По предположению индукции мы в конце концов получим, что ТЕРМ[Е)=0. Если это случится в строке 5 процедуры КОРРЕКТИР, то С добавится к ВРЕМ в строке 7, а значение ТЕРМ[С] сделается равным 0 во время этого вызова процедуры КОРРЕКТИР. Значение ТЕРМ[Е1 не может стать равным 0 на шаге 2 алгоритма 9.4, поскольку Е+0. (Если бы оказалось, что Е=0, то ТЕРМ[Е] уже было бы присвоено значение 0 к тому моменту, когда мы стали рассматривать С ]- Е на шаге 3.) Итак, в случае ] значение ТЕРМ[С] оказывается равным О.
Случай 2. Š— это такое МО, что С [ — Е является шагом рпз]ь Тогда можно найти такие конфигурации А, В и Р, что (С, г) лежит ниже (А, В), А 1 — ч В и Р]-* О, причем каждый из этих переходов совершается за меньшее число шагов, чем переход С 1-* 0. (Конфигурация А служит "поверхностью" МО Е.) По предположению индукции, значение ТЕРМ[А) полагается равным В, а значение ТЕРМ[Я вЂ” равным О. Допустим, что последнее происходит раньше первого.
Тогда (А, В) со временем помещается в НОВ, а на шаге 4 вызывается КОРРЕКТИР(С, Р). Так как в этот момент ТЕРМИ=0, то в строке 5 полагаем ТЕРМ[С1=0. Допустим теперь, что ТЕРМ[А1 присвоено значение В до того, как ТЕРМ[Р] присвоено значение 0. Тогда при вызове КОРРЕКТИР(С,Р) ТЕРМ[Я= 8 и С добавляетсь к ПРЕД[Р). Но тогда 0 становится значением ТЕРМ[С] при вычислении ТЕРМ[г]. Это завершает индукцию и доказательство корректности алгоритма 9.4, Проанализируем время работы алгоритма 9.4. Шаги ] и 2 занимают 0(л) времени, поскольку всего конфигураций 0(и). Так как для каждой конфигурации 2ДМА делает не более одного шага, то пар конфигураций (С, 0), в которых С 1- О, всего 0(л). Поэтому процедура КОРРЕКТИР вызывается на шаге 3 не более 0(п) раз. Пара (С', 0') попадает в список НОВ, когда С' =Ф~ 0' и уже найдено, что 0' — терминатор для С'.
Так как каждая конфигурация имеет лишь один терминатор (если она его вообще имеет), то никакая пара не помещается в список НОВ более одного раза. Следователь- рнь ПОЗИЦИОННЫЕ ДЕРЕВЬЯ но, общее число пар, помещаемых в список НОВ, не превосходит 0(л). Ниже каждой пары, попавшей в НОВ, лежит ограниченное число пар, ибо если (С, О) лежит ниже (С', 0'), то положения головок конфигураций С и С', а также 0 и 0', различаются не более чем на 1. Поэтому КОРРЕКТИР вызывается 0(п) раз.
Теперь оценим общее время, затрачиваемое на подпрограмму КОРРЕКТИР. Можно показать, что в массиве ПРЕД каждая конфигурация появляется не более одного раза и в список ВРЕМ никакая конфигурация не попадает более одного раза. Общее время выполнения строк 4 — 6 процедуры КОРРЕКТИР пропорционально количеству конфигураций В, удаляемых из ВРЕМ, а время выполнения строки 7 — количеству конфигураций А, добавляемых к ВРЕМ. Так как КОРРЕКТИР вызывается не более 0(л) раз, то общее время, занимаемое процедурой КОРРЕКТИР, без учета времени на строки 4 — 6 и 7 составляет 0(л). Следовательно, алгоритм 9.4 работает линейное время.
П Результаты настоящего раздела применяются главным образом при доказательстве существования алгоритмов линейной сложности, решающих определенные задачи, Мы уже видели, что некоторые задачи идентификации образов можно сформулировать как задачи распознавания языков. Если мы сможем построить 2ДМА, распознающий язык, соответствующий задаче идентификации образов, то сможем утверждать, что существует алгоритм линейной сложности, решающий ту же задачу. Так как на входе длины и 2ДМА может делать пв или даже 2" шагов, то часто бывает проще найти алгоритм для распознавания языка на 2ДМА, чем алгоритм линейной сложности для решения задачи идентификации образов прямо на РАМ.
9.5. ПОЗИЦИОННЫЕ ДЕРЕВЬЯ И ИДЕНТИФИКАТОРЫ ПОЗИЦИЙ В предыдущем разделе мы показали, что если задачу идентификации образов можно сформулировать как задачу распознавания языка, для которой можно найти решающий ее 2ДМА, то исходную задачу идентификации образов можно решить за линейное время. Можно было бы взять прямо алгоритм 9.4 как алгоритм линейной сложности, решающий исходную задачу. Но мультипликативная постоянная, возникающая при таком моделировании, сделала бы этот подход в лучшем случае непривлекательным.
В настоящем разделе мы изучим структуру данных, которую можно использовать для идентификации образов с помощью более практичных алгоритмов, работающих линейное время. Эта структура данных применима, в частности, к следующим задачам. 1. По данным цепочке-тексту х и цепочке-образу у найти все вхождения у в х. 13 А. Ако, Дж. Хопкрафт. Дж. Увьовв гл. я. ялгооитмы идянтиоикяции 2. По данной цепочке-тексту х найти самую длинную повторяющуюся подцепочку в х. 3. По данным двум цепочкам х и у найти самую длинную подцепочку, входящую как в х, так и в у. Определение. Позицией в цепочке длины и считается любюе число от 1 до и.
Говорят, что символ а входит в цепочку х в позиции 1, если х=уаг и ~у(=1 — 1. Говорят, что подцепочка и идентифицирует позицию 1 в цепочке х, если х=уие, где ~у ~ =1 — 1, и цепочку х можно представить в виде у'их' только при у'=у, т. е. в позиции 1 начинается единственное вхождение цепочки и в х. Например„подцепочка Ьйа идентифицирует позицию 2 вцепочкеаЬЬаЬЬ. Подцепочка 66 не идентифицирует позицию 2. В оставшейся части этой главы положим х=а,а,...а„ вЂ” цепочка в некотором алфавите ! и а„+, ††(яЬ!. Тогда каждая позиция 1 цепочки х$=а,ая...а„а„+, идентифицируется по крайней мере одной цепочкой, а именно а~а,~,...а„~,.
Кратчайшая цепочка, идентифицирующая позицию 1 в х9, называется идентификатором (для) позиции 1 в х и обозначается через з((). Пример 9.19. Рассмотрим цепочку аЬЬа669. Идентификаторы позиций от 1 до 7 приведены на рис. 9.19. С) Идентификаторы позиций в цепочке х9 удобно представлять с помощью дерева, называемого 7-деревом, в котором помечены ребра и некоторые узлы. Определение. !-деревом называют помеченное дерево Т, ребра которого, выходящие из любого внутреннего узла, помечены различными символами из 7.
Если ребро (о, в) Е Т помечено символом а, то в называют аныном узла и. Позиция ~ Идентификатор аЬ6а ЬЬа Ьа а669 669 69 Б Ряс. 9Л9. Идентификаторы для оЬЬоЬЬЯ. В.В. ПОЗИЦИОННЫЕ ДЕРЕВЬЯ Деревом позиций (или позиционным деревом) (для) цепочки х$= =а,...а„а„+„где а, Е1, 1(!<и, и а„+,— — $, называют () О ®)- дерево, для которого выполнены следующие условия. 1) Т имеет и+1 листьев, помеченных числами 1, 2,..., и+!. Листья дерева Т взаимно однозначно соответствуют позициям в х3. 2) Последовательность реберных меток, стоящих на пути из кор- ня в лист с меткой (, служит идентификатором з(1) позиции Е Пример 9.17. Позиционное дерево для цепочки аЬЬаЬЬ$ изображено на рис. 9.20.
Например, путь из корня в лист с меткой 2 помечен цепочкой ЬЬа, являющейся идентификатором позиции 2. П Сформулируем некоторые основные свойства идентификаторов. Лемма 9.3. Пусть з(1) — идентификатор позиции 1 цепочки х$=а,а,...а„+,. (а) Если в(1) имеет длину !', то длина надцепочки з(! — 1) не пре- восходит 1+1.
(б) Никакой идентификатор не является собственным префик- сом другого. Д о к а з а тел ь от в о., (а) Если длина подцепочки з(( — 1) больше 1+1, то найдется такая позиция ЬФ! — 1, что а;,а, ...ащ,— — а,а„+,...а, . ПоэтомУ а;а,+ц ..а+т,=а,+,а„е, ...а„.,м и а;а,~,...а;+~, не идентифицирует позицию й получили противоречие.
(б) Легкое упражнение. П Лемма 9.3(б) гарантирует, что для каждой цепочки х9 действительно существует позиционное дерево. Рнс. 9.20. Повнннонное дерево. 13е гл. к хлгоэнтмы идентивиклции С помощью позиционных деревьев можно решить многие задачи идентификации образов, включая те, что были упомянуты в начале раздела. Пример 9.18. Исследуем основную задачу идентификации образов: "Является ли у=Ь,Ьь ..Ьр подцепочкой цепочки х=а,а,... ...а„?" Допустим, что мы уже построили для х3 позиционное дерево Т. Чтобы узнать, входит ли р=Ь,Ьь ..Ь в х, рассмотрим его как граф переходов некоторого детерминировайного конечного автомата. Иными словами, отправляясь из корня дерева Т, проследим максимально длинный возможный путь в позиционном дереве, которому приписана цепочка Ь,Ь,...Ь~ для некоторого 0(1(р. Пусть этот путь оканчивается в узле о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
