|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[254] заданным содержимым (т.е. получающийся из образца параллельным переносом). 34-2.4 У Ани на компьютере есть га-битовый файл А = (an i, ап 2, , ао), а У Бори - га -битовый файл В = (bn-i, Ьп 2, ,Ьо). Они хотят проверить, идентичны ли эти файлы, не пересылая их друг другу, следующим образом. Выбирается простое число q > 1000га и случайное целое число х £ {0,1,..., q - 1}. После этого Аня вычисляет выражение А(х) = I ajX% J mod q, \г=0 / а Боря вычисляет аналогичное выражение В(х). Покажите, что, если А ф В, существует лишь один шанс из тысячи, что А(х) = В(х) (и уж конечно А(х) = В(х), если А = В). (Указание: воспользуйтесь упражнением 33.4-4). 34.3. Поиск подстрок с помощью конечных автоматов Многие алгоритмы для поиска подстрок начинают с того, что строят конечный автомат, который находит в тексте Г все вхождения образца Р. В этом разделе мы опишем, как можно построить такой автомат. Сам по себе поиск подстроки с помощью конечного автомата весьма эффективен: каждый символ поступает на вход конечного автомата только единожды, а обработка каждого символа занимает ограниченное время, так что общее время работы есть ©(га) - после того, однако, как автомат построен! К сожалению, время на построение конечного автомата может быть велико, если велик алфавит У (в разд. 34.4 мы обсудим остроумный способ обойти эту трудность). В этом разделе мы дадим определение конечного автомата, затем рассмотрим специальный конечный автомат, предназначенный для поиска подстрок, и наконец покажем, как сконструировать этот автомат, исходя из подстроки, которую он призван искать. 34.3.1. Конечные автоматы По определению, конечный автомат (finite automaton) - это пятерка М = (Q, до, А, У, S), где: •Q - конечное множество состояний (states); •Qo & Q - начальное состояние (start state); •ACQ - конечное множество допускающих состояний (accepting states); Рис. 34.5. Переводы слов в рисунке: input - вход, state - состояние. Подпись: Конечный автомат со множеством состояний Q = {0,1}, начальным состоянием д0 = 0 и входным алфавитом £ = {а, b}. (а) Таблица значений функции перехода S. (б) Функция перехода в виде диаграммы. Состояние 1 - единственное допускающее состояние (чёрное). Стрелками показаны переходы. Например стрелка из состояния 1 в состояние 0, помеченная буквой Ь, означает, что 5(1,Ъ) = 0. Этот автомат допускает строки, оканчивающиеся на нечётное число букв а (точнее говоря, строки вида ya.k, где строка у пуста или оканчивается на Ь, а число к нечётно). Например, для входной строки abaaa последовательность состояний (включая исходное) будет (0,1, 0,1, 0,1), и эта строка допускается; для входной строки abbaa последовательность состояний будет (0,1, 0, 0,1, 0), и эта строка отвергается. •£ - конечный входной алфавит (input alphabet); •6 - функция из Q X £ в Q, называемая функцией перехода (transition function) автомата. Первоначально конечный автомат находится в состоянии до! затем он по очереди читает символы из входной строки. Находясь в состоянии q и читая символ а, автомат переходит в состояние S(q, а). Если автомат находится в состоянии q £ А, говорят, что он допускает (accepts) прочитанную часть входной строки; если же q £ А, то прочитанная часть строки отвергнута (is rejected). На рис. 34.5 показан пример простого автомата с двумя состояниями. С конечным автоматом М связана функция (р: £* -> Q, называемая функцией конечного состояния (final-state function), определяемая следующим образом: <~p(w) есть состояние, в которое придёт автомат (из начального состояния), прочитав строку w. Автомат допускает строку w тогда и только тогда, когда <~p(w) £ А. Функцию Lp можно определить рекуррентно: 34.3.2. Автоматы для поиска подстрок Для каждого образца Р можно построить конечный автомат, ищущий этот образец в тексте (см. рис. 34.6, где изображен автомат, соответствующий образцу Р = ababaca). Зафиксируем до конца этого раздела строку-образец Р. Первым шагом в построении автомата, соответствующего строке-образцу Р[1..га], будет построение по Р вспомогательной для любых w £ £* и а £ £. функции а: £* -> {0,1,..., то}, называемой суффикс-функцией (suffix function). По определению, а сопоставляет строке ж длину максимального суффикса ж, являющегося префиксом Р: Поскольку Р0 = е является суффиксом любой строки, а определена на всем £*. Пример: если Р = ab, то а(е) = 0, <т(ссаса) = 1, (т(ссаЬ) = 2. Если длина Р равна то, то <т(ж) = то тогда и только тогда, когда Р - суффикс ж. Если ж □ у, то и (ж) <?(у)- Теперь определим конечный автомат, соответствующий образцу Р[1..то], следующим образом: •Множество состояний есть Q = { 0,1,..., то }. Начальное состояние до = 0, единственное допускающее состояние есть то. •Функция перехода 6 определена следующей формулой (д - состояние, a G £ - символ): Объясним, откуда берётся формула (34.3). Мы хотим сконструировать автомат таким образом, чтобы при его действии на строку Г соотношение являлось инвариантом (тогда равенство <~р(Т{) = то будет равносильно тому, что Р входит в Г со сдвигом г - тп, и автомат тем самым найдёт все допустимые сдвиги). Но в этом случае вычисление перехода по формуле (34.3) необходимо для поддержания истинности инварианта (см. теорему 34.4 ниже). Например, в автомате рис. 34.6, имеем 5(5, b) = 4: если g = 5, прочитанная часть входа кончается на ababa, и после добавления входного символа b наибольший суффикс прочитанной части, являющийся префиксом Р, будет равен abab. Запишем действие конечного автомата, ищущего подстроку Р длины то в данном тексте Г, в виде программы (8 обозначает функцию перехода): Finite-Automaton-Matcher(Т,\deltа,т) 1п \gets length[Т] 2q \gets О 3for i \gets 1 to n 4do q \gets \delta(q, T[i]) 5if q=m 6then s \gets i-m 7print Образец входит со сдвигом s Поскольку эта программа обрабатывает каждый символ из текста Г по разу, время её работы есть 0(п). Однако следует учесть а (ж) = max{ к : Рк □ ж }. (34.3) (34.4) |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||