СПОСОБ И УСТРОЙСТВО ПОИСКА СОСТАВНОГО ОБРАЗЦА В ПОСЛЕДОВАТЕЛЬНОСТИ

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 регистров для хранения кодов символов текста и первыми входами 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-входовым элементом и, выход которого является одноразрядным выходом двухвходовой схемы сравнения на равенство.