Способ и устройство поиска составного образца в последовательности

Способ и устройство поиска составного образца в последовательности

Иллюстрации

Показать все

Реферат

Изобретение относится к области вычислительной техники и информатики, может быть использовано в информационно-поисковых и экспертных системах, в системах высокочастотного трейдинга, в системах передачи данных, в специализированных устройствах и системах обработки символьной информации и др.

Рассматривается задача поиска составного образца в анализируемой последовательности (текст, поток данных). 13 общем случае, составной образец и анализируемая последовательность представляют одномерные структуры данных (строки), составленные из букв рабочего алфавита. Пусть заданы составной образец x длиной m-символов, содержащий z подстрок x₁, x₂…x_z с длинами t₁, t₂, …t_z, такими, что (t₁+t_2, +…+t_z≤m, и текст у длиной n-символов, где n>0, m>0 и m≤n. Требуется найти позиции вхождения подстрок из x в y, т.е. определить такие наименьшие адреса i₁, i₂…i_z, при которых справедливо

, .

В частном случае, для образцов, включающих только одну подстроку, задача поиска формулируется как поиск вхождения. При лом вюрая часть условия (1) записывается как

i₁+1=i₂; i₂+1=1i₃; .

По умолчанию выражения (2) подразумеваются, они определяют физически смежный характер расположения вхождений отдельных подстрок из x в структуре текста y.

Наиболее важным практическим случаем для систем обработки символьной информации является поиск составного образца x, содержащего z подстрок x₁, x₂…x_z с длинами, равными одному символу каждая, т.е. t₁=t₂=…t_z=1. Фактически в анализируемой последовательности y осуществляется посимвольный поиск из x, для каждого элемента которого не обязательно выполняется условие (2), но обязательно выполняемся условие (1).

Известен способ конвейерного поиска вхождений [Кулик, Б.А. Системы поиска в произвольном тексте / Б.А.Кулик // Программирование. 1987. №1 - С.6-10.], основанный на параллельном сопоставлении текущего символа образца с анализируемой последовательностью и на вычислении, хранении и обработке двух двоичных (характеристических) векторов с количеством бит, равным количеству символов в тексте. Алгоритмизация данного способа заключается в циклической обработке предыдущего и текущего характеристических векторов на основе аппаратно-ориентированной операции «косая конъюнкция», представляющей собой побитовое умножение двух двоичных векторов, причем биты предыдущего вектора со смещением на одну позицию к началу вектора. Недостаток данного способа заключается в необходимости дополнительных затрат времени на проверку позиций «1» в двоичных векторах в соответствии с распределением символов составного образца по тексту.

Известен способ матричного поиска вхождений строки-образца [Титенко, Е.А. Метод параллельною поиска по образцу и матричное устройство для его реализации / К.А.Титенко // Информационные системы и технологии. №4. - 2011 С.24-30.], основанный на двумерном представлении слов-операндов для учета позиционных и временных соотношений между символами двух строк и заключающийся в организации вычислений по диагоналям двоичной (характеристической) матрицы. Параллельная обработка матрицы состоит в побитовой обработке элементов строк и столбцов в составе k (k=m-n-1) диагоналей матрицы. Последовательности смежных «1» в составе каждой диагонали матрицы описывают структурные отношения вхождения. При организации поиска составного образца недостаток данного способа - невозможность учета позицией ню нерегулярного распределения символов составного образца по тексту и, как следствие, избыточные затраты времени на последовательную обработку каждого символа составного образца и дополнительная проверка текущего и предыдущего адресов односимвольных вхождений па условие i_j-1<i_j, где j=1…z.

Известно устройство [А.с. 1485254 СССР, МКИ G06F 12/00. Устройство для адресации по содержанию блока памяти /.А.Кулик, Э.В.Рахов, Н.Н.Востров, Т.П.Копиец - №4313200/24-24, заявл. 05.10.87; опубл. 07.06.89, Бюл. №21. 10 с., ил.] для адресации по содержанию блока памяти, состоящее из двух блоков ассоциативных признаков, блока памяти логических векторов и операционного блока, выполняющего, в том числе операцию идентификации на основе обработки двоичных векторов-столонов (поиск по столбцу). Вместе с тем ограниченность операции идентификации связана с теоретико-множественной трактовкой исходных данных. Вследствие этого структурные отношения следования в характеристических векторах не учитываются, что не позволяет непосредственно использовать операционный блок для поиска вхождений составного образца в тексте.

Известна параллельная система информационного поиска [Патент 2195015 РФ, МПК G06K 17/30. Параллельная система информационного поиска / В.М.Довгаль, С.С.Шевелев; заявитель и патентообладатель Курск, гос. техн. ун-т. - №2001 120172/09: заявл. 18.07.2001; опубл. 20.12.2002, Бюлл. №12], содержащая блок памяти вхождений, блок памяти слов, блок управления, массив блоков определения вхождений, работающих одновременно и имеющих в своем составе, регистр сдвига для хранения текста и ассоциативную память для храпения подстроки образца. Работа системы заключается в параллельном сопоставлении в ассоциативной памяти подстроки образца и текста. В случае отсутствия вхождения осуществляется сдвиг текста на одну полицию и новая итерация поиска. Недостаток данной системы - невозможность учета структурных отношений упорядочения вхождений подстрок составного образца в анализируемом тексте.

Устройством-прототипом является устройство для параллельного поиска и обработки данных [Патент 72771 Российская Федерация, МПК G06F 12/00. Устройство для параллельного поиска и обработки данных E.А.Титенко, Л.А.Лисицин, В.М.Довгаль; заявитель и патентообладатель Курск, гос. техн. ун-т. - №2007149075/22: заявл. 25.12.2007; опубл. 27.04.2008, Бюлл. №12.], состоящее из двух блоков хранения и сравнения ассоциативных признаков, блока памяти логических векторов, операционного блока и блока матричного поиска, выполняющее параллельную обработку совокупности характеристических векторов, объединенных в двумерную матрицу поиска. Недостатком данного устройства является ограниченная функциональность - устройство позволяет осуществлять только поиск вхождений образца, состоящего только из одной подстроки. Характеристическая матрица поиска имеет геометрическую форму параллелограмма, а связи между смежными элементами диагоналей имеют локальный характер, что не позволяем этому устройству решать задачу поиска составного образца в анализируемой последовательности.

Технической задачей изобретения является расширение функциональных возможностей за счет модернизации связей ячеек характеристической матрицы и ввода дополнительных элементов в характеристическую матрицу, что позволит решить поставленную задачу. Сущность модернизации характеристической матрицы заключается в совмещении параллельной побитовой обработки элементов в составе диагоналей матрицы, длина которых равна длине образца, с построчным вычислением стартовых значений ячеек характеристической матрицы.

Решение технической задачи достигается тем, что в устройство поиска составного образца в последовательности, содержащее первый и в второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов и операционный блок, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым информационными входами устройства, а выходы блоков хранения и сравнения ассоциативных признаков соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы задания режимов первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами задания режимов устройства, а четвертый, пятый, шестой входы задания режимов устройства соответственно соединены с тремя входами кодов операций операционного блока, первый выход которого является первым выходом устройства, первый вход начальной установки устройства подключен к входу начальной установки операционного блока, второй вход начальной установки - к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, введены дополнительный однобитовый выход операционного блока, который является вторым выходом операционного блока, и блок поиска составного образца, имеющим четыре входа и один выход, причем первый вход начальной установки устройства подключен к первому входу блока поиска составного образца, второй вход которого соединен со вторым выходом операционного блока, третий и четвертый входы блока поиска составного образца являются соответственно третьим и четвертым информационными входами устройства, а выход блока поиска составного образца является вторым выходом устройства, при этом блок поиска составного образца содержит элемент задержки, n регистров для храпения кодов символов составного образца разрядностью p бит каждый, m регистров для хранения кодов символов текста разрядностью p бит каждый, k триггеров позиции, а также характеристическую матрицу, состоящую из поисковых ячеек и имеющую геометрическую форму параллелограмма, размер матрицы - n×k поисковых ячеек (k-m-n+1 - количество диагоналей в матрице) и (n-1)×k двухвходовых элементов ИЛИ для построчного вычисления стартовых значений, при этом каждый регистр для хранения кодов символов составного образца и каждый регистр для хранения кодов символов текста имеют соответственно три входа (первый и второй управляющие входы и третий информационный p-разрядный вход) и один p-разрядный выход, каждый триггер позиции имеет соответственно три входа (первый и второй управляющие входы и третий информационный вход) и один p-разрядный выход, каждая поисковая ячейка имеет три информационных входа (первый и второй входы разрядностью p бит каждый, третий - одноразрядный вход) и один выход, каждая поисковая ячейка содержит двухвходовую схему сравнения на равенство p-разрядных кодов символов составного образца и текста и двухвходовой элемент И, причем первый и второй p-разрядные входы поисковой ячейки соединены соответственно с первым и вторым p-разрядными входами двухвходовой схемы сравнения на равенство соответственно, выход которой является первым входом двухвходового элемента И, выход которого является выходом поисковой ячейки, второй вход двухвходового элемента И соединен с третьим входом поисковой ячейки, причем первые p-разрядные входы всех поисковых ячеек i-ой строки матрицы (i=1-n) соединены с p-разрядным выходом i-ого регистра для хранения символа составного образца, p-разрядный выход j-ого регистра для хранения кода символа текста (j=1-m) соединен соответственно со вторыми p-разрядными входами всех поисковых ячеек, входящих в j-ый столбец матрицы, выход (i, j)-ой поисковой ячейки, кроме i=n (последняя строка матрицы), соединен с первым входом (i, j)-го двухвходового элемента ИЛИ, второй вход которого соединен с выходом (i,j-1)-го двухвходового элемента ИЛИ, кроме первого двухвходового элемента ИЛИ в текущей строке матрицы, выход (i, j)-го двухвходового элемента ИЛИ соединен со вторым входом (ij+1) двухвходового элемента ИЛИ и с третьим входом (i+1, j+1) поисковой ячейки, кроме i=n, на второй вход первого двухвходового элемента ИЛИ в каждой строке матрицы, подается значение логического «0», выход поисковой ячейки, расположенной в последней строке матрицы, соединен с третьим входом j-го триггера позиции, на третий вход каждой поисковой ячейки, расположенной в первой строке матрицы, подано значение логической «1», первый вход блока поиска составного образца соединен соответственно с первыми входами n регистров для хранения кодов символов составного образца, а также с первыми входами m регистров для хранения кодов символов текста и первыми входами k триггеров позиций, второй вход «Запись строк» блока поиска составного образца соединен со входом элемента задержки и со вторыми входами n регистров для хранения кодов символов составного образца и вторыми входами m регистров для хранения кодов символов текста соответственно, выход элемента задержки соединен со вторыми входами k триггеров позиций, выходы которых образуют информационный k-разрядный выход блока поиска составного образца, третий вход блока матричного поиска состоит из n групп по p разрядов каждая группа, кодирующих символы составного образца, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход i-ого регистра для хранения кода символа составного образца, четвертый вход блока поиска составного образца состоит из m групп разрядов по p разрядов каждая группа, кодирующих символы текста, причем j-ая группа разрядов (j=1-m) подается на третий p-разрядный вход j-ого регистра для хранения кода символов текста, каждая двухвходовая схема сравнения на равенство в составе поисковой ячейки состоит из p-входового элемента И, а также из p двухвходовых элементов суммы по модулю два с инверсией, на первые входы которых подастся соответствующий разряд из i-ой p-разрядной группы третьего входа блока поиска составного образца, а па вторые входы двухвходовых элементов суммы по модулю два с инверсией - соответствующий разряд из j-ой p-разрядной группы четвертого входа блока поиска составного образца, выходы всех двухвходовых элементов суммы по модулю два с инверсией соединены с p-входовым элементом И, выход которого является одноразрядным выходом двухвходовой схемы сравнения на равенство.

Сущность изобретения поясняется чертежами, где на фиг.1 представлена функциональная схема устройства поиска составного образца в последовательности, на фиг.2 - функциональная схема блока поиска составного образца, на фиг.3 - функциональная схема поисковой ячейки характеристической матрицы, на фиг.4 - пример поиска составного образца, на фиг.5 - временные диаграммы работы на операции «ПОИСК СОСТАВНОГО ОБРАЗЦА» («ПСО»).

Сущность предлагаемого способа заключаемся в совмещении параллельной побитовой обработки диагонально расположенных элементов характеристической матрицы, длина которых равна длине составного образца, с построчным вычислением стартовых значений для поисковых ячеек характеристической матрицы. Организации построчного вычисления начального значения поисковых ячеек характеристической матрицы позволяет учесть нерегулярный характер расположения отдельных подстрок составного образца в структуре анализируемой последовательности. Начальное значение в пределах отдельной строки матрицы формируемся как итерационная функция ИЛИ результатов посимвольного сопоставления в пределах анализируемой последовательности. Вычисленные стартовые значения «1» в позициях текущей строки характеристической матрицы инициируют процессы параллельного поиска по диагоналям матрицы, что позволяет соединить в один поисковый объект позиционно нерегулярные расположения символов составного образца.

Устройство поиска составного образца в последовательности (фиг.1) содержит блоки 1₁ и 1₂ хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, блок 4 поиска составного образца, информационные входы 4₁, 4₂, 4₃ и 4₄, информационные выходы 5₁-5₂, входы 6₁-6₆ задания режима работы, входы 7₁ и 7₂ начальной установки.

Структура блоков 1₁, 1₂, 2, 3 строго соответствуют устройству-прототипу в схемном и в функциональном отношении, состоит из совпадающих элементов и связей между ними.

Блок 4 поиска составного образца содержит два управляющих входа: «Начальная установка» 7₁ (первый вход) и вход «Запись строк» (второй вход), третий и четвертый входы для подачи символов составного образца и текста в параллельном коде через информационные входы 4₃, и 4₄ устройства, а также один информационный выход, являющийся вторым выходом 5₂ устройства. При этом второй управляющий вход блока 4 соединен со вторым выходом операционного блока 3.

Блок 4 поиска составного образца содержит элемент 31 задержки, состоящий из n пар инверторов, n регистров 32₁-32_n для хранения кодов символов составного образца, m регистров 33₁-33_m для хранения кодов символов текста, характеристической матрицы поисковых ячеек 34₁₁-34_nm. и (n-1)×k двухвходовых элементов 40 ИЛИ для построчного вычисления стартовых значений, к триггеров 37 позиций, причем регистр 32_i (i=1-n) и регистр 33_j (j=1-m) содержат первый и второй управляющие входы, третий p-разрядный информационный вход и один выход соответственно. Первые и вторые входы n регистров 32 для хранения кодов символов составного образца и первые и вторые входы m регистров 33 для хранения кодов символов текста соединены соответственно с первым и вторым управляющими входами блока 4 поиска составного образца, третий вход которого разрядностью p×n бит предназначен для параллельной записи составного образца в регистры 32₁-32_n и состоит из n групп разрядов по p разрядов каждая группа, кодирующих символы составного образца, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход регистра 32_i (i=1-n), четвертый вход блока 4 поиска составного образца разрядностью p×m бит предназначен для параллельной записи текста в регистры 33₁-33_m и состоит из m групп разрядов по p разрядов каждая группа, кодирующих символы текста, причем j-ая группа разрядов (j=1-m) подается на третий p-разрядиый вход регистра 33_j (j=1-m). Второй управляющий вход блока 4 поиска составного образца также соединен со входом элемента 31 задержки.

Характеристическая матрица поисковых ячеек 34₁₁-34_nm имеет размер n×k ячеек (k=m-n+1 - количество диагоналей в матрице), причем каждая поисковая ячейка 34_ij имеет три входа и один выход и содержит двухвходовую схему 35_ij сравнения на равенство p-разрядных кодов символов составного образна и текста и двухвходовой элемент 36 И, каждая двухвходовая схема 35_ij сравнения на равенство в составе поисковой ячейки 34_ij состоит из p-входового элемента 39 И, а также p двухвходовых элементов 38₁-38_р суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-ой p-разрядной группы третьего входа блока 4 поиска составного образца, а на вторые входы двухвходовых элементов 38₁-38_р суммы по модулю два с инверсией - соответствующий разряд из j-ой p-разрядной группы четвертого входа блока 4 поиска составного образца, все выходы двухвходовых элементов 38₁-38_р суммы по модулю два с инверсией в составе двухвходовой схемы 35_ij сравнения на равенство соединены с p-входовым элементом 39 И, выход которого является выходом двухвходовой схемы 35_ij сравнения на равенство. Первый и второй p-разрядные входы поисковой ячейки 34_ij соответственно соединены с первым и вторым p-разрядными входами двухвходовой схемы 35_ij сравнения на равенство, выход которой является первым входом двухвходового элемент 36 И, второй вход которого является третьим входом поисковой ячейки 34_ij, выходом которой является выход двухвходового элемента 36 И. Также в каждую строку характеристической матрицы, кроме последней строки, входят к двухвходовых элементов 40 ИЛИ.

Характеристическая матрица поисковых ячеек 34₁₁-34_nm имеем геометрическую форму параллелограмма, в которой в каждой строке располагается k поисковых ячеек, сдвинутых относительно следующей строки ячеек вправо на 1 позицию, начиная с ячеек первой строки 34₁₁-34_1k. Такая форма матрицы обеспечивает направление поиска по диагоналям, проходящим через ячейки от первой строки к последней строке включительно. Также в каждую строку характеристической матрицы, кроме последней строки, входят k двухвходовых элементов 40 ИЛИ. Первые p-разрядные входы k поисковых ячеек i-ой строки матрицы (i=1-n) соединены с p-разрядным выходом регистра 32_i. P-разрядный выход регистра 33_j (j=1-m) соединен со вторыми p-разрядными входами всех поисковых ячеек, входящих в j-ый столбец матрицы. Выход каждой поисковой ячейки 34_ij, кроме i=n (последняя строка матрицы), соединен с первым входом (i, j)-го двухвходового элемента 40 ИЛИ, второй вход которого соединен с выходом (i, j-1)-го двухвходового элемента 40 ИЛИ, кроме первого двухвходового элемента 40 ИЛИ в каждой строке матрицы, выход (i, j)-го двухвходового элемента 40 ИЛИ соединен со вторым входом (i,j+1) двухвходового элемента 40 ИЛИ и с третьим входом (i+1, j+1) поисковой ячейки, кроме i=n, па второй вход первого двухвходового элемента 40 ИЛИ в каждой строке матрицы, подается значение логического «0», выход поисковой ячейки, расположенной в последней строке матрицы, соединен с третьим входом j-го триггера позиции. На третий вход каждой ячейки, расположенной в первой строке матрицы, подается значение логической «1», задавая тем самым направление поиска по соответствующей диагонали от первой строки матрицы к последней строке включительно.

Триггера 37₁-37_k позиций хранят результат поиска в виде k-разрядного кода, в котором значением логической «1» отмечены позиции начала вхождений составного образца в текст. Триггер 37_i позиции (i=1-k) содержит три входа (первый и второй управляющие, третий одноразрядный информационный вход) и один выход. Первый вход блока 4 поиска составного образца соединен соответственно с первыми входами k триггеров 37 позиций, вторые входы k триггеров 37 позиций соединены с выходом элемента 31 задержки. Выходы триггеров 37₁-37_k позиций образуют k-разрядный информационный выход блока 4 поиска составного образца.

Данное устройство, как и устройство-прототип, работает в режимах «Запись» и «Операция». Режим "Запись" строго соответствует алгоритму, описанному в устройстве-прототипе.

В алгоритме режима "Операция" дополнительно к выполняемым в устройстве-прототипе вводится операция, обозначаемая как «ПСО» и имеющая собственный код операции, который подается на соответствующий вход режима работы. С учетом появления блока 4 по сравнению с устройством-прототипом в алгоритм режима "Операция" вносятся следующие дополнения.

Пусть устройство выполняет режим «Операция» с кодом операции «ПСО». На вход 7₁ «Начальная установка» операционного блока 3 и блока 4 поиска составного образца подается импульсный сигнал начальной установки, который сбрасывает в нулевое состояние регистр 22 команд по его входу 1, регистр 30 по его входу 1, а также k триггеров 37 позиций по их входу 1, n регистров 32 по их входу 1 и m регистров 33 по их входу 1. После окончания действия сигнала начальной установки на вход 6₆, режима работы операционного блока 3 подается код операции «ПСО», который обнаруживается дешифратором 23 команд и со второго выхода операционного блока 3 на второй вход «Запись строк» блока 4 поиска составного образца подается импульсный сигнал. Данный импульсный сигнал по входу «Запись строк» блока 4 поиска составного образца подается соответственно на вторые входы разрешения записи n регистров 32 для хранения кодов символов составного образца и на вторые входы разрешения записи m регистров 33 для хранения кодов символов текста, обеспечивая тем самым запись n символов составного образца и m символов текста в параллельном коде с входов 4₃ и 4₄ устройства. Также импульсный сигнал по входу «Запись строк» блока 4 поиска составного образца через элемент 31 задержки подаемся соответственно на вторые входы разрешения записи k триггеров 37 позиций. Элемент 31 задержки, выполненный в виде n пар инверторов, необходим для завершения процессов поиска составного образца по диагоналям характеристической матрицы, состоящей из поисковых ячеек 34₁₁-34_nm. Поиск начинается с ячеек первой строки характеристической матрицы. Начальный k-битовый характеристический вектор, равный 11…1, подается на третьи входы поисковых ячеек первой строки матрицы и определяет тем самым направление параллельного поиска по всем диагоналям характеристической матрицы от поисковых ячеек первой строки до поисковых ячеек последней строки включительно. Время поиска составного образца определяется величиной Т=mτ_И, где τ_И - время задержки в элементе 36 И. По завершении процессов поиска импульсный сигнал с выхода элемента 31 задержки через время Т=m2τ_инв (2τ_инв - время задержки на цепочке инверторов) записывает k-битовый результат поиска составного образца в триггера 37₁-37_k позиций. Выходы триггеров 37₁-37_k позиций являются k-разрядным выходом блока 4 поиска составного образца и образуют второй выход устройства 5₂.

Выполнение алгоритма в режиме «Операция» на остальных операциях строго соответствует устройству-прототипу.

Таким образом, достигается расширение функциональности устройства поиска составного образца в последовательности за счет модернизации связей ячеек характеристической матрицы и ввода дополнительных элементов в характеристическую матрицу поиска.

1. Способ поиска составного образца в анализируемой последовательности, отличающийся совмещением параллельной побитовой обработки элементов в составе диагоналей характеристической матрицы, длина которых равна длине составного образца в анализируемой последовательности, с построчным вычислением стартовых значений поисковых ячеек характеристической матрицы, что позволяет учесть позиционно нерегулярное расположение символов составного образца в анализируемой последовательности и соединить в один поисковый объект позиционно нерегулярные расположения символов составного образца в анализируемой последовательности.

2. Устройство поиска составного образца в анализируемой последовательности, содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов и операционный блок, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым информационными входами устройства, а выходы блоков хранения и сравнения ассоциативных признаков соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы задания режимов первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами задания режимов устройства, а четвертый, пятый, шестой входы задания режимов устройства соответственно соединены с тремя входами кодов операций операционного блока, первый выход которого является первым выходом устройства, первый вход начальной установки устройства подключен к входу начальной установки операционного блока, второй вход начальной установки - к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, отличающееся тем, что в него, во-первых, введен дополнительный однобитовый выход операционного блока, который является вторым выходом операционного блока, во-вторых, блок поиска составного образца в анализируемой последовательности, имеющий четыре входа и один выход, причем первый вход начальной установки устройства подключен к первому входу блока поиска составного образца в анализируемой последовательности, второй вход которого соединен со вторым выходом операционного блока, третий и четвертый входы блока поиска составного образца в анализируемой последовательности являются соответственно третьим и четвертым информационными входами устройства, а выход блока поиска составного образца в анализируемой последовательности является вторым выходом устройства, при этом блок поиска составного образца в анализируемой последовательности содержит элемент задержки, n регистров для хранения кодов символов составного образца в анализируемой последовательности разрядностью p бит каждый, m регистров для хранения кодов символов текста разрядностью p бит каждый, k триггеров позиций, а также характеристическую матрицу, состоящую из поисковых ячеек и имеющую геометрическую форму параллелограмма, размер матрицы - n×k поисковых ячеек (k=m-n+1 - количество диагоналей в матрице) и (n-1)×k двухвходовых элементов ИЛИ для построчного вычисления стартовых значений, при этом каждый регистр для хранения кодов символов составного образца в анализируемой последовательности и каждый регистр для хранения кодов символов текста имеют соответственно три входа (первый и второй управляющие входы и третий информационный p-разрядный вход) и один p-разрядный выход, каждый триггер позиции имеет соответственно три входа (первый и второй управляющие входы и третий информационный вход) и один p-разрядный выход, каждая поисковая ячейка имеет три информационных входа (первый и второй входы разрядностью p бит каждый, третий - одноразрядный вход) и один выход, каждая поисковая ячейка содержит двухвходовую схему сравнения на равенство p-разрядных кодов символов составного образца в анализируемой последовательности и текста и двухвходовой элемент И, причем первый и второй p-разрядные входы поисковой ячейки соединены соответственно с первым и вторым p-разрядными входами двухвходовой схемы сравнения на равенство соответственно, выход которой является первым входом двухвходового элемента И, выход которого является выходом поисковой ячейки, второй вход двухвходового элемента И соединен с третьим входом поисковой ячейки, причем первые p-разрядные входы всех поисковых ячеек i-ой строки матрицы (i=1-n) соединены с p-разрядным выходом i-ого регистра для хранения символа составного образца в анализируемой последовательности, p-разрядный выход j-ого регистра для хранения кода символа текста (j=1-m) соединен соответственно со вторыми p-разрядными входами всех поисковых ячеек, входящих в j-ый столбец матрицы, выход (i,j)-ой поисковой ячейки, кроме i=n (последняя строка матрицы), соединен с первым входом (i,j)-го двухвходового элемента ИЛИ, второй вход которого соединен с выходом (i,j-1)-го двухвходового элемента ИЛИ, кроме первого двухвходового элемента ИЛИ в текущей строке матрицы, выход (i,j)-го двухвходового элемента ИЛИ соединен со вторым входом (ij+1) двухвходового элемента ИЛИ и с третьим входом (i+1, j+1) поисковой ячейки, кроме i=n, на второй вход первого двухвходового элемента ИЛИ в каждой строке матрицы подается значение логического «0», выход поисковой ячейки, расположенной в последней строке матрицы, соединен с третьим входом j-го триггера позиции, на третий вход каждой поисковой ячейки, расположенной в первой строке матрицы, подано значение логической «1», первый вход блока поиска составного образца в анализируемой последовательности соединен соответственно с первыми входами n регистров для хранения кодов символов составного образца в анализируемой последовательности, а также с первыми входами m регистров для хранения кодов символов текста и первыми входами к триггеров позиций, второй вход «Запись строк» блока поиска составного образца в анализируемой последовательности соединен со входом элемента задержки и со вторыми входами n регистров для хранения кодов символов составного образца в анализируемой последовательности и вторыми входами m регистров для хранения кодов символов текста соответственно, выход элемента задержки соединен со вторыми входами k триггеров позиций, выходы которых образуют информационный k-разрядный выход блока поиска составного образца в анализируемой последовательности, третий вход блока матричного поиска состоит из n групп по p разрядов каждая группа, кодирующих символы составного образца в анализируемой последовательности, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход i-ого регистра для хранения кода символа составного образца в анализируемой последовательности, четвертый вход блока поиска составного образца в анализируемой последовательности состоит из m групп разрядов по p разрядов каждая группа, кодирующих символы текста, причем j-ая группа разрядов (j=1-m) подается на третий p-разрядный вход j-ого регистра для хранения кода символов текста, каждая двухвходовая схема сравнения на равенство в составе поисковой ячейки состоит из p-входового элемента И, а также из p двухвходовых элементов суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-ой p-разрядной группы третьего входа блока поиска составного образца в анализируемой последовательности, а на вторые входы двухвходовых элементов суммы по модулю два с инверсией - соответствующий разряд из j-ой p-разрядной группы четвертого входа блока поиска составного образца в анализируемой последовательности, выходы всех двухвходовых элементов суммы по модулю два с инверсией соединены с p-входовым элементом И, выход которого является одноразрядным выходом двухвходовой схемы сравнения на равенство.