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

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

  2) функция вычисления уравнения НДСКУ;

  3) функции, соответствующие операциям при вычислении правой части уравнения
   НДСКУ.

  Разбиение алгоритма по функциям поиска каждой цепочки приведено на рис.3.5.
                    Поиск            Поиск          Поиск
                   цепочки         цепочки         цепочки
                        1                2              3
                  Рис. 3.5. Разбиение по функциям поиска цепочек
     На следующем уровне функцию поиска отдельной цепочки можно разбить по функ-
циям вычисления уравнений НДСКУ. Например, поиск цепочки 1 состоит в вычислении


                                         26