СПОСОБ И УСТРОЙСТВО ПОИСКА СОСТАВНОГО ОБРАЗЦА В ПОСЛЕДОВАТЕЛЬНОСТИ
METHOD AND APPARATUS FOR SEARCHING FOR COMPOSITE SAMPLE IN SEQUENCE

Изобретение относится к области вычислительной техники и информатики, может быть использовано в информационно-поисковых и экспертных системах, в системах высокочастотного трейдинга, в системах передачи данных, в специализированных устройствах и системах обработки символьной информации и др.
1
2
z
1
2
z
1
2,
z
1
2
z
Рассматривается задача поиска составного образца в анализируемой последовательности (текст, поток данных). 13 общем случае, составной образец и анализируемая последовательность представляют одномерные структуры данных (строки), составленные из букв рабочего алфавита. Пусть заданы составной образец x длиной m-символов, содержащий z подстрок x, x…x с длинами t, t, …t, такими, что (t+t+…+t≤m, и текст у длиной n-символов, где n>0, m>0 и m≤n. Требуется найти позиции вхождения подстрок из x в y, т.е. определить такие наименьшие адреса i, i…i, при которых справедливо
, .
В частном случае, для образцов, включающих только одну подстроку, задача поиска формулируется как поиск вхождения. При лом вюрая часть условия (1) записывается как
1
2
2
3
i+1=i; i+1=1i; .
По умолчанию выражения (2) подразумеваются, они определяют физически смежный характер расположения вхождений отдельных подстрок из x в структуре текста y.
1
2
z
1
2
z
Наиболее важным практическим случаем для систем обработки символьной информации является поиск составного образца x, содержащего z подстрок x, x…x с длинами, равными одному символу каждая, т.е. t=t=…t=1. Фактически в анализируемой последовательности y осуществляется посимвольный поиск из x, для каждого элемента которого не обязательно выполняется условие (2), но обязательно выполняемся условие (1).
Известен способ конвейерного поиска вхождений [Кулик, Б.А. Системы поиска в произвольном тексте / Б.А.Кулик // Программирование. 1987. №1 - С.6-10.], основанный на параллельном сопоставлении текущего символа образца с анализируемой последовательностью и на вычислении, хранении и обработке двух двоичных (характеристических) векторов с количеством бит, равным количеству символов в тексте. Алгоритмизация данного способа заключается в циклической обработке предыдущего и текущего характеристических векторов на основе аппаратно-ориентированной операции «косая конъюнкция», представляющей собой побитовое умножение двух двоичных векторов, причем биты предыдущего вектора со смещением на одну позицию к началу вектора. Недостаток данного способа заключается в необходимости дополнительных затрат времени на проверку позиций «1» в двоичных векторах в соответствии с распределением символов составного образца по тексту.
j-1
j
Известен способ матричного поиска вхождений строки-образца [Титенко, Е.А. Метод параллельною поиска по образцу и матричное устройство для его реализации / К.А.Титенко // Информационные системы и технологии. №4. - 2011 С.24-30.], основанный на двумерном представлении слов-операндов для учета позиционных и временных соотношений между символами двух строк и заключающийся в организации вычислений по диагоналям двоичной (характеристической) матрицы. Параллельная обработка матрицы состоит в побитовой обработке элементов строк и столбцов в составе k (k=m-n-1) диагоналей матрицы. Последовательности смежных «1» в составе каждой диагонали матрицы описывают структурные отношения вхождения. При организации поиска составного образца недостаток данного способа - невозможность учета позицией ню нерегулярного распределения символов составного образца по тексту и, как следствие, избыточные затраты времени на последовательную обработку каждого символа составного образца и дополнительная проверка текущего и предыдущего адресов односимвольных вхождений па условие i<i, где 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
2
1
2
3
4
1
2
1
6
1
2
Устройство поиска составного образца в последовательности (фиг.1) содержит блоки 1 и 1 хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, блок 4 поиска составного образца, информационные входы 4, 4, 4 и 4, информационные выходы 5-5, входы 6-6 задания режима работы, входы 7 и 7 начальной установки.
1
2
Структура блоков 1, 1, 2, 3 строго соответствуют устройству-прототипу в схемном и в функциональном отношении, состоит из совпадающих элементов и связей между ними.
1
3
4
2
Блок 4 поиска составного образца содержит два управляющих входа: «Начальная установка» 7 (первый вход) и вход «Запись строк» (второй вход), третий и четвертый входы для подачи символов составного образца и текста в параллельном коде через информационные входы 4, и 4 устройства, а также один информационный выход, являющийся вторым выходом 5 устройства. При этом второй управляющий вход блока 4 соединен со вторым выходом операционного блока 3.
1
n
1
m
11
nm.
i
j
1
n
i
1
m
j
Блок 4 поиска составного образца содержит элемент 31 задержки, состоящий из n пар инверторов, n регистров 32-32 для хранения кодов символов составного образца, m регистров 33-33 для хранения кодов символов текста, характеристической матрицы поисковых ячеек 34-34 и (n-1)×k двухвходовых элементов 40 ИЛИ для построчного вычисления стартовых значений, к триггеров 37 позиций, причем регистр 32 (i=1-n) и регистр 33 (j=1-m) содержат первый и второй управляющие входы, третий p-разрядный информационный вход и один выход соответственно. Первые и вторые входы n регистров 32 для хранения кодов символов составного образца и первые и вторые входы m регистров 33 для хранения кодов символов текста соединены соответственно с первым и вторым управляющими входами блока 4 поиска составного образца, третий вход которого разрядностью p×n бит предназначен для параллельной записи составного образца в регистры 32-32 и состоит из n групп разрядов по p разрядов каждая группа, кодирующих символы составного образца, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход регистра 32 (i=1-n), четвертый вход блока 4 поиска составного образца разрядностью p×m бит предназначен для параллельной записи текста в регистры 33-33 и состоит из m групп разрядов по p разрядов каждая группа, кодирующих символы текста, причем j-ая группа разрядов (j=1-m) подается на третий p-разрядиый вход регистра 33 (j=1-m). Второй управляющий вход блока 4 поиска составного образца также соединен со входом элемента 31 задержки.
11
nm
ij
ij
ij
ij
1
р
1
р
1
р
ij
ij
ij
ij
ij
Характеристическая матрица поисковых ячеек 34-34 имеет размер n×k ячеек (k=m-n+1 - количество диагоналей в матрице), причем каждая поисковая ячейка 34 имеет три входа и один выход и содержит двухвходовую схему 35 сравнения на равенство p-разрядных кодов символов составного образна и текста и двухвходовой элемент 36 И, каждая двухвходовая схема 35 сравнения на равенство в составе поисковой ячейки 34 состоит из p-входового элемента 39 И, а также p двухвходовых элементов 38-38 суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-ой p-разрядной группы третьего входа блока 4 поиска составного образца, а на вторые входы двухвходовых элементов 38-38 суммы по модулю два с инверсией - соответствующий разряд из j-ой p-разрядной группы четвертого входа блока 4 поиска составного образца, все выходы двухвходовых элементов 38-38 суммы по модулю два с инверсией в составе двухвходовой схемы 35 сравнения на равенство соединены с p-входовым элементом 39 И, выход которого является выходом двухвходовой схемы 35 сравнения на равенство. Первый и второй p-разрядные входы поисковой ячейки 34 соответственно соединены с первым и вторым p-разрядными входами двухвходовой схемы 35 сравнения на равенство, выход которой является первым входом двухвходового элемент 36 И, второй вход которого является третьим входом поисковой ячейки 34, выходом которой является выход двухвходового элемента 36 И. Также в каждую строку характеристической матрицы, кроме последней строки, входят к двухвходовых элементов 40 ИЛИ.
11
nm
11
1k
i
j
ij
Характеристическая матрица поисковых ячеек 34-34 имеем геометрическую форму параллелограмма, в которой в каждой строке располагается k поисковых ячеек, сдвинутых относительно следующей строки ячеек вправо на 1 позицию, начиная с ячеек первой строки 34-34. Такая форма матрицы обеспечивает направление поиска по диагоналям, проходящим через ячейки от первой строки к последней строке включительно. Также в каждую строку характеристической матрицы, кроме последней строки, входят k двухвходовых элементов 40 ИЛИ. Первые p-разрядные входы k поисковых ячеек i-ой строки матрицы (i=1-n) соединены с p-разрядным выходом регистра 32. P-разрядный выход регистра 33 (j=1-m) соединен со вторыми p-разрядными входами всех поисковых ячеек, входящих в j-ый столбец матрицы. Выход каждой поисковой ячейки 34, кроме 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», задавая тем самым направление поиска по соответствующей диагонали от первой строки матрицы к последней строке включительно.
1
k
i
1
k
Триггера 37-37 позиций хранят результат поиска в виде k-разрядного кода, в котором значением логической «1» отмечены позиции начала вхождений составного образца в текст. Триггер 37 позиции (i=1-k) содержит три входа (первый и второй управляющие, третий одноразрядный информационный вход) и один выход. Первый вход блока 4 поиска составного образца соединен соответственно с первыми входами k триггеров 37 позиций, вторые входы k триггеров 37 позиций соединены с выходом элемента 31 задержки. Выходы триггеров 37-37 позиций образуют k-разрядный информационный выход блока 4 поиска составного образца.
Данное устройство, как и устройство-прототип, работает в режимах «Запись» и «Операция». Режим "Запись" строго соответствует алгоритму, описанному в устройстве-прототипе.
В алгоритме режима "Операция" дополнительно к выполняемым в устройстве-прототипе вводится операция, обозначаемая как «ПСО» и имеющая собственный код операции, который подается на соответствующий вход режима работы. С учетом появления блока 4 по сравнению с устройством-прототипом в алгоритм режима "Операция" вносятся следующие дополнения.
1
6
3
4
11
nm
И
И
инв
инв
1
k
1
k
2
Пусть устройство выполняет режим «Операция» с кодом операции «ПСО». На вход 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. Поиск начинается с ячеек первой строки характеристической матрицы. Начальный k-битовый характеристический вектор, равный 11…1, подается на третьи входы поисковых ячеек первой строки матрицы и определяет тем самым направление параллельного поиска по всем диагоналям характеристической матрицы от поисковых ячеек первой строки до поисковых ячеек последней строки включительно. Время поиска составного образца определяется величиной Т=mτ, где τ - время задержки в элементе 36 И. По завершении процессов поиска импульсный сигнал с выхода элемента 31 задержки через время Т=m2τ (2τ - время задержки на цепочке инверторов) записывает k-битовый результат поиска составного образца в триггера 37-37 позиций. Выходы триггеров 37-37 позиций являются k-разрядным выходом блока 4 поиска составного образца и образуют второй выход устройства 5.
Выполнение алгоритма в режиме «Операция» на остальных операциях строго соответствует устройству-прототипу.
Таким образом, достигается расширение функциональности устройства поиска составного образца в последовательности за счет модернизации связей ячеек характеристической матрицы и ввода дополнительных элементов в характеристическую матрицу поиска.