Устройство поиска произвольных вхождений

 

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

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

Известно "Устройство для реализации подстановок с двухкомпонентными вхождениями" (а.с. 1667097, 1991 г. Бюл. 28), позволяющее определить вхождения в представленном слове-образце [9].

Известно также "Устройство для сортировки чисел" (а.с. 1277091, 1986 г. Бюл. 46), позволяющее упорядочить числа в возрастающем и в убывающем порядке [10].

Известно "Устройство для морфологического анализа слов естественных языков и языков "деловой прозы"" (а. с. 1837327, 1993 г. Бюл. 32), которое позволяет проводить морфологический анализ слов реальных языков на основе логических признаков принадлежности к классам словоформ [8].

В качестве прототипа выбрано "Устройство поиска вхождений" (патент 2150740, 2000 г.), которое позволяет осуществлять поиск вхождений, представленных в четырех видах [8].

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

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

Решение задачи осуществляется тем, что устройство поиска произвольных вхождений, содержащее блок памяти слов, блок памяти вхождений, компаратор, блок хранения адреса вхождений, блок управления, отличающиеся тем, что дополнительно введены блок анализа и формирования сигналов сдвига, причем первый и второй управляющие входы блока управления соединены соответственно с первым и вторым управляющими выходами блока памяти вхождений, управляющий вход которого соединен с первым управляющим выходом блока управления, с первого по четвертый информационные выходы которого соединены соответственно с первым по четвертый информационными входами блока памяти вхождений, информационный выход которого соединен с первым информационным входом компаратора, управляющий выход которого соединен с первым управляющим входом блока анализа и формирования сигналов сдвига и с третьим управляющим входом блока управления, со второго по шестой управляющие выходы которого соединены соответственно со вторым по шестой управляющими входами блока анализа и формирования сигналов сдвига, первый и второй управляющие выходы которого соединены соответственно с четвертым и пятым управляющими входами блока управления, с тринадцатого по семнадцатый управляющие выходы которого соединены соответственно с одиннадцатым по седьмой управляющими входами блока анализа и формирования сигналов сдвига, информационный выход которого соединен с информационным входом блока хранения адреса вхождений, с первого по шестой управляющие входы которого соединены соответственно с седьмым по двенадцатый управляющими выходами блока управления, восемнадцатый управляющий выход которого соединен с управляющим входом блока памяти слов, с первого по четвертый информационные входы которого соединены соответственно с пятым по восьмой информационными выходами блока управления, восьмой управляющий вход которого соединен с управляющим выходом блока памяти слов, информационный выход которого соединен со вторым информационным входом компаратора, шестой и седьмой управляющие входы блока управления "ПУСК" и "СБРОС" являются внешними входами устройства.

БПВ - блок служит для хранения вхождений, с которыми необходимо будет провести поисковые операции.

БПС - блок служит для хранения слов, в которых будут определяться вхождения.

КОМ - служит для сравнения символов слово-образца с буквами вхождения.

БАФС - блок служит для анализа сигнала компаратора по обнаружению вхождений и формирования сигналов сдвига, а также по определению адреса (позиции) вхождений в слове-образце.

БХАВ - блок служит для хранения в памяти адресов вхождений.

БУ - блок служит для управления устройством.

Процессы поиска вхождений образца в обрабатываемом слове адекватно описываются в терминах языка регулярных выражений путем использования операций итерации и конъюнктивного следования (конкатенация) [1].

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

Если образец имеет повторение своих начальных фрагментов, то его форма записи будет иметь вид: S={G}F, (1) где - S образец; G - начальный повторяющийся фрагмент; F - собственное окончание образца; {} - обозначение операции "итерация".

Очевидно, что при существовании итерации фрагмента в середине образца при следующей форме его записи: S=G{H}F (2)
не влечет за собой пропуска позиции вхождения образца в обрабатываемое слово. Также безопасной структурой образца является следующая его форма представления:
S=G{F} (3)
В случае общего положения структура образца может принимать вид:
S={G}H{F} (4)
Вместе с тем, существует еще одна структура образца, которая порождает необходимость в выполнении отступа в пространстве обрабатываемого слова с целью предотвращения аварийного пропуска позиции вхождения. Такая структура образца имеет вид:
S=GFGP, (5)
т.е. начальный фрагмент образца входит в его собственную структуру более одного раза.

В выражениях (1), (2), (3), (4) и (5) S, G, F, Н и Р - произвольные непустые слова.

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

При осуществлении поисковых функций в словах вхождения могут быть представлены шестью различными комбинациями букв в слове-образце (вхождении):
1) нет повтора одинаковых букв (итерации) в слове-образце, пример "абсорпнеи";
2) повтор одинаковых букв есть в середине слова-образца, пример "мтрааааавыф", при этом принято обозначение P{S}T;
3) итерация существует в конце слова, пример "савку-ооооо", обозначение P{S};
4) итерация в слове-образце существует в начале слова, примером может служить вхождение "еееимпавк", обозначение {S}P;
5) итерация в слове-образце присутствует и в начале слова, и в конце, пример "ииипрнссссс", обозначение {S}P{V}.

6) слово-образец состоит полностью из итераций, пример -"ммммм", обозначение {S}.

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

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

Пятый случай, когда итерация и в начале и в конце слова-образца, поиск в представленном устройстве осуществляется с начала слова. Но предварительно осуществляется анализ вхождения блоком поиска итераций устройства. Вхождение разбивается на две части:
1) только итерации, т.е. часть, состоящая из одинаковых символов:
2) остальная часть вхождения, но без итераций в начале слова-образца.

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

Необходимо рассмотреть случаи, когда под итерацией понимается не только одна буква, но несколько чередующихся символов, например слово-образец имеет вид: абабабабпртоо. Вначале слова записаны итерации, состоящие из разных букв аб, и таких повторов в примере будет 4. Такие итерации назовем двухбуквенные. Легко привести примеры трех, четырех, пяти и n-буквенных итераций. В конце слово-образец заканчивается также итерацией, но из одинаковых букв. В конце слова-образца тоже могут быть многобуквенные итерации. Для осуществления поиска различных видов слов-образцов, состоящих из различных вариантов итераций, необходимо, очевидно, разработать сложные схемы селекции, определяющие вид итераций. Затем, в зависимости от вида итерации выбирается алгоритм, осуществляющий поисковую операцию.

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

Алгоритм функционирования устройства заключается в следующем.

В регистре слов находится обрабатываемое слово. В регистре вхождений записывается слово-образец. Задача устройства заключается в определении вхождения в обрабатываемом слове. Если вхождение найдено, то ее адрес записывается в память устройства. Если вхождение не найдено, то в регистр обрабатываемого слова записывается новое слово для проведения поисковой операции. Сравнение в устройстве происходит по-буквенно. На вход компаратора поступают по одной букве из регистра обрабатываемого слова и из регистра слова-образца. Если результат сравнения положительный, то происходит сдвиг влево на один разряд обоих регистров, и на вход компаратора поступают очередные символы из регистров. Возможно возникнет ситуация, когда положительное сравнение произойдет на первой букве, на второй, на третьей и т.д., но на k букве результат сравнения будет отрицательным и при этом конца слова-образца не будет обнаружено. Двоично-десятичные счетчики устройства подсчитывают количество положительных сравнений. Скажем, их произошло k совпадений, а на k+1 получен отрицательный результат. В этом случае осуществляется сдвиг вправо на k-1 разрядов регистра, в котором хранится обрабатываемое слово. Происходит "вычеркивание" первой буквы из серии, где произошли положительные сравнения. Дальнейшее сравнение будет происходить, уже начиная со второй буквы обрабатываемого слова и с первой буквой вхождения. Вхождение будет переписано заново из памяти вхождений. Процедуры сдвига возможны при применении реверсивных регистров, которые осуществляют сдвиг информации как влево, так и вправо.

На фиг. 1 изображена структурная схема устройства поиска произвольных вхождений.

На фиг. 2 представлен вариант технической реализации блока памяти вхождений.

На фиг.3 представлен вариант технической реализации блока памяти слов.

На фиг.4 показана функциональна схема блока анализа и формирования сигналов сдвига.

На фиг. 5 изображена функциональная схема блока хранения адреса вхождений.

На фиг.6 - содержательная ГСА работы устройства.

На фиг.7 - размеченная ГСА работы устройства.

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

Для описания алгоритма работы блока 6 управления используются следующие идентификаторы.

1. ПРКВ - признак конца вхождения. Это может быть двоичный код, равный 11...1.

2. ПРКС - признак конца слова. Равный 11..1.

3. КР - команда, определяющая конец работы устройства.

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

5. СУ2 - сигналы управления сдвигающим регистром блока памяти слов (сигналы записи, приема, выдачи данных).

6. СДВ - команда сдвига, поступающая из блока управления на вход сдвигающего регистра вхождения блока памяти вхождений.

7. СДС - команда сдвига, поступающая из блока управления на вход сдвигающего регистра слова блока памяти слов.

8. СУП1 - команды управления записью, выдачей, хранения блока памяти вхождений.

9. СУП2 - команды управления записью, выдачей, хранения блока памяти слов.

10. АД1 - адреса данных выдачи, записи блока памяти вхождения.

11. АД2 - адреса данных выдачи, записи блока памяти слов.

12. ДН1 - данные (двоичные коды букв) блока памяти вхождений.

13. ДН2 - данные (двоичные коды букв) блока памяти слов.

14. ССР - сигнал сравнения, поступающий из компаратора.

15. СИН - команда синхронизации, поступающая на вход Сч D.18 блока анализа и формирования сигналов сдвига из блока управления.

16. ОБН - команда обнуления двоичного счетчика Сч D.18 блока анализа и формирования сигналов сдвига.

17. СВА - команда выдачи адреса вхождения из блока анализа и формирования сигналов сдвига в блок хранения адреса вхождений.

18. СЗЩ - команда разрешения записи в триггер Тр D.14 выходного сигнала из компаратора.

19. СДЛ - команда, поступающая из блока управления, открывающая или запирающая электронный ключ И D. 20 блока анализа и формирования сигналов сдвига.

20. СН - команда синхронизации двоичного счетчика Сч D.21 блока анализа и формирования сигналов сдвига.

21. СО - команда обнуления двоичного счетчика Сч D.21 блока анализа и формирования сигналов сдвига.

22. ПИМ - прямоугольные импульсы, поступающие на информационный вход электронного ключа И D.20 блока анализа и формирования сигналов сдвига.

23. АдСТ - адреса столбцов для записи вхождений в блок хранения адреса вхождений.

24. АдСТР - адреса строк для записи вхождений в блок хранения адреса вхождений.

25. ДАВ - данные адресов вхождений.

26. АВХ - адрес вхождения.

27. ВДВ - выходные данные вхождения блока памяти вхождений.

28. ВДС - выходные данные слова блока памяти слов.

29. ДС - данные слов.

30. ДВ - данные вхождений.

31. ПРИ - прямоугольные импульсы, поступающие из бока управления на информационный вход логического элемента И D.16.

32. ТАК - тактовые прямоугольные импульсы, поступающие на информационный вход логического элемента И D.17.

33. СВП - команда, определяющая количество сдвигов вправо регистра PrC1 D.10 блока памяти слов.

34. ДШЕ - команда, определяющая двоичный код 0001 (единицу) на выходе двоичного счетчика Сч D.18.

35. ГИ - генератор импульсов, поступающий из блока управления на суммирующий вход (+) двоичного счетчика Сч ст D.24.

36. ТИ - тактовые импульсы, поступающие из блока управления на суммирующий вход (+) двоичного счетчика Сч стр D.25.

37. СБР - команда обнуления двоичного счетчика Сч ст D.24.

38. СБО - команда обнуления двоичного счетчика Сч стр D.25.

39. Сч/Зп - команда считывания/записи оперативно-запоминающего устройства.

40. ВК - команда выбора кристалла оперативно-запоминающего устройства.

Работа алгоритма управления устройства.

Содержательная ГСА управления приведена на фиг.6 и отражает работу блока управления (фиг.1).

По сигналам "УОО" и "ПУСК" (блоки 2,4-граф-схемы алгоритма) (фиг.1) происходит установка в нуль всех элементов памяти устройства, по команде "СБРОС:=1" (блок 3).

В блоке 5 алгоритма происходит запись в регистр слов из памяти слов слова-образца РгС1: = ДС, в регистр вхождений записывается из памяти вхождений последовательность букв (вхождение) РгВ:=ДВ. D-Триггер Тр блока анализа и формирования сигналов сдвига устанавливается в "0" ТР:=0. По этим командам происходит предварительная загрузка устройства.

В блоке 6 алгоритма происходит анализ признака конца вхождения ПРКВ (фиг. 2). Если ПРКВ=1, то в регистре вхождения обнаружен двоичный код 11..1. В этом случае вхождение обнаружено в слове-образце, и в блок хранения адреса вхождений записывается адрес вхождения (фиг.5). Если ПРКВ=0, то это означает, что процесс сравнения идет по-буквенно, но не все буквы вхождения еще просмотрены, при этом осуществляется переход на 9 блок алгоритма.

В блоке 7 алгоритма происходит запись адреса в блок хранения адреса вхождений. На управляющий вход электронного ключа Кл блока 4 анализа и формирования сигналов сдвига поступает разрешающий сигнал из блока управления - СВА, Кл:=СВА. Информация с выхода двоичного счетчика СЧ2 через открытый ключ Кл поступает на вход оперативно-запоминающего устройства ОЗУ (фиг.4, фиг.5). Сигнал разрешения для записи информации поступает из блока управления Сч/Зп: = 0, ВК:=0. На управляющие входы поступают нулевые значения, что соответствует режиму записи в ОЗУ устройства входной информации, т.е. адреса вхождения АВХ ОЗУ:=АВХ.

В блоке 8 алгоритма происходит запись очередного вхождения в регистр вхождений РгВ блока 1 памяти вхождений. Из памяти вхождений на вход регистра поступает информация РгВ:=ДВ.

В блоке 9 алгоритма происходит анализ признака конца слова ПРКС (признаком является двоичный код, равный всем единицам 11...1). Если ПРКС=0, то процесс поиска будет продолжен и при этом осуществляется переход на блок 10 алгоритма. Если обнаружен признак конца слова ПРКС=1, то осуществляется переход на блок 22 алгоритма.

В блоке 10 алгоритма происходит анализ сигнала сравнения ССР, поступившего с выхода компаратора (фиг.4). Если ССР=1, то произошло совпадение буквы вхождения с буквой слова. В этом случае осуществляется переход на блок 19 алгоритма. Если ССР= 0, то совпадения не произошло и переход произошел на блок 11 алгоритма.

В блоке 11 алгоритма анализируется содержимое триггера Тр (фиг.4). Если Тр= 0, то это означает, что совпадения на предыдущем шаге не было, в этом случае формируется сигнал сдвига влево на один разряд в блоке 3 памяти слов регистра РгС1. Если Тр=1, то осуществляется переход на блок 13 алгоритма, где анализируется состояние счетчика СЧ1 блока 4 анализа и формирования сигналов сдвига.

В блоке 12 алгоритма формируется командой СДС:=0 сдвиг влево на один разряд информации из регистра РгС1 в регистр РгС2 блока 3 памяти слов. При этом РгС2:=РгС1. На освободившиеся место в регистр РгС1 записывается очередной символ обрабатываемого слова из памяти слов блока 3 РгС1:=ДС. По выходу из блока формируется переход на 6 алгоритма.

В блоке 13 анализируется состояние двоичного счетчика СЧ1 блока 4 анализа и формирования сигналов сдвига. Если состояние счетчика меньше или равно единице, то осуществляется переход на блок 16 алгоритма. Если условие выполняется, т.е. значение счетчика СЧ1 больше единицы, то происходит переход на блок 14 алгоритма.

В блоке 14 алгоритма формируется подача прямоугольных импульсов из блока управления ПРИ на вычитающий вход двоичного счетчика СЧ1 блока 4 анализа и формирования сигналов сдвига. По команде СВП:=1 в счетчике происходит алгебраическое вычитание единицы до тех пор, пока состояние этого счетчика не будет равно единичному значению СЧ1:=ПРИ.

В блоке 15 алгоритма формируется сдвиг вправо. Командой СДС:=1 информация из регистра РгС2 сдвигается на один разряд в регистр РгС1, РгС1:=РгС2. По команде СУ2:=1 происходит разрешение осуществления операций сдвига в блоке 3 памяти слов. Информация из регистра РгС2 сдвигается в регистр РгС1 до тех пор, пока состояние счетчика СЧ1 не будет равно единице. Блоки 13, 14, 15 алгоритма формируют цикл. Выходом из цикла является условие, при котором значение счетчика будет не больше единицы. По выходу из блока осуществляется переход на блок 13 алгоритма.

В блоке 16 алгоритма на вход регистра вхождения РгВ блока 1 памяти вхождений из блока управления поступают управляющие сигналы РгВ:=СУ1. В результате этого в регистр вхождений записывается информация из памяти вхождений РгВ:=ДВ.

В блоке 17 алгоритма регистр вхождений РгС1 принимает информацию из регистра РгС2 РгС1: = РгС2. Обрабатываемое слово сдвигается вправо на n-1 разрядов, где n - количество сдвигов влево этого же слова.

В блоке 18 алгоритма по команде ОБН:=1 происходит обнуление счетчика СЧ1 блока 4 анализа и формирования сигналов сдвига. Двоичный счетчик СЧ1 принимает нулевое значение СЧ1:=0. По выходу из блока формируется переход на блок 6 алгоритма.

В блоке 19 алгоритма на вход D-триггера блока 4 анализа и формирования сигналов сдвига поступает сигнал ССР из компаратора КОМ 2 ТР:=ССР. Триггер устанавливается в единичное состояние. Это означает, что входные символы на входе компаратора равны между собой.

В блоке 20 алгоритма по команде СЗЩ:=1 из блока управления происходит разрешение на запись в D-триггер информации с выхода компаратора. По команде ТР: = 1 D-триггер блока 4 анализа и формирования сигналов сдвига устанавливается в единицу. На суммирующий вход двоичного счетчика СЧ1 этого же блока поступают тактовые импульсы СЧ1:=ТАК. Счетчик подсчитывает количество совпадений в компараторе.

В блоке 21 алгоритма по командам СДВ:=0 и СДС:=0 формируется сдвиг влево информации, находящейся в регистрах соответственно РгВ блока 1 памяти вхождений и РгС1 блока 3 памяти слов. При этом осуществляется переход на блок 6 алгоритма.

В блоке 22 алгоритма происходит анализ конца работы всего поискового устройства. Конец работы устройства будет в том случае, когда память вхождений окажется "пустой". Если КР=0, то осуществляется переход на блок 23. Если КР= 1, то устройство поиска заканчивает работу и происходит переход на блок 24 алгоритма - конечный блок алгоритма.

В блоке 23 алгоритма происходит запись очередного слова из памяти слов в регистр слов для дальнейшего поиска вхождений (фиг.3), управляющей командой СУ2: = 1 происходит разрешение приема регистром РгС1 информации из памяти слов. Командой РгС1:=ДС в регистр записывается очередное слово. По выходу из блока формируется переход на блок 6 алгоритма.

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

Внешние управляющие сигналы "ПУСК" и "СБРОС" поступают в блок 6 управления.

В оперативно-запоминающем устройстве блока БПС записаны слова-образцы (слова), в которых необходимо обнаружить вхождения. Под вхождениями подразумевается символ или цепочка символов (включая слова), которые нужно найти в словах блока БПС. Вхождения находятся в оперативно-запоминающем устройстве блока БПВ. В блоке сравнения (компараторе) происходит последовательное сравнение каждой буквы вхождения с символами слова. В блоке 4 анализа и формирования сигналов сдвига обрабатывается сигнал сравнения блоков БПС и БПВ. Если вхождение обнаружено в слове, то формируется адрес (позиция) этого вхождения в слове. Адрес хранится в блоке 5 хранения адреса. Если сравнение не произошло, то формируются сигналы сдвига в блоке БУ, поступающие на вход блоков БПС и БПВ. Если при работе устройства возникает ситуация, при которой были получены вначале положительные результаты сравнения в компараторе, а затем отрицательный, но признак конца вхождения еще необнаружен. В этом случае будут найдены только несколько символов вхождения, но не все вхождения полностью. При положительном результате в компараторе происходит сдвиг влево на одну позицию информации регистра РгС1. Слово из регистра РгС1 по-буквенно переходит во вторую часть регистра - РгС2. Двоичным счетчиком фиксируется положительная серия сравнений в компараторе. В случае отрицательного результата при сравнении происходит обратный сдвиг вправо информации из РгС2 в РгС1, но на один сдвиг меньше. Процесс поиска вхождений будет продолжен, но со второй буквы обрабатываемого слова. Первая буква в этом случае как бы "вычеркивается". Процесс продолжается до тех пор, пока не будут обнаружены все вхождения в обрабатываемом слове.

Блок 1 памяти вхождений содержит оперативно-запоминающее устройство (ОЗУ) - память вхождений DD8, реверсивный регистр сдвига РгВ DD7 (регистр вхождений), в котором будет хранится вхождение, логический элемент И DD9 для обнаружения признака конца вхождения. По сигналам управления СУП1 происходит разрешение записи информации, по адресным входам АД1 записываются данные ДН1 в ОЗУ (память вхождений) из блока 6 управления (фиг.2). С выхода памяти вхождений информация ДВ поступает на вход реверсивного регистра вхождений РгВ DD7, по сигналам управления СУ1 из блока 6 управления происходит запись буквы вхождения в регистр вхождений. Сигнал сдвига вхождений СДВ из блока 6 управления поступает на вход реверсивного регистра вхождений (фиг.2). Выходная информация из реверсивного регистра вхождений ВДВ поступает на вход компаратора (фиг. 1). Реверсивный регистр РгВ выполняет сдвиг в любом направлении: слева направо или наоборот. Сдвиг вправо выполняется при значении сигнала СДВ=1, сдвиг влево при СДВ=0, т.е. направление сдвига осуществляется одним управляющим сигналом [2,3,4,6]. Элемент И DD9 формирует сигнал признака конца вхождений ПРКВ, равный единице (все единицы на входе). В памяти вхождений формируется сигнал КР - конец работы, если ОЗУ будет пусто. Перед началом работы устройства в памяти вхождений записаны все вхождения, в регистре вхождений находится первое вхождение, сигнал признака конца вхождений ПРКВ равен нулю, сигнал сдвига вхождений СДВ равен нулю.

Компаратор 2 представляет собой устройство сравнения на равенство входных величин: выходных данных вхождений ВДВ блока 1 БПВ и выходных данных слов ВДС блока 3 БПС (фиг.1). Если входные сигналы равны, то на выходе компаратора формируется единичный сигнал ССР. В обратном случае ССР будет равен нулю. Выходной сигнал компаратора поступает на вход блока 6 управления и на вход блока 4 анализа и формирования сигналов сдвига (фиг.1).

Блок 3 памяти слов содержит оперативно-запоминающее устройство (ОЗУ) - память слов DD12, реверсивный регистр сдвига РгС1 DD10 (регистр слов), в котором будет хранится слово-образец (вхождение), реверсивный регистр сдвига РгС2 DD11, логический элемент И DD13 предназначен для обнаружения признака конца слова ПРКС. По сигналам управления СУП2 происходит разрешение записи информации, по адресным входам АД2 записываются данные ДН2 в ОЗУ (память слов) из блока 6 управления (фиг.3). С выхода памяти слов информация ДС поступает на вход реверсивного регистра слов PrCl DD10, по сигналам управления СУ2 из блока 6 управления происходит запись слова в реверсивный регистр слов PrC1 DD10. Сигнал сдвига слов СДС из блока 6 управления поступает на вход реверсивного регистра слов РгС1 (фиг.3). Выходная информация из реверсивного регистра слов РгС1 поступает на вход логического элемента И DD13, а также на второй вход компаратора КОМ. Элемент И DD13 формирует сигнал признака конца слова ПРКС, равный единице (все единицы на входе). Перед началом работы устройства в памяти слов DD12 записаны все слова, в регистре слов находится первое слово, сигнал признака конца слова ПРКС равен нулю. Если на выходе компаратора КОМ будет сформирован сигнал сравнения ССР, то сигнал сдвига СДС будет равен нулю, в этом случае будет сформирован сигнал сдвига влево на один разряд. Информация из регистра PrCl DD10 сдвинется на один символ влево. Этот символ перейдет по сигналам СУ2 в регистр РгС2 DD11. Процесс сдвига влево будет продолжаться до тех пор, пока не будет получен отрицательный результат сравнения в компараторе КОМ DD2. Предположим, что было зафиксировано 4 сдвига влево и получен отрицательный сигнал сравнения ССР, равный нулю. Тогда блоком управления 6 будут сформированы сигналы вправо, при этом сигнал сдвига СДС равен единице. Информация из регистра РгС2 DD11 будет сдвинута вправо на один разряд меньше, чем влево, в нашем случае 3. Три буквы из регистра РгС2 DD11 перейдут в регистр PrC1 DD10. В этом случае вторая буква будет первой в регистре PrC1, процесс поиска вхождений будет продолжен.

Блок 4 анализа и формирования сигналов сдвига содержит D-триггер DD14, двухвходовый логический элемент И DD15 с инверсным входом, двухвходовый логический элемент И DD17, двухвходовый логический элемент И DD20, трехвходовый логический элемент И DD16 с инверсным входом, трехвходовый элемент И DD19 с инверсными входами, трехвходовый элемент И DD23 с инверсным входом, электронный ключ DD22, двоичный счетчик СЧ1 DD18, двоичный счетчик СЧ2 DD21. Перед началом работы устройства двоичные счетчики DD18, DD21, а также D-триггер установлены в нулевое состояние. Блок 4 анализа и формирования сигналов сдвига обрабатывает выходной сигнал ССР с компаратора. Если сигнал ССР равен единице, то это означает, что произошло совпадение двоичного кода символа вхождения с двоичным кодом буквы слова. В этом случае D-триггер Тр DD14 по приходу из блока управления разрешающего сигнала СЗЩ устанавливается в единичное состояние. Логический элемент И DD17, выполняющий функцию электронного ключа, отпирается, тактовые импульсы ТАК из блока управления поступают на суммирующий (+) вход двоичного счетчика СЧ1 DD18. В двоичном счетчике СЧ1 DD18 происходит суммирование тактовых импульсов, количество которых соответствует количеству совпадений в компараторе. На выходе двоичного счетчика СЧ1 DD18 формируется двоичный код, соответствующий количеству положительных совпадений в компараторе. При каждом положительном совпадении в компараторе происходит формирование сигналов сдвига влево СДВ и СДС, равных нулю, и осуществляется сдвиг на один символ влево в регистрах РгВ DD7 блока 1 памяти вхождений и регистре РгС1 блока 3 памяти слов. Регистр РгС2 DD11 блока памяти слов записывает каждый символ, поступающий из регистра PгCl DD10. В случае обнаружения признака конца вхождения ПРКВ, равным единице, логическим элементом И DD13 блока 3 памяти слов происходит определение адреса вхождения и записывание по соответствующему адресу записи в оперативно-запоминающее устройство ОЗУ DD26 блока 5 хранения адреса вхождений. Если признак конца слова не обнаружен ПРКС=0 (равен нулю), то предыдущее вхождение восстанавливается, т. е. переписывается заново из памяти вхождений и процесс поиска вхождений в слове продолжается. Если совпадений в компараторе не происходит, выходной сигнал ССР равен нулю, то формируется только сигнал СДС, равный нулю, и происходит сдвиг влево на одну позицию информации, находящейся в регистре слов PгCl DD10 блока 3 памяти слов. При каждом сдвиге влево и отрицательном результате совпадения в компараторе из памяти слов ПС переписывается (дописывается) символ в регистр памяти слов PrCl DD10 блока 3 памяти слов. Возможна ситуация в поисковой операции, когда был получен положительный результат сравнения символов, тогда формируется сдвиг влево на один разряд регистров. После сдвига получен второй раз положительный результат, третий и так далее, но признака конца вхождения еще нет. Допустим, на n шаге получен отрицательный результат сравнения, а вхождение полностью не обнаружено. В этом случае D-триггер Тр DD14 был установлен в состояние единицы, т. е. на выходе элемента единица. На следующем этапе сигнал сравнения равен нулю ССР=0. На выходе логического элемента И DD15 будет сформирован единичный сигнал. Логический элемент И DD16 также будет открыт, прямоугольные импульсы из блока управления ПРИ будут поступать на вычитающий вход двоичного счетчика СЧ1 DD18. Вычитание происходит до тех пор, пока на выходе счетчика не будет двоичный код, равный единице. На положительный вход счетчика прямоугольные импульсы из блока управления поступать не будут, т.к. логический элемент И DD17, выполняющий функцию электронного ключа, будет заперт установившимся в нулевое состояние D-триггером DD14. Логический элемент И DD19 выполняет роль дешифратора единицы. Выход этого элемента равен единице в случае получения на выходе счетчика СЧ1 двоичного кода 0001. При всех других комбинациях на выходе данного элемента будет состояние нуль. При единице на выходе этого элемента логический элемент И DD16 запирается, т.к. единица поступает на инверсный вход. Прямоугольные импульсы на вычитающий вход счетчика СЧ1 не поступают. Счетчик СЧ1 обнуляется командой ОБН, поступающей из блока управления. Логический элемент И DD23 выполняет роль своеобразного "клапана", формирующего количества сдвигов вправо регистра РгС1. Каждый раз когда происходит вычитание единицы из содержимого счетчика СЧ1, происходит перемещение вправо информации из регистра РгС2 в регистр РгС1. Количество сдвигов вправо будет на один меньше, чем количество сдвигов влево. В нашем примере n-1. Вторая буква из полученной серии положительных сдвигов будет первой в регистре РгС1. Вхождение будет заново переписано из памяти вхождений в регистр вхождений РгВ. Процесс поиска будет продолжен.

Признак конца работы устройства КР, равного единице, может быть сформирован тогда, когда все вхождения просмотрены, в памяти вхождений нет информации. Еcли КР равен нулю, то регистр слова РгС1 блока 3 памяти слов БПС принимает новую информацию (новое слово) из памяти слов (фиг.3).

Блок 5 хранения адреса вхождений БХАВ содержит оперативно-запоминающее устройство ОЗУ DD26, двоичный счетчик, формирующий адреса столбцов ОЗУ - Сч ст DD24, двоичный счетчик, формирующий адреса строк ОЗУ - Сч стр DD25. Двоичные счетчики вначале работы устройства обнулены управляющими сигналами СБР, СБО, поступающими из блока управления. На входы счетчиков поступают прямоугольные импульсы ГИ, ТИ из блока управления. Счетчики формируют адреса строк и столбцов, по которым будут записаны адреса вхождений, поступающие на вход оперативно-запоминающего устройства ОЗУ DD26. Сигналы управления оперативно-запоминающего устройства ОЗУ DD26 считывания/запись и выбора кристалла соответственно при записи принимают значения Сч/Зп=0, ВК=0.

Блок 6 управления синтезируется на основе ГСА алгоритма управления (фиг. 6) известным способом [3, 5]. Размеченная ГСА работы блока 6 управления приведена на фиг.7, где обозначено:
логические условия:
X1: "УОО"
Х2:"ПУСК"
Х3:"ПРКВ"
Х4:"ПРКС"
Х5: "ССР"
Х6: "ТР"
Х7: "СЧ1>1"
Х8: "КР"
операторы:
У1: "СБРОС:=1"
У2: "РгВ:=ДВ"
У3: "РгС1:=ДС"
У4: "Тр:=0"
У5: "Кл:=СВА"
У6: "Сч/3п:=0"
У7: "ВК:=0"
У8: "ОЗУ:=АВХ"
У9: "СДС:=0"
У10: "РгС2:=РгС1"
У11: "СВП:=1"
У12: "СЧ1:=ПРИ"
У13: "СДС:=1"
У14: "РгС1:=РгС2"
У15: "СУ2:=1"
У16: "РгВ:=СУ1"
У17: "ОБН:=1"
У18: "СЧ1:=0"
У19: "ТР:=ССР"
У20: "СЗЩ:=1"
У21: "ТР:=1"
У22: "СЧ1:=ТАК"
У23: "СДВ:=0"
ИСТОЧНИКИ ИНФОРМАЦИИ
1. Кудрявцев В.Б., Подколзин А.С., Ушчумлич Ш. Введение в теорию абстрактных автоматов. М.: Из-во МГУ, 1985, 174 с.

2. Марков А.А., Нагорный Н.М. Теория алгоритмов. Москва.: Наука - 318 с. Главная редакция физико-математической литературы. 1984 г.

3. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. Москва. : Наука. Главная редакция физико-математической литературы. 1987 г., 210 с.

4. Алексенко А.Г., Шагурин И.И. Микросхемотехника: Учеб. пособие для вузов. 2-е изд., перераб. и доп. М.: Радио и связь, 1990. 496 с.: ил.

5. Баранов С. И. Синтез микропрограммных автоматов. Энергия. Ленинградское отделение. 1974 г. 184 с.

6. Цифровые и налоговые интегральные микросхемы: справочник под ред. С. В. Якубовского. - М.: Радио и связь, 1990. - 496 с.: ил.

7. Патент 2150740 (прототип).

8. А.С. СССР 1837327 (аналог).

9. А.С. СССР 1667097 (аналог).

10. А.С. СССР 1277091 (аналог).

Формула изобретения

Устройство поиска произвольных вхождений, содержащее блок памяти слов, блок памяти вхождений, компаратор, блок хранения адреса вхождений, блок управления, отличающееся тем, что дополнительно введены блок анализа и формирования сигналов сдвига, причем первый и второй управляющие входы блока управления соединены соответственно с первым и вторым управляющими выходами блока памяти вхождений, управляющий вход которого соединен с первым управляющим выходом блока управления, с первого по четвертый информационные выходы которого соединены соответственно с первым по четвертый информационными входами блока памяти вхождений, информационный выход которого соединен с первым информационным входом компаратора, управляющий выход которого соединен с первым управляющим входом блока анализа и формирования сигналов сдвига и с третьим управляющим входом блока управления, со второго по шестой управляющие выходы которого соединены соответственно со вторым по шестой управляющими входами блока анализа и формирования сигналов сдвига, первый и второй управляющие выходы которого соединены соответственно с четвертым и пятым управляющими входами блока управления, с тринадцатого по семнадцатый управляющие выходы которого соединены соответственно с одиннадцатым по седьмой управляющими входами блока анализа и формирования сигналов сдвига, информационный выход которого соединен с информационным входом блока хранения адреса вхождений, с первого по шестой управляющие входы которого соединены соответственно с седьмым по двенадцатый управляющими выходами блока управления, восемнадцатый управляющий выход которого соединен с управляющим входом блока памяти слов, с первого по четвертый информационные входы которого соединены соответственно с пятым по восьмой информационными выходами блока управления, восьмой управляющий вход которого соединен с управляющим выходом блока памяти слов, информационный выход которого соединен со вторым информационным входом компаратора, шестой и седьмой управляющие входы блока управления "СБРОС" и "ПУСК" являются внешними входами устройства.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7