Устройство для параллельного поиска вхождений и пересечений слов

Устройство для параллельного поиска вхождений и пересечений слов

Иллюстрации

Показать все

Реферат

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

Пусть заданы линейные конструктивные объекты x - образец длиной n символов и y - текст длиной m символов, составленные как цепочки символов конечного алфавита, где n>0, m>0 и n≤m. Требуется найти позиции всех вхождений x в y (далее условимся называть вхождение), т.е. определить все значения i, при которых у(i, i+n-1)=x(1, n), где 1≤i≤k, k=m-n+1. Также необходимо найти позиции всех пересечений собственного начала образца x с собственным окончанием текста у (далее условимся называть «пересечение 1»), т.е. определить все такие i, при которых y(i, m)=x(1, m-i+1), где k+1≤i<m, k=m-n+1, и необходимо найти позиции всех пересечений собственного окончания образца x с собственным началом текста y (далее условимся называть «пересечение 2»), т.е. определить все такие i, при которых y(1, i)=x(n-i+1, n), где 1≤i<n. Таким образом, в обобщенной задаче требуется найти все вхождения и все указанные пересечения.

Обработка данных и знаний в системах символьных вычислений основана не только на операциях поиска вхождений, но и на нахождении позиций «пересечений 1» и «пересечений 2». При обнаружении вхождений образца в обрабатываемом тексте необходимо выполнять множественные отступы (возвраты) в пространстве как образца, так и текста. Множественные отступы при поиске вхождений и пересечений образца связаны с выполнением непродуктивных шагов сопоставления и приводят к непродуктивным затратам времени. При реализации технического решения необходимо так организовать поиск позиций вхождений, «пересечений 1» и «пересечений 2», чтобы исключить необходимость возвратных отступов при обнаружении вхождений и этим повысить быстродействие работы на операциях поиска.

Известен алгоритм поиска СДВИГ-И, позволяющий последовательно отыскивать все вхождения образца в тексте. Суть алгоритма состоит в построении и обработке характеристических векторов. Недостатком данного алгоритма является последовательная обработка m векторов-столбцов, что приводит к избыточным затратам времени за счет m-кратного обращения к памяти символов текста для вычисления текущего вектора-столбца.

Также известно устройство поиска произвольных вхождений (патент № RU 2202823 С2, МКП G06F 17/30). Недостатком этого устройства является последовательный способ обработки текста и образца с отступами при обработке частичных вхождений.

Наиболее близким устройством к заявляемому является устройство для параллельного поиска и обработки данных, состоящее из двух блоков хранения и сравнения ассоциативных признаков, блока памяти логических векторов, операционного блока и блока матричного поиска (патент № RU 72771 U1, МКП G06F 12/00), выполняющее параллельную обработку совокупности характеристических векторов, объединенных в двумерную матрицу поиска.

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

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

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

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

Устройство для параллельного поиска вхождений и пересечений слов (фиг.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₂, третьим 5₃ и четвертым 5₄ выходом устройства. При этом второй управляющий вход блока 4 соединен со вторым выходом операционного блока 3.

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

Характеристическая матрица поисковых ячеек 34₁₁-34_nm размером m*n ячеек имеет форму прямоугольника, что обеспечивает направление поиска по всем диагоналям, проходящим через ячейки следующим образом:

l-я (l=1…n-1) диагональ, по которой происходит поиск «пересечений 1», проходит через l поисковых ячеек 34_ij, где i=l…1, j=m…m-l+1;

f-я (f=n…m) диагональ, по которой происходит поиск вхождений, проходит через n поисковых ячеек 34_ij, где i=n…1, j=m-f+n…m-f+1;

g-я (g=m+1…m+n-l) диагональ, по которой происходит поиск «пересечений 2», проходит через n+m-g поисковых ячеек 34_ij, где i=n…g-m+1, j=g-n+1…m.

Первые p-разрядные входы m поисковых ячеек i-ой строки характеристической матрицы (i=1…n) соединены с p-разрядным выходом регистра 32_i. Выход p-разрядного регистра 33_j (j=1…m) соединен со вторыми p-разрядными входами всех поисковых ячеек, входящих в j-ый столбец матрицы. Выход каждой поисковой ячейки 34_ij, кроме i=1, j=1…n (верхняя строка характеристической матрицы), кроме i=2…m, j=1 (левый столбец характеристической матрицы), соединен с третьим входом поисковой ячейки 34_i-1j-1. Выход поисковой ячейки 34_ij (i=2…m, j=1), расположенной в левом столбце характеристической матрицы, соединен с информационным входом 3 триггера 41_j-i позиции «пересечения 2», выход поисковой ячейки 34_ij (i=1, j=1…k), расположенной в верхней строке характеристической матрицы, соединен с информационным входом 3 триггера 37_j позиции вхождения, выход поисковой ячейки 34_ij (i=1, j=k+1_...m), соединен с информационным входом 3 триггера 40_j-k позиции «пересечения 1», третий вход каждой поисковой ячейки, расположенной в нижней n-ой строке матрицы и в правом m-ом столбце матрицы, предназначен для подачи значения логической «1», задавая тем самым начальное значение для поиска по соответствующей диагонали от нижней строки характеристической матрицы к ее верхней строке.

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

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

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

Пусть устройство выполняет режим «Операция» с кодом операции «ПВП». На вход 7₁ «Начальная установка» блока 4 матричного поиска вхождений и пересечений слов подается импульсный сигнал начальной установки, который сбрасывает в нулевое состояние k триггеров 37 позиций вхождения, n-1 триггеров 41 позиций «пересечения 2», n-1 триггеров 40 позиций «пересечения 1» по их входу 1, n регистров 32 по их входу 1 и m регистров 33 по их входу 1. После окончания действия сигнала начальной установки на второй вход «Запись строк» блока 4 матричного поиска вхождений и пересечений слов подается импульсный сигнал от операционного блока. Данный импульсный сигнал по входу «Запись строк» блока 4 матричного поиска вхождений и пересечений слов подается соответственно на вторые входы разрешения записи n регистров 32 кодов символов образца и на вторые входы разрешения записи m регистров 33 кодов символов текста, обеспечивая тем самым запись n символов образца и m символов текста в параллельном коде с входов 4₃ и 4₄ устройства соответственно. Также импульсный сигнал по входу «Запись строк» блока 4 матричного поиска вхождений и пересечений слов через элемент 31 задержки подается соответственно на вторые входы разрешения записи k триггеров 37 позиций вхождения, n-1 триггеров 41 позиций «пересечения 2», n-1 триггеров 40 позиций «пересечения 1». Элемент 31 задержки, выполненный в виде n пар инверторов, необходим для завершения процессов параллельного поиска вхождений и пересечений по диагоналям характеристической матрицы, состоящей из поисковых ячеек 34₁₁-34_nm.

Поиск начинается с ячеек нижней строки и правого столбца характеристической матрицы. Начальные m-битовый и n-битовый характеристические векторы, равные соответственно подаются соответственно на третьи входы поисковых ячеек n-ной (нижней) строки матрицы и на третьи входы поисковых ячеек m-ного (правого) столбца характеристической матрицы, которые соединены с входом логической «1», определяя тем самым направление параллельного поиска по всем диагоналям характеристической матрицы от поисковых ячеек нижней строки и правого столбца к поисковым ячейкам верхней строки и левого столбца характеристической матрицы включительно. Время параллельного поиска вхождений не зависит от количества диагоналей, а определяется величиной T=τ_комп+nτ_и, где τ_и - время задержки в элементе 36 И, τ_комп - время задержки в схеме сравнения 35. По завершении процессов поиска импульсный сигнал с выхода элемента 31 задержки через время T'=n2τ_инв (2τ_инв - время задержки на паре инверторов) записывает k-битовый результат поиска начала вхождений в триггеры 37₁-37_k позиций вхождения, n-1-битовый результат поиска «пересечения 2» в триггеры 41₁…41_n-1, n-1-битовый результат поиска «пересечения 1» в триггеры 40₁…40_n-1. Выходы триггеров 37₁…37_k позиций вхождения являются k-разрядным выходом блока 4 матричного поиска вхождений и пересечений слов и образуют первый выход устройства 5₂, n-1-разрядные выходы триггеров 41₁-41_n-1 позиций «пересечения 2» и n-1-разрядные выходы триггеров 40₁…40_n-1 позиций «пересечения 1» образуют второй и третий выходы устройства 5₃ и 5₄ соответственно. Наличие логических «1» в разряде информационного выхода 5₂ указывает на позиции вхождений образца в текст. Наличие логических «1» разряде информационного выхода 5₃ указывает позицию «пересечения 2» в тексте. Наличие логических «1» в разряде информационного выхода 5₄ указывает позицию «пересечения 1» в тексте. На фиг.4 (в) проиллюстрирована интерпретация результатов обработки характеристической матрицы.

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

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

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

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