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

                                 Рис.7.2
      Если цепочки-образы не содержат итераций, то при таком разбиении на
блоки поиск может быть выполнен параллельно во всех блоках. Если же
цепочка-образ не имеет фиксированной длины (при её задании используется
итерация), то алгоритм просмотра блоков последовательности усложняется, и
сужаются возможности параллельной обработки. Длина области перекрытия
определится в этом случае количеством символов в цепочке
предшествующих внешней итерации. Причем если при поиске в блоке эта
часть цепочки обнаружена, то в дальнейшем необходимо просматривать
последовательно все следующие за этим блоки до тех пор, пока не будет
обнаружено, что искомая цепочка прервалась или цепочка найдена.
      Исходя из вышесказанного, длину области перекрытия можно
определить следующим образом. Пусть максимальная длина цепочки (или её
части предшествующей внешней итерации) равна N, тогда длина перекрытия
L должна быть равна L=N-1. Единица вычитается для того, чтобы цепочка,
если она есть, не вошла в последующий смежный блок. При таком условии
невозможен случай, когда часть одной и той же цепочки лежала бы в двух
смежных блоках. Естественно, что и длина перекрытия не может быть
больше выбранной длины блока.
      Такое деление на блоки соответствует условиям реальных задач,
поскольку обычно длина искомой цепочки намного меньше длины файла,
внутри которого она ищется.
      Кроме того, при разбиении последовательности на блоки нужно учесть
следующее. Если среди искомых есть цепочки, длины которых меньше N, то
при поиске возможен случай, когда такие цепочки целиком будут лежать в
двух смежных блоках в области перекрытия. Тогда при поиске они будут
учтены дважды. Для решения этой проблемы можно предложить следующее.
Если в блоке обнаружена такая цепочка, то нужно проверить - не лежит ли
последний символ этой цепочки внутри области перекрытия. Если последний
символ окажется в пределах области перекрытия, то полученный результат
поиска можно игнорировать, т.к. эта цепочка будет найдена в следующем
блоке.
      На этом декомпозиция данных завершается, т.к. разбиение символа,
как элемента данных, невозможно. Символ, являясь входным сигналом на
очередном шаге алгоритма, неделим. Операции, полученные при такой
декомпозиции, с входными данными очевидны, а именно, в зависимости от
значения очередного входного сигнала происходит изменение состояния
алгоритма поиска.
      Разбиение по функциям, используемым в алгоритме, выполняем с
учетом их иерархии. В алгоритме можно выделить следующие функции:
      1)    функция поиска одной цепочки-образа;
      2)    функция вычисления уравнения НДСКУ;


                                                                      216