Проектирование параллельных алгоритмов в задачах идентификации. Вашкевич Н.П - 6 стр.

мер, наличие в тексте слова или предложения; обнаружение сигнатуры вируса при поиске
в файле и т.п. В этом случае достаточно реализовать алгоритм поиска с использованием
модели одностороннего автомата, когда при обнаружении цепочки вырабатывается вы-
ходной сигнал индицирующий положительный результат поиска. Обнаружение факта
наличия цепочки и локализация места ее расположения, например найти в тексте фразу
и заменить ее на другую или обнаружить вирус и "вылечить". Для таких случаев необхо-
димо реализация алгоритма поиска и локализации двухсторонним автоматом, когда при
обнаружении цепочки для локализации ее места положения блок чтения автомата начи-
нает перемещаться справа налево (при этом запоминаются позиции ленты) до момента
обнаружения начала цепочки. При программной реализации, если этот поиск реализуется
как один процесс, после того как обнаружена цепочка - образ блок чтения начинает пере-
мещаться в обратном направлении для поиска начала цепочки. Если запомнить при этом
позицию конца цепочки то затем блок чтения можно сразу переместить вправо на пози-
цию следующую за ее концом. Если же операционная система позволяет параллельно вы-
полнить несколько процессов, то тогда можно запустить еще один процесс для локализа-
ции цепочки, в то время как родительский продолжает просматривать входную последо-
вательность. Алгоритм работы автомата в прямом направлении реализуется на основе
РВАС, а алгоритм работы в обратном на основе "зеркальной" РВАС.
   Необходимо отметить что задачи распознавания образов не сводятся только к поиску
одной единственной цепочки во входной последовательности. Приведем формулировку
таких задач, которые встречаются на практике.
   1) Поиск любой из нескольких цепочек, т.е. хотя бы одна из цепочек есть во входной
   последовательности. Вообще казалось бы эту задачу можно свести к поочередному
   поиску каждой цепочки за несколько просмотров входной последовательности, но в
   этом случае время поиска возрастает пропорционально количеству цепочек и их дли-
   не, а в некоторых случаях, например "поиск на лету" (без возможности повторных
   просмотров входной последовательности) он в принципе становится невозможным.

  2) Поиск наличия всех заданных цепочек, т.е. во входной последовательности долж-
   ны быть все из искомых цепочек до того как на вход автомата поступит "bottom"

  3) Поиск заданного количества из всех искомых цепочек т.е. например ищутся 5
   цепочек, а результат поиска может быть положительным, если будет найдены хотя бы
   3 из них. Здесь дополнительная трудность при поиске состоит в том, что заранее не-
   возможно определить порядок, в котором они будут находится во входной последова-
   тельности. Если же искать их последовательно друг за другом то из-за этого возмож-
   ны существенные потери времени.

  4) Поиск нескольких цепочек, у которых префикс и суффикс одинаковы, а корни
   различны. Если префикс обозначить через А, суффикс через С, а корни через В1,В2,В3,
   то на языке РВАС алгоритм поиска запишется как: r(у)=А&(В1 ∨ В2 ∨ В3)&С. Можно,



                                          6