Способ и матричное устройство параллельно-конвейерного поиска по образцу Российский патент 2023 года по МПК G06F12/00 

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

Пусть заданы одномерные объекты (слова, строки): O - образец длиной n символов и S - текст длиной f символов, составленные как цепочки символов из конечного алфавита, где n>0, f>0 и n<f.

Требуется найти позиции всех полных вхождений образца O в текст S (далее условимся называть вхождения по образцу), т.е. определить все значения позиций i, при которых S(i, i+n–1) = O(1, n) где 1≤i≤r, r=f–n+1.

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

S= f₁⋅f₂ ⋅ …⋅ f_q

где «⋅» - операция конкатенации подстрок, f_i – i-я подстрока из S, i=1-q.

Поиск реализуется за q итераций, на каждой итерации реализуется параллельный поиск по текущей подстроке из S длиной m символов с учетом предыдущих положительных сопоставлений символов образца O и предыдущей подстроки из S. Эти предыдущие положительные сопоставления задают частичные вхождения образца O в подстроке текста S и понимаются как текущие граничные значения, необходимые для поиска на следующей итерации. Конвейеризация достигается за счет совместной обработки текущей подстроки из текста S и граничных результатов от предыдущей итерации поиска.

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

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

Недостаток данного способа – последовательная обработка m-разрядных двоичных векторов, описывающих частичные вхождения образца в тексте.

Известен способ поиска по образцу [Максимов, В. Алгоритмы поиска, или как искать неизвестно что / В. Максимов // Монитор. 1995. №6 - С. 10-16], основанный на последовательном вычислении и обработке двоичных векторов сравнения текущего символа текста и n символов образца. Разрядность характеристического вектора равна n бит, в котором логическая «1» в j-й позиции характеризует вхождение текущего символа текста в образце. Алгоритмизация данного способа сводится к циклической обработке предыдущего двоичного вектора и текущего двоичного вектора на основе логической операции «косая конъюнкция». Предыдущий двоичный вектор задает односимвольные вхождения текста в образец, что позволяет последовательно выделять и аккумулировать префикс образца до его полного вхождения по символам текста.

Недостаток данного способа – последовательная обработка n-разрядных двоичных векторов, описывающих вхождение текущего символа текста в образце.

Наиболее близким является подход к параллельному поиску вхождений и пересечений слов [Патент 2430408 РФ, МПК G06F17/30. опубл. 27.09.2011, Бюл. №27], состоящий в построении прямоугольной двоичной матрицы сравнений символов образца и текста размером n × m поисковых ячеек. Алгоритмизация данного подхода сводится к параллельной обработке k (k=m-n+1) диагоналей матрицы, проходящих через все строки, и формированию результирующего k-разрядного вектора вхождений.

Недостаток данного способа заключается в том, что позиции частичных вхождений в ячейках прямоугольной двоичной матрицы с индексами {(1,k+1)…(1,m), (2,k+2)…(2,m), …(n-1,m)} не используются как граничные значения от предыдущей итерации поиска при обработке текущей подстроки текста, что не позволяет вести параллельно-конвейерный поиск по подстрокам текста.

Сущность предлагаемого способа поиска по образцу заключается в дополнении прямоугольной двоичной матрицы сравнений треугольной двоичной матрицей со сторонами (n-1)×(n-1), в которой будут храниться частичные вхождения - вхождения символов префикса образца в тексте. Разбиение текста на подстроки длиной по m символов позволит на текущем шаге к поиску по k=m-n+1 диагоналям дополнительно вести поиск по n-1 диагоналям, расширенным всеми ячейками треугольной двоичной матрицы с индексами {(1,1)…(1,n-1), (2,n-1)…(2,n-1, …(n-1,n-1)}, которые хранят вхождения символов префикса образца в предыдущей подстроке текста.

Предлагаемый способ параллельно-конвейерного поиска основан на разбиении исходного текста на подстроки по m символов и выполнении поиска по образцу длиной n символов по этим подстрокам с учетом предыдущих (граничных) значений, отличающийся параллельными парными сравнениями символов образца и символов текущей подстроки. Поиск по образцу в пределах текущей подстроки реализуется параллельной проверкой логических «1» по всем элементам k диагоналей прямоугольной двоичной матрицы сравнений и по элементам n-1 диагоналей, формируемых из элементов треугольной двоичной матрицы и элементов прямоугольной двоичной матрицы сравнений, взятых из ее нижней левой части. Проверка логических «1» в ячейках каждой диагонали осуществляется на основе последовательности логических операций «косая конъюнкция». Переход к следующей итерации поиска реализуется записью текущих значений из верхней правой части прямоугольной двоичной матрицы сравнений в треугольную двоичную матрицу, и дозагрузкой следующей подстроки текста.

Известно устройство [А.с. 1485254 СССР, МКИ G06 F 12/00, опубл. 07.06.89, Бюл. №21] для адресации по содержанию блока памяти, состоящее из двух блоков ассоциативных признаков, блока памяти логических векторов и операционного блока. Работа устройства основана на обработке элементов двух множеств (признаков и объектов) с помощью логических векторов-строк или векторов столбцов. Вектор-строка является характеристическим вектором, описывающим определенное подмножество признаков, принадлежащих множеству объектов. В качестве элементарных операций над векторами реализованы логические операции умножения, сложения, суммы по модулю 2, инверсии и т.д., а также операции идентификации объекта.

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

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

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

Устройством-прототипом является устройство для параллельного поиска вхождений и пересечений слов [Патент 2430408 РФ, МПК G06F17/30, опубл. 27.09.2011, Бюл. №27], состоящее из двух блоков ассоциативных признаков, блока памяти логических векторов, операционного блока и блока матричного поиска. Данное устройство в режиме «Операция» может выполнять поиск полных и частичных вхождений образца длиной n символов в тексте длиной m символов (операция «Поиск вхождений и пересечений»). Блок матричного поиска имеет прямоугольную форму и содержит k диагоналей, проходящих через все строки прямоугольной матрицы, и 2(n-1) диагоналей, проходящих через (n-1), (n-2), … 2, 1 строки матрицы в ее левой нижней и правой верхней частях. Все элементы прямоугольной матрицы поисковых ячеек являются результатом параллельного сравнения каждого символов образца с каждым символов текста с учетом прямоугольной формы матрицы. Поиск полных вхождений образца проводится по k диагоналям прямоугольной матрицы (k=m-n+1). Поиск частичных вхождений образца проводится по n-1 диагоналям, построенным из ячеек прямоугольной матрицы в ее нижней левой и верхней правой частях.

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

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

Решение технической задачи достигается тем, что в матричное устройство параллельно-конвейерного поиска по образцу (далее - устройство), содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов, операционный блок и блок матричного поиска, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым информационными входами устройства, а выходы блоков хранения и сравнения ассоциативных признаков соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы задания режимов первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами задания режимов устройства, а четвертый, пятый, шестой входы задания режимов устройства соответственно соединены с тремя входами кодов операций операционного блока, первый выход которого является первым выходом устройства, первый вход начальной установки устройства подключен к входу начальной установки операционного блока и первому входу блока матричного поиска, второй вход начальной установки - к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, второй выход которого («Запись строк») подключен ко второму входу блока матричного поиска, два информационных входа которого являются внешними третьим и четвертым входами устройства, первый и второй выходы блока матричного поиска являются вторым и третьим выходами устройства соответственно, содержащее в составе блока матричного поиска n p-разрядных регистров хранения символов образца и m p-разрядных регистров хранения символов текста, при этом каждый регистр кода символа образца и каждый регистр кода символа текста имеют соответственно по три входа (первый и второй управляющие входы и третий информационный p-разрядный вход) и один p-разрядный выход, входы регистров хранения символов образца образуют третий p×n-разрядный информационный вход устройства, i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход i-го регистра кода символа образца, входы регистров хранения символов текста образуют четвёртый p×m-разрядный информационный вход устройства, j-ая группа разрядов (j=1-m) подается на третий p-разрядный вход j-го регистра кода символа текста, первый вход начальной установки устройства подключен к первым входам n регистров хранения символов образца и первым входам m регистров хранения символов текста, вход «Запись строк» подключен ко вторым входам n регистров хранения символов образца и вторым входам m регистров хранения символов текста, а также содержащее в составе блока матричного поиска k триггеров позиций полных вхождений, выходы триггеров позиций полных вхождений являются k-разрядным выходом блока матричного поиска и образуют второй выход устройства, n-1 триггеров позиций граничных вхождений, выходы триггеров позиций граничных вхождений являются (n-1)-разрядным выходом блока матричного поиска и образуют третий выход устройства, k триггеров позиций полных вхождений количеством и n-1 триггеров позиций граничных вхождений имеют по три входа каждый и один выход, отличающееся тем, что в устройство введены треугольная матрица граничных ячеек количеством (n⋅(n+1))/2 ячеек, присоединенная слева к прямоугольной матрице поисковых ячеек и располагаемая в строках 1-я, 2-я, … (n-1)-я в количестве граничных ячеек (n-1), (n-2), …2, 1 соответственно, а также пять внешних входов: третий вход начальной установки, являющийся пятым входом блока матричного поиска, вход тактовых импульсов «ТИ», являющийся шестым входом блока матричного поиска, однобитовый управляющий вход «ЗП гран. знач.» для перезаписи граничных значений из поисковых ячеек прямоугольной матрицы в граничные ячейки, являющийся седьмым входом блока матричного поиска, однобитовый управляющий вход «Запись результатов» для записи результатов поиска вхождений в триггеры позиций полных вхождений и в триггеры позиций граничных вхождений, являющийся восьмым входом блока матричного поиска, однобитовый управляющий вход «Запись сравнений» для записи результатов сравнения i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в матрицу поисковых ячеек блока матричного поиска, являющийся девятым входом блока матричного поиска; в блок матричного поиска введены первый, второй, третий двухвходовые элементы И, первым и вторым входами первого двухвходового элемента И являются управляющий вход «Запись сравнений» и вход ТИ соответственно, а его выход обозначен как «Упр.1», первым и вторым входами второго двухвходового элемента И являются управляющий вход «Запись результатов» и вход ТИ соответственно, а его выход обозначен как «Упр.2», первым и вторым входами третьего двухвходового элемента И являются управляющий вход «ЗП гранич. знач.» и вход ТИ соответственно, а его выход обозначен как «Упр.3»; третий вход начальной установки устройства подключен к первым входам k триггеров позиций полных вхождений и к первым входам n-1 триггеров позиций граничных вхождений, вторые входы k триггеров позиций полных вхождений и n-1 триггеров позиций граничных вхождений подключены к выходу «Упр.2» второго двухвходового элемента И; в составе блока матричного поиска построена прямоугольная матрица поисковых ячеек количеством n×m, каждая ячейка имеет 6 входов и 1 выход, в состав поисковой ячейки входят двухвходовая схема сравнения на равенство p-разрядных кодов i-го символа образца (i=1…n) и j-го символа текста (j=1…m), первый D-триггер с тремя входами, двухвходовой элемент И, второй D-триггер с тремя входами, причем первый вход поисковой ячейки является первым входом схемы сравнения на равенство, второй вход поисковой ячейки является вторым входом схемы сравнения на равенство, третий вход поисковой ячейки подключен к второму входу двухвходового элемента И, четвертый вход поисковой ячейки подан на R-входы сброса первого и второго D-триггеров, пятый вход поисковой ячейки подан на C-вход синхронизации первого D-триггера, шестой вход поисковой ячейки подключен к C-входу синхронизации второго D-триггера; выход схемы сравнения на равенство соединен с D-входом первого D-триггера, выход которого подключен к первому входу двухвходового элемента И, выход которого подключен к D-входу второго D-триггера, выход которого является выходом поисковой ячейки; каждая двухвходовая схема сравнения на равенство в составе поисковой ячейки состоит из p двухвходовых элементов суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-ой р-разрядной группы третьего входа блока матричного поиска, а на вторые входы двухвходовых элементов суммы по модулю два с инверсией - соответствующий разряд из j-ой р-разрядной группы четвертого входа блока матричного поиска, выходы всех двухвходовых элементов суммы по модулю два с инверсией соединены с p-входовым элементом И, выход которого является выходом двухвходовой схемы сравнения на равенство; каждая граничная ячейка в составе треугольной матрицы, имеет 5 входов и 1 выход, в состав граничной ячейки входят третий D-триггер с тремя входами, двухвходовой элемент И, четвертый D-триггер с тремя входами, причем первый вход граничной ячейки подан на R-входы сброса третьего и четвертого D-триггеров, второй вход граничной ячейки подан на C-вход синхронизации третьего D-триггера, третий вход граничной ячейки соединен с выходом поисковой ячейки, отстоящей на k ячеек вправо в соответствующей строке прямоугольной матрицы и подан на D-вход третьего D-триггера, выход которого соединен с первым входом двухвходового элемента И, четвертый вход граничной ячейки подан на С-вход синхронизации четвертого D-триггера, пятый вход граничной ячейки соединен со вторым входом двухвходового элемента И, выход которого соединен с D-входом четвертого D-триггера, выход которого является выходом граничной ячейки; поисковые ячейки количеством n × m образуют прямоугольную матрицу, в которой первые 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-го триггера позиции полного вхождения, третьи входы поисковых ячеек n-й строки и m-го столбца соединены с входом логической «1» для организации поиска по всем диагоналям в составе обеих матриц, выход (i, j)-ой поисковой ячейки (i=1… n-1, j=k+i …m) соединен с третьим входом (i,t) граничной ячейки (i=1 …n-1, t=i…n-1); выход (i, j)-й поисковой ячейки (i=2 … n, j=1), т.е. ячейки первого столбца прямоугольной матрицы, соединен с пятым входом (i-1, n-1)-ой граничной ячейки, т.е. ячейки в последнем столбце треугольной матрицы, четвертые входы поисковых ячеек подключены к первому входу начальной установки, пятые входы поисковых ячеек подключены к выходу «Упр.1» первого двухвходового элемента И, шестые входы поисковых ячеек подключены к входу тактовых импульсов ТИ; граничные ячейки количеством (n⋅(n+1))/2 образуют треугольную матрицу, в которой первые входы граничных ячеек подключены к первому входу начальной установки, вторые входы граничных ячеек подключены к выходу «Упр.3» третьего двухвходового элемента И, третьи входы (i,t) граничных ячеек (i=1 …n-1, t=i …n-1) подключены к выходам (i, j)-ых поисковых ячеек (i=1… n-1, j=k+i …m), четвертые входы граничных ячеек подключены к входу тактовых импульсов ТИ, пятый вход (i, j)-й граничной ячейки (i=1 …n-1, j=n-1) соединен с выходом поисковой ячейки (i+1,1), пятый вход (i, j)-й граничной ячейки (i=1…n-1, j=i…n-2) соединен с выходом граничной ячейки (i+1, j+1), выход (i, j)-й граничной ячейки (i=1, j=1…n-1) соединен с третьим входом j-го триггера позиции частичного вхождения.

Сущность изобретения поясняется чертежами, где на фиг. 1 представлена структурная схема матричного устройства параллельно-конвейерного поиска по образцу, на фиг. 2 – функциональная схема блока матричного поиска, на фиг. 3 – функциональная схема поисковой ячейки прямоугольной матрицы, на фиг. 4 – функциональная схема граничной ячейки треугольной матрицы, на фиг. 5– функциональная схема сравнения на равенство, на фиг. 6 - пример параллельно-конвейерного поиска.

Устройство содержит блоки 1₁ и 1₂ хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, блок 4 матричного поиска, информационные входы устройства 4₁, 4₂, 4₃ и 4₄, первый, второй, третий информационные выходы устройства 5₁, 5₂ , 5₃ соответственно, тринадцать управляющих однобитовых входов: входы 6₁-6₆ задания режима работы, входы 7₁, 7₂, 7₃ начальной установки, входы «Запись сравнений», «Запись результатов», «ЗП Гранич. знач.», вход тактовых импульсов ТИ.

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

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

Блок 4 матричного поиска содержит n регистров 32₁-32_n для хранения кодов символов образца, m регистров 33₁–33_m для хранения кодов символов подстроки текста, причем регистр 32_i (i=1-n) и регистр 33_j (j=1-m) содержат первый и второй управляющие входы, третий p-разрядный информационный вход и один p-разрядный выход соответственно. Блок 4 матричного поиска также содержит прямоугольную матрицу поисковых ячеек 34₁₁–34_nm, k триггеров 37 позиций полных вхождений, n-1 триггеров 41 позиций частичных вхождений, треугольную матрицу граничных ячеек {44₁₁–44_1n-1, 44₂₂–44_2n-1 … 44_n-1n-1}, второй двухвходовой элемент 42 И, на первый и второй входы которого поданы «Запись результатов» и вход ТИ соответственно, первый двухвходовой элемент 43 И, на первый и второй входы которого поданы «Запись сравнений» и вход ТИ соответственно, третий двухвходовой элемент 45 И, на первый и второй входы которого поданы «ЗП гранич. знач.» и вход ТИ соответственно, выход «Упр.1» элемента 42 И подключен к пятым входам поисковых ячеек 34₁₁–34_nm, выход «Упр.2» элемента 43 И подключен ко вторым входам триггеров 37₁ -37_k, 41₁ -41_n-1, выход «Упр.3» элемента 45 И подключен ко вторым входом граничных ячеек {44₁₁–44_1n-1, 44₂₂–44_2n-1 … 44_n-1n-1}.

Первые и вторые входы n регистров 32 для хранения кодов символов образца, а также первые и вторые входы m регистров 33 для хранения кодов символов подстроки текста соединены соответственно с входом начальной установки 7₁ и управляющим входом «Запись строк» блока 4 матричного поиска, информационный вход 4₃ которого разрядностью p×n бит предназначен для параллельной записи образца в регистры 32₁–32_n и состоит из n групп разрядов по p разрядов каждая группа, кодирующих символы образца, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход регистра 32_i (i=1-n), информационный вход 4₄ блока 4 матричного поиска разрядностью p×m бит предназначен для параллельной записи подстроки текста в регистры 33₁-33_m и состоит из m групп разрядов по p разрядов каждая группа, кодирующих символы текста, причем j-ая группа разрядов (j=1-m) подается на третий p-разрядный вход регистра 33_j (j=1-m).

Блок матричного поиска содержит матрицу поисковых ячеек 34₁₁–34_nm, каждая поисковая ячейка 34_ij имеет шесть входов и один выход, в состав поисковой ячейки 34_ij входят двухвходовая схема 35 сравнения на равенство p-разрядных кодов i-го символа образца (i=1…n) и j-го символа текста (j=1…m), первый D-триггер 40₁ с тремя входами, двухвходовой элемент И 36, второй D-триггер 40₂ с тремя входами, причем первый вход поисковой ячейки 34_ij является первым входом схемы 35 сравнения на равенство, второй вход поисковой ячейки 34_ij является вторым входом схемы 35 сравнения на равенство, третий вход поисковой ячейки 34_ij подключен ко второму входу двухвходового элемента 36 И, четвертый вход поисковой ячейки 34_ij подан на R-входы сброса первого D-триггера 40₁ и второго D-триггера 40₂, пятый вход поисковой ячейки 34_ij подан на C-вход синхронизации первого D-триггера 40₁, шестой вход поисковой ячейки 34_ij подключен к С-входу синхронизации второго D-триггера 40₂ , выход которого является выходом поисковой ячейки 34_ij. Выход схемы 35 сравнения на равенство соединен с D-входом первого D-триггера 40₁, выход которого подключен к первому входу двухвходового элемента И 36, выход которого подключен к D-входу второго D-триггера 40₂; схема 35 сравнения на равенство состоит из p двухвходовых элементов 38₁–38_p суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-ой р-разрядной группы информационного входа 4₃ блока 4 матричного поиска, а на вторые входы двухвходовых элементов 38₁–38_p суммы по модулю два с инверсией - соответствующий разряд из j-ой р-разрядной группы информационного входа 4₄ блока 4 матричного поиска, все выходы двухвходовых элементов 38₁-38_p суммы по модулю два с инверсией в составе двухвходовой схемы 35_ij сравнения на равенство соединены с p-входовым элементом 39 И, выход которого является выходом двухвходовой схемы 35_ij сравнения на равенство.

Прямоугольная матрица поисковых ячеек 34₁₁–34_nm имеет k=m-n+1 диагоналей, проходящих через все строки матрицы, при этом первый вход поисковой ячейки 34_ij соединен с выходом i-го регистра 32_i хранения символа образца (i=1 …n), второй вход поисковой ячейки 34_ij соединен с выходом с выходом j-го регистра 33_ij хранения символа текста (j=1 …m). Выход поисковой ячейки 34_ij (i=2 …n, j=2 …m) соединен c третьим входом поисковой ячейки 34_i-1j-1, выход поисковой ячейки 34_ij (i=1, j=1…k) подключен к третьему входу триггера 37_j позиции полного вхождения. Третьи входы поисковых ячеек n-й строки и m-го столбца соединены с входом логической «1» для организации поиска по всем диагоналям в составе обеих матриц. Выходы поисковых ячеек 34_ij (i=1… n-1, j=k+i …m) соединены с третьими входами граничных ячеек 44_it (i=1 …n-1, t=i … n-1), выходы поисковых ячеек 34_ij (i=2 … n, j=1), т.е. первого столбца прямоугольной матрицы, подключены к пятым входам граничных ячеек 44_i-1n-1, т.е. к ячейкам последнего столбца треугольной матрицы. Четвертые входы всех поисковых ячеек подключены к первому входу начальной установки 7₁, пятые входы всех поисковых ячеек подключены к выходу «Упр.1» первого двухвходового элемента И, шестые входы всех поисковых ячеек подключены к входу тактовых импульсов ТИ.

Блок матричного поиска также содержит треугольную матрицу граничных ячеек {44₁₁–44_1n-1, 44₂₂–44_2n-1 … 44_n-1n-1}. Каждая граничная ячейка 44_ij имеет пять входов и один выход. В состав граничной ячейки 44_ij входят третий D-триггер 46₁ с тремя входами, двухвходовой элемент 47 И, четвертый D-триггер 46₂ с тремя входами, причем первый вход граничной ячейки 44_ij подан на R-входы сброса третьего D-триггера 46₁ и четвертого D-триггера 46₂, второй вход граничной ячейки 44_ij подан на C-вход синхронизации третьего D-триггера 46₁, третий вход граничной ячейки 44_ij подан на D-вход третьего D-триггера 46₁, выход которого соединен с первым входом двухвходового элемента И 47, четвертый вход граничной ячейки 44_ij подан на С-вход синхронизации четвертого D-триггера 46₂, пятый вход граничной ячейки 44_ij соединен со вторым входом двухвходового элемента И 47, выход которого соединен с D-входом четвертого D-триггера 46₂, выход которого является выходом граничной ячейки 44_ij.

Граничные ячейки количеством (n⋅(n+1))/2 образуют треугольную матрицу ячеек {44₁₁–44_1n-1, 44₂₂–44_2n-1 … 44_n-1n-1}, в которой первые входы граничных ячеек 44_ij подключены к первому входу начальной установки 7₁, вторые входы граничных ячеек 44_ij подключены к выходу «Упр.3» третьего двухвходового элемента И, третьи входы (i,t) граничных ячеек 44_it (i=1 …n-1, t=i …n-1) подключены к выходам поисковых ячеек 34_ij (i=1… n-1, j=k+i …m), что необходимо для перезаписи значений для следующей итерации поиска, четвертые входы граничных ячеек 44_ij подключены к входу тактовых импульсов ТИ, пятые входы граничных ячеек 44_ij (i=1 …n-1, j=n-1), т.е. граничных ячеек последнего столбца треугольной матрицы, соединены с выходами поисковых ячеек 44_i+11, т.е. поисковых ячеек первого столбца прямоугольной матрицы, пятые входы граничных ячеек 44_ij (i=1…n-1, j=i…n-2) соединены с выходами граничных ячеек 44_i+1j+1, выходы граничных ячеек 44_ij (i=1, j=1…n-1) соединены с третьими входами триггеров 41₁ – 41_n-1 позиций частичных вхождений.

Триггеры 37₁–37_k позиций полных вхождений хранят результат поиска вхождений в виде k-разрядного кода, в котором значениями логических «1» отмечены позиции вхождения образца в текущий фрагмент текст. Триггер 37_v позиции (v=1-k) полного вхождения содержит три входа (первый и второй управляющие, третий одноразрядный информационный вход) и один выход. Третий вход начальной установки 7₃ соединен с первыми входами k триггеров 37 позиций полных вхождений. Выход «Упр.2» второго двухвходового элемента 42 И соединен со вторыми входами триггеров 37₁–37_k позиций полных вхождений. Третьи входы триггеров 37₁–37_k позиций полных вхождений соединены с выходами поисковых ячеек 34₁₁–34_1k. Выходы триггеров 37₁-37_k позиций полных вхождений являются k-разрядным выходом блока 4 матричного поиска и образуют второй выход устройства 5₂.

Триггеры 41₁–41_n-1 позиций частичных вхождений хранят результат поиска вхождений в виде n-1-разрядного кода, в котором значениями логических «1» отмечены позиции вхождения образца с учетом граничных значений от предыдущего подстроки текста. Триггер 41_w позиции (w=1…n-1) частичного вхождения содержит три входа (первый и второй управляющие, третий одноразрядный информационный вход) и один выход. Третий вход начальной установки 7₃ соединен с первыми входами n-1 триггеров 41 позиций частичных вхождений. Выход «Упр.2» второго двухвходового элемента 42 И соединен со вторыми входами триггеров 41₁–41_n-1 позиций частичных вхождений. Третьи входы триггеров 41₁–41_n-1 позиций частичных вхождений соединены с выходами граничных ячеек 44₁₁–44_1n-1. Выходы триггеров 41₁–41_n-1 позиций частичных вхождений являются n-1-разрядным выходом блока 4 матричного поиска и образуют третий выход устройства 5₃.

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

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

Пусть устройство выполняет режим «Операция» с кодом операции «ПВГ». На первый вход 7₁ «Начальная установка» операционного блока 4 матричного поиска подается импульсный сигнал начальной установки, который сбрасывает в нулевое состояние: n регистров 32 по их входу 1 и m регистров 33 по их входу 1, два D-триггера 40₁ и 40₂ в составе поисковых ячеек 34₁₁–34_nm, два D-триггера 46₁ и 46₂ в составе граничных ячеек {44₁₁–44_1n-1, 44₂₂–44_2n-1 … 44_n-1n-1}. На третий вход 7₃ начальной установки операционного блока 4 матричного поиска подается импульсный сигнал начальной установки, который сбрасывает в нулевое состояние: k триггеров 37 позиций полных вхождений по их входу 1, n-1 триггеров 41 позиций частичных вхождений по их входам 1 соответственно. После окончания действия сигнала начальной установки на вход 6₆ режима работы операционного блока 3 подается код операции «ПВГ», который обнаруживается операционным блоком 3 и на второй вход «Запись строк» блока 4 матричного поиска подается сигнал логической «1».

Данное значение по входу «Запись строк» блока 4 матричного поиска подается соответственно на вторые входы разрешения записи n регистров 32 для хранения кодов символов образца и на вторые входы разрешения записи m регистров 33 для хранения кодов символов текста, обеспечивая тем самым запись n символов образца и m символов подстроки текста в параллельном коде с информационных входов 4₃ и 4₄ устройства соответственно.

Сигнал по управляющему входу «Запись сравнений» совместно с сигналом по входу ТИ обеспечивают запись результатов сравнений n символов образца и m символов подстроки текста в первые D-триггера 40₁ поисковых ячеек 34₁₁–34_nm, образуя начальную прямоугольную матрицу поиска, представляющую собой двоичную матрицу параллельных сравнений ij-ых символов образца и подстроки текста (i=1…n, j=1…m). Выходы поисковых ячеек 34₁₁–34_nm, дополненные граничными ячейками {44₁₁–44_1n-1, 44₂₂–44_2n-1 … 44_n-1n-1} треугольной матрицы, образуют k+n-1 диагоналей.

Последовательность импульсов по входу ТИ, подаваемому на входы 6 поисковых ячеек и входы 4 граничных ячеек, обеспечивает вычисление позиций вхождения образца по ячейкам k+n-1 диагоналей, начиная от поисковых ячеек n-й строки и m-го столбца прямоугольной матрицы, на третьи входы которых подана логическая «1».

По сигналу на управляющем входе «Запись результатов» совестно с сигналом по входу ТИ обеспечивается запись результатов поиска в триггеры 37₁–37_k позиций полных вхождений и триггеры 41₁–41_n-1 позиций частичных вхождений.

Переход к следующей итерации поиска обеспечивается сбросом триггеров 37₁–37_k позиций полных вхождений и триггеров 41₁–41_n-1 позиций частичных вхождений по сигналу на третьем входе начальной установки 7₃ , а также перезаписью частичных вхождений из n⋅(n+1)/2 поисковых ячеек, расположенных в правой верхней части прямоугольной матрицы в граничные ячейки {44₁₁–44_1n-1, 44₂₂–44_2n-1 … 44_n-1n-1} треугольной матрицы по сигналу «ЗП гранич. знач.».

Следующая итерация поиска реализуется подачей на входы устройства 4₃ и 4₄ новых значений, которые записываются в регистры 32₁ - 32_n и 33₁ - 33_m. Далее в прямоугольной и треугольной матрицах реализуется поиск по k+n-1 диагоналям и фиксация результатов в триггерах 37₁–37_k и 41₁–41_n-1.

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

Изобретение относится к способу и устройству параллельно-конвейерного поиска по образцу. Технический результат заключается в повышении эффективности поиска по образцу в текстовых данных. Способ поиска по образцу заключается в дополнении прямоугольной двоичной матрицы сравнений треугольной двоичной матрицей со сторонами (n-1)×(n-1), в которой хранятся частичные вхождения - вхождения символов префикса образца в тексте. За счет выполнения разбиения текста на подстроки длиной по m символов обеспечивается возможность на текущем шаге к поиску по k=m-n+1 диагоналям выполнения дополнительного поиска по n-1 диагоналям, расширенным всеми ячейками треугольной двоичной матрицы с индексами {(1,1)…(1,n-1), (2,n-1)…(2,n-1, …(n-1,n-1)}, которые хранят вхождения символов префикса образца в предыдущей подстроке текста. 2 н.п. ф-лы, 6 ил.

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

2. Матричное устройство параллельно-конвейерного поиска по образцу, содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов, операционный блок и блок матричного поиска, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым информационными входами устройства, а выходы блоков хранения и сравнения ассоциативных признаков соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы задания режимов первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами задания режимов устройства, а четвертый, пятый, шестой входы задания режимов устройства соответственно соединены с тремя входами кодов операций операционного блока, первый выход которого является первым выходом устройства, первый вход начальной установки устройства подключен к входу начальной установки операционного блока и первому входу блока матричного поиска, второй вход начальной установки - к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, второй выход которого «Запись строк» подключен ко второму входу блока матричного поиска, два информационных входа которого являются внешними третьим и четвертым входами устройства, первый и второй выходы блока матричного поиска являются вторым и третьим выходами устройства соответственно, содержащее в составе блока матричного поиска n p-разрядных регистров хранения символов образца и m p-разрядных регистров хранения символов текста, при этом каждый регистр кода символа образца и каждый регистр кода символа текста имеют соответственно по три входа (первый и второй управляющие входы и третий информационный p-разрядный вход) и один p-разрядный выход, входы регистров хранения символов образца образуют третий p×n-разрядный информационный вход устройства, i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход i-го регистра кода символа образца, входы регистров хранения символов текста образуют четвёртый p×m-разрядный информационный вход устройства, j-ая группа разрядов (j=1-m) подается на третий p-разрядный вход j-го регистра кода символа текста, первый вход начальной установки устройства подключен к первым входам n регистров хранения символов образца и первым входам m регистров хранения символов текста, вход «Запись строк» подключен ко вторым входам n регистров хранения символов образца и вторым входам m регистров хранения символов текста, а также содержащее в составе блока матричного поиска k триггеров позиций полных вхождений, выходы триггеров позиций полных вхождений являются k-разрядным выходом блока матричного поиска и образуют второй выход устройства, n-1 триггеров позиций граничных вхождений, выходы триггеров позиций граничных вхождений являются (n-1)-разрядным выходом блока матричного поиска и образуют третий выход устройства, k триггеров позиций полных вхождений количеством и n-1 триггеров позиций граничных вхождений имеют по три входа каждый и один выход, отличающееся тем, что в устройство введены треугольная матрица граничных ячеек количеством (n⋅(n+1))/2 ячеек, присоединенная слева к прямоугольной матрице поисковых ячеек и располагаемая в строках 1-я, 2-я, … (n-1)-я в количестве граничных ячеек (n-1), (n-2), … 2, 1 соответственно, а также пять внешних входов: третий вход начальной установки, являющийся пятым входом блока матричного поиска, вход тактовых импульсов «ТИ», являющийся шестым входом блока матричного поиска, однобитовый управляющий вход «ЗП гран. знач.» для перезаписи граничных значений из поисковых ячеек прямоугольной матрицы в граничные ячейки, являющийся седьмым входом блока матричного поиска, однобитовый управляющий вход «Запись результатов» для записи результатов поиска вхождений в триггеры позиций полных вхождений и в триггеры позиций граничных вхождений, являющийся восьмым входом блока матричного поиска, однобитовый управляющий вход «Запись сравнений» для записи результатов сравнения i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в матрицу поисковых ячеек блока матричного поиска, являющийся девятым входом блока матричного поиска; в блок матричного поиска введены первый, второй, третий двухвходовые элементы И, первым и вторым входами первого двухвходового элемента И являются управляющий вход «Запись сравнений» и вход ТИ соответственно, а его выход обозначен как «Упр.1», первым и вторым входами второго двухвходового элемента И являются управляющий вход «Запись результатов» и вход ТИ соответственно, а его выход обозначен как «Упр.2», первым и вторым входами третьего двухвходового элемента И являются управляющий вход «ЗП гранич. знач.» и вход ТИ соответственно, а его выход обозначен как «Упр.3»; третий вход начальной установки устройства подключен к первым входам k триггеров позиций полных вхождений и к первым входам n-1 триггеров позиций граничных вхождений, вторые входы k триггеров позиций полных вхождений и n-1 триггеров позиций граничных вхождений подключены к выходу «Упр.2» второго двухвходового элемента И; в составе блока матричного поиска построена прямоугольная матрица поисковых ячеек количеством n×m, каждая ячейка имеет 6 входов и 1 выход, в состав поисковой ячейки входят двухвходовая схема сравнения на равенство p-разрядных кодов i-го символа образца (i=1…n) и j-го символа текста (j=1…m), первый D-триггер с тремя входами, двухвходовой элемент И, второй D-триггер с тремя входами, причем первый вход поисковой ячейки является первым входом схемы сравнения на равенство, второй вход поисковой ячейки является вторым входом схемы сравнения на равенство, третий вход поисковой ячейки подключен к второму входу двухвходового элемента И, четвертый вход поисковой ячейки подан на R-входы сброса первого и второго D-триггеров, пятый вход поисковой ячейки подан на C-вход синхронизации первого D-триггера, шестой вход поисковой ячейки подключен к C-входу синхронизации второго D-триггера; выход схемы сравнения на равенство соединен с D-входом первого D-триггера, выход которого подключен к первому входу двухвходового элемента И, выход которого подключен к D-входу второго D-триггера, выход которого является выходом поисковой ячейки; каждая двухвходовая схема сравнения на равенство в составе поисковой ячейки состоит из p двухвходовых элементов суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-ой р-разрядной группы третьего входа блока матричного поиска, а на вторые входы двухвходовых элементов суммы по модулю два с инверсией - соответствующий разряд из j-ой р-разрядной группы четвертого входа блока матричного поиска, выходы всех двухвходовых элементов суммы по модулю два с инверсией соединены с p-входовым элементом И, выход которого является выходом двухвходовой схемы сравнения на равенство; каждая граничная ячейка в составе треугольной матрицы, имеет 5 входов и 1 выход, в состав граничной ячейки входят третий D-триггер с тремя входами, двухвходовой элемент И, четвертый D-триггер с тремя входами, причем первый вход граничной ячейки подан на R-входы сброса третьего и четвертого D-триггеров, второй вход граничной ячейки подан на C-вход синхронизации третьего D-триггера, третий вход граничной ячейки соединен с выходом поисковой ячейки, отстоящей на k ячеек вправо в соответствующей строке прямоугольной матрицы и подан на D-вход третьего D-триггера, выход которого соединен с первым входом двухвходового элемента И, четвертый вход граничной ячейки подан на С-вход синхронизации четвертого D-триггера, пятый вход граничной ячейки соединен со вторым входом двухвходового элемента И, выход которого соединен с D-входом четвертого D-триггера, выход которого является выходом граничной ячейки; поисковые ячейки количеством n × m образуют прямоугольную матрицу, в которой первые 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-го триггера позиции полного вхождения, третьи входы поисковых ячеек n-й строки и m-го столбца соединены с входом логической «1» для организации поиска по всем диагоналям в составе обеих матриц, выход (i, j)-ой поисковой ячейки (i=1 … n-1, j=k+i … m) соединен с третьим входом (i, t) граничной ячейки (i=1 … n-1, t=i … n-1); выход (i, j)-й поисковой ячейки (i=2 … n, j=1), т.е. ячейки первого столбца прямоугольной матрицы, соединен с пятым входом (i-1, n-1)-ой граничной ячейки, т.е. ячейки в последнем столбце треугольной матрицы, четвертые входы поисковых ячеек подключены к первому входу начальной установки, пятые входы поисковых ячеек подключены к выходу «Упр.1» первого двухвходового элемента И, шестые входы поисковых ячеек подключены к входу тактовых импульсов ТИ; граничные ячейки количеством (n⋅(n+1))/2 образуют треугольную матрицу, в которой первые входы граничных ячеек подключены к первому входу начальной установки, вторые входы граничных ячеек подключены к выходу «Упр.3» третьего двухвходового элемента И, третьи входы (i, t) граничных ячеек (i=1 … n-1, t=i … n-1) подключены к выходам (i, j)-ых поисковых ячеек (i=1 … n-1, j=k+i … m), четвертые входы граничных ячеек подключены к входу тактовых импульсов ТИ, пятый вход (i, j)-й граничной ячейки (i=1 … n-1, j=n-1) соединен с выходом поисковой ячейки (i+1,1), пятый вход (i, j)-й граничной ячейки (i=1 … n-1, j=i … n-2) соединен с выходом граничной ячейки (i+1, j+1), выход (i, j)-й граничной ячейки (i=1, j=1 … n-1) соединен с третьим входом j-го триггера позиции частичного вхождения.