Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 199 стр.

некоторого i подцепочка z k ,i z v ,i1... z m , j цепочки М принадлежит языку,
представленному выражением p [58].
      В зависимости от того, какая цель преследуется в результате поиска
можно выделить следующие классы задач.
      Обнаружение факта наличия цепочки, и только. Например, наличие
в тексте слова или предложения; обнаружение сигнатуры вируса при поиске
в файле и т.п. В этом случае достаточно реализовать алгоритм поиска с
использованием модели одностороннего автомата, когда при обнаружении
цепочки вырабатывается выходной сигнал, индицирующий положительный
результат поиска.
      Обнаружение факта наличия цепочки и локализация места ее
расположения. Примером этого может быть необходимость нахождения
фразы в тексте и замены ее, или обнаружение вируса в файле и "лечение" его.
Для таких случаев необходимо реализация алгоритма поиска и локализации
двухсторонним автоматом, когда при обнаружении цепочки для локализации
ее места положения блок чтения автомата начинает перемещаться справа
налево (при этом запоминаются позиции ленты) до момента обнаружения
начала цепочки. При программной реализации, если этот поиск реализуется
как один процесс, после того как обнаружена «цепочка – образ» блок чтения
начинает перемещаться в обратном направлении для поиска начала цепочки.
Если запомнить при этом позицию конца цепочки, то затем блок чтения
можно сразу переместить вправо на позицию, следующую за ее концом. Если
же операционная система позволяет параллельно выполнить несколько
процессов, то тогда можно запустить еще один процесс для локализации
цепочки, в то время как родительский продолжает просматривать входную
последовательность. Алгоритм работы автомата в прямом направлении
реализуется на основе РВАС, а алгоритм работы в обратном на основе
«зеркальной» РВАС.
      Необходимо отметить, что задачи распознавания образов не сводятся
только к поиску одной единственной цепочки во входной
последовательности. Приведем формулировку таких задач, которые
встречаются на практике.
      1) Поиск любой из нескольких заданных цепочек, т.е. хотя бы одна из
цепочек есть в последовательности. Эту задачу можно свести к
поочередному поиску каждой цепочки в последовательности. Тогда число
просмотров будет равно числу искомых цепочек. Но в этом случае время
поиска возрастает пропорционально количеству цепочек и их длине, а в
некоторых случаях, например «поиск на лету» (без возможности повторных
просмотров входной последовательности) он в принципе становится
невозможным.
      2) Поиск наличия всех заданных цепочек, т.е. в последовательности
должны быть все искомые цепочки.


                                                                            199