Description:

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РФ ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Н. П. Вашкевич, Е. И. Калиниченко **ПРОЕКТИРОВАНИЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ В ЗАДАЧАХ ИДЕНТИФИКАЦИИ** Учебное пособие Пенза 1999 УДК 519.713 В 23 Васкевич Н.П., Калиниченко Е.И. Проектирование параллельных алгоритмов в задачах идентификации: Учеб. пособие. Пенза: Пенз. государ. ун-т, 1999. 80 с.: 18 ил., библиогр. 5 назв. Рассматриваются вопросы решения задач распознавания цепочек образов с использованием теорий регулярных выражений алгебры событий и недетерминированных автоматов. Приводятся примеры решения таких задач. Предлагается методика проектирования параллельных алгоритмов. Описывается инструментальная система, позволяющая автоматизировать разработку алгоритмов с последующей их верификацией. Учебное пособие подготовлено на кафедре "Вычислительная техника" и предназначено для студентов специальности 2201 при изучении ими дисциплин "Теория автоматов", "Недетерминированные автоматы и их применение", "Системное программирование", выполнения курсового проектирования, а также может быть использовано студентами других специальностей при изучении дисциплин связанных с синтаксическим анализом и т.п. Рецензент М. М. Бутаев, к.т.н., вед.н.с. ГНПП "Рубин" (c) Издательство Пензенского государственного университета, 1999 (c) Н. П. Васкевич, Е. И. Калиниченко **Предисловие** Задачи идентификации языков, реализуемые цифровым автоматом-распознавателем, имеют в настоящее время очень широкое применение. В частности, идентификация цепочек символов входит как составная часть во многие задачи, связанные с редактированием текстов, поиском данных и символьной обработкой. Многие программы для редактирования текстов разрешают пользователю задавать типы замен в цепочке текста. Например, пользователю необходимо заменить какое-то слово другим словом во всем тексте или его части. Чтобы выполнить такое действие, программа редактирования текста должна суметь найти вхождение слова и определить его местоположение. Некоторые искусные редактирующие программы разрешают пользователю в качестве множества заменяемых цепочек символов указывать регулярное множество. Например, пользователь может поставить задачу: "Заменить _Z*_ в тексте W пустой цепочкой", имея в виду, что в W следует стереть пару квадратных скобок и символы между ними. Антивирусной программе, для обнаружения "простых" вирусов необходимо найти последовательность байт (сигнатуру), а при поиске "полиморфных" вирусов обнаружение сигнатуры может входить как одна из составляющих технологии поиска. В данном пособии приводятся методы и примеры решения таких задач. При проверке алгоритмов использовалась система "СОМПА", в разработке которой принимали самое активное участие студенты Синев С. А. (гр. 95В1), Антонов А. В., Токарев А. Н. (гр. 96ВВ1). Использованы также результаты курсовой работы студента Евдокимова А.С. (гр. 96ВВ3). **Язык регулярных выражений алгебры событий и недетерминированные конечные автоматы** Поскольку предлагаемое решение таких задач основано на использовании языка регулярных выражений алгебры событий (РВАС) и модели недетерминированного конечного автомата (НДКА), то далее будут приведены основные положения этих теорий, а более подробный материал по РВАС и НДКА приведен в _1_. Следуя _1_, приведем некоторые понятия и определения. Событие в любом алфавите Z есть произвольное множество слов в этом алфавите. Элементарными событиями в алфавите Z называются события, состоящие из одной любой буквы алфавита Z, и событие s_e, где е - пустое слово. Под алгеброй событий в алфавите Z понимается множество всех событий в этом алфавите, на котором определены две двухместные операции: сцепление (конкатенация, умножение) и объединение (дизъюнкция), а также одна одноместная операция, называемая итерацией. Сцепление двух событий s1 • s2 это событие, состоящее из всех слов вида k1 • k2, где k1 любое слово из s1, а k2 любое слово события s2. При этом s1 • s2 = s2 • s1. В дальнейшем знак сцепления событий (•) для обозначения этой операции будем опускать. Дизъюнкция двух событий s1 ∪ s2 это теоретико-множественное объединение этих событий. Итерация события s, записываемая в виде {s}*, -это событие, состоящее из пустого слова e и всевозможных слов вида: s, ss, и т.д., т.е. {s}* = e ∪ s ∪ ss ∪ ... . В алгебре событий, при отсутствии круглых скобок изменяющих порядок действий, установлен следующий приоритет операций в порядке убывания: итерация, конкатенация и потом дизъюнкция. Регулярное событие это событие, которое можно получить из элементарных событий в результате применения к ним конечного числа раз основных операций алгебры событий. Теперь определим модель цифрового автомата распознавателя, для которого будут разрабатываться алгоритмы решения задач идентификации цепочек образов. Детерминированный конечный автомат распознаватель (ДКА) будем рассматривать как устройство, которое в каждый конкретный момент времени находится в одном из конечного множества состояний, и входной ленты (входная последовательность), состоящей из клеток, которая просматривается слева направо блоком чтения этого устройства. Каждый шаг алгоритма распознавания ДКА состоит из перехода в новое состояние, определяемого его текущим состоянием и читаемым входным сигналом, и сдвига блока чтения на одну клетку вправо. Оказывается, что любой язык представим регулярным выражением тогда и только тогда, когда он допускается некоторым конечным автоматом. Если решается задача только обнаружения наличия цепочки образа, то достаточно модели одностороннего автомата, в которой на каждом шаге алгоритма блок чтения может перемещаться на одну клетку только слева направо. Если же решается задача обнаружения местоположения цепочки образа, то необходимо использовать модель двухстороннего автомата, в которой блок чтения может перемещаться или слева направо или справа налево. Лента, которую читает автомат, должна содержать два специальных символа: "начало" (top) и "конец" (bottom), при достижении которых передвижение головки соответственно влево и вправо невозможно, о чем сообщается выработкой специальных сигналов "достижение начала"(yt) и "достижение конца"(yb). Важным обобщением понятия ДКА является НДКА. Для каждого состояния и каждого входного сигнала функция переходов НДКА имеет нуль или более вариантов выбора следующего шага алгоритма. В _1,2_ предлагается аналитический язык задания НДКА, получивший название языка систем канонических уравнений и систем выходных функций (СКУ и СВФ). Там же предлагается способ перехода от РВАС к СКУ и СВФ. Эта связка двух языков позволяет снять ограничения языка РВАС при формализации ниже перечисленных задач идентификации. Например, хотя алгоритм идентификации задачи типа "1" (смотри ниже) практически напрямую формализуется на языке РВАС, переход к его программной или аппаратной реализации мягко говоря неочевиден. Основным достоинством языка СКУ и СВФ является то, что алгоритм записанный на этом языке представляет готовое решение для программной или аппаратной реализации, и что самое главное, автором языка предложен простой и эффективный способ перехода от РВАС к СКУ и СВФ. Алгоритм построения СКУ по регулярным выражениям исходной системы событий содержит следующие этапы: 1) В каждом из регулярных выражений исходной системы событий, отмеченных соответствующими выходными сигналами, выделяют параллельные ветви в отдельные регулярные выражения. Получается система выражений, в каждом из которых в правой части (за исключением содержимого итерационных скобок) есть только операции сцепления и итерации. Ключевые слова: функция поиск, входной, define, событие, обнаружение, решение, позволять, записанный информация, количество цепочка-образ, последовательность, worker, оперативный память, алфавит, выбранный каталог, количество, однопроцессорный система, искомый, сообщение тип, выполнение, нужный проверить, событие ску, область перекрытие, использование, язык тпив, выполняться параллельно, управляющий процессор, сигнал, эз, параллельный реализация, конъюнкция, используемый, элементарный задача, параллельный алгоритм, объединение процессор, эффективный, поиск цепочка, сигнал извне, файл, взаимодействие процессор, ошибка, получить, входной сигнал, входной последовательность, выражение, hpp include, hpp, событие определяющий, автомат, выполняться, этап необходимый, затрата память, подход, общий память, общий схема, процессор, следующий, язык, иили операция, разбиение алгоритм, реализация, образ, блок, управлять, символ, программный, коммуникация, ндск, качество параметр, максимальный, система, разбиение, операция, шаг, сообщение, цепочка найденный, рассмотреть, давать, рабочий процессор, решение задача, параметр, необходимый, искомое цепочка, этап проектирование, приложение, состояние, обработка, пункт, малый, этап, язык ску, цепочка образ, цепочка, возможный, устройство, дать, необходимый коммуникация, уровень, inum events sprev, результат, верификация алгоритм, этап разбиение, программный реализация, алгоритм поиск, использовать, слева направо, параллельный, функция, кнопка, include result, простой, функциональный декомпозиция, блок чтение, результат поиск, проектирование, функция findfirstfile, должный, модель, распределение задача, распределение, уравнение, количество процессор, управляющий, разработка, выбор, include, гибкость, событие состоящий, итерационный скобка, моделирование, адрес, программа, определяться, максимальный разбиение, свф, алгебра событие, увеличение, длина перекрытие, использование блокировка, рабочий, мультипроцессорный система, вывод, общий, выполнить, каталог, тип, нужный, определение коммуникация, из-за, значение, вычисление, регулярный, ску, цепочка-образ, размещение задача, дизъюнкция, полученный, узкий место, язык рвас, использоваться, стратегия, возможность, алгоритм, мультипроцессорный, элементарный, задача, выбранный файл, определение, достаточный, задача процессор, рвас, слово, размер, поиск, длина, окно, ску свф, равный, многопроцессорный система, память, агломерация, анализатор, декомпозиция, приведенный, привести, идентификация