Устройство для поиска информации

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1325514 А1 (51)4 06 F 15/40

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 4033287/24-24 (22) 07.03.86 (46) 23.07.87. Бюл. Р 27 (72) Б.С.Богумирский (53) 681.325(088.8) (56) Авторское свидетельство СССР

9 1228116, кл. С 06 F 15/40, 1984.

Авторское свидетельство СССР

9 1206810, кл. С 06 F 15/40, 1984. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных. Цель изобретения — расширение функциональных возможностей уст- ройства за счет обеспечения нахождения записи с заданным признаком в бинарном дереве с произвольным размещением признаков в узлах. С этой целью в устройство, содержащее группу элементов ИЛИ, группы элементов

И., регистры, блок памяти, элемент задержки, элемент И, дешифратор, элемент ИЛИ и генератор импульсов, введены три дешифратора, три элемента

ИЛИ, пять элементов И, группа элементов И, стековая память и распределитель импульсов. 1 ил.

Каждый узел дерева занимает одну ячейку блока 33 памяти и состоит из полей данных (либо указателя на данные), признака левого, правого и об- 40 ратного указателей. Признак предназначен для идентификации данных, хранящихся в узле. Левый и правый указатели задают адреса узлов, следующих непосредственно за данным, а 45 обратный указатель — адрес предшествующего данному узлу. Произвольный узел может иметь пустой либо левый„ либо правый указателя. Пустой указатель задается кодом, расшифровывает- В0 ся дешифраторами 16, 18 и 19 и обозначается 9. Узел, в который не входит ни одно ребро, имеет пустой обратный указатель, а узлы, из которых не выходит ни одного ребра, содержат пустые левые и правые указатели. Устройство реализует поиск требуемого узла методом полного перебора в глубину.! 13255

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

Цель изобретения - расширение

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

На чертеже приведена функциональная схема устройства.

Устройство содержит группу 1 элементов ИЛИ, группы 2-5 элементов И, элементы И 6-11, элементы ИЛИ 12-15, дешифраторы 16-19, .элемент 20 сравнения, элемент 21 задержки, стековую память (стек) 22, содержащую первый

23 и второй 24 разряды, регистры 2527, разряды 28 данных и 29 признака левого 30, правого 31 и обратного 32 указателей регистра 27, блок 33 памяти, распределитель 34 импульсов, содержащий с первого по шестой выходы 25

35-40, генератор 41 импульсов, группу 42 адресных входов устройства входы признака 43 и запуска 44 устройства, вход 45 признака конца работы устройства и информационные 46 выходы устройства.Бинарное дерево представляет со,бой связный неориентированный граф, в котором из каждого узла выходит не более двух ребер.

l4 2

Устройство работает следующим образом.

В исходном состоянии генератор 41 остановлен, выходы распределителя 34 и стека 22 — нулевые. По группе 42 входов в регистр 26 записывается адрес узла, в который не входит ни одно ребро, а по входу 43 в регистр

25 — признак искомого узла. Устройство готово к работе °

Цикл работы устройства состоит из шести тактов.

Импульсом по входу 44 запускается генератор 41, каждый такт определяется импульсом на соответствующем выходе распределителя 34. Если не найден требуемый узел и дерево полностью не просмотрено, начинается новый цикл. В каждом цикле выполняются следующие действия.

По импулт су 35 код узла дер ев а, адрес которого находится в регистре

26, принимается в регистр 27. Признак этого узла сравнивается с признаком искомого узла, и в случае сравнения элемент 20 сравнения выцает сигнал. Поля левого 30 и правого 31 указателей анализируются дешифраторами 18 и 19 на 9, при обнаружении которого эти. дешифраторы выдают сигналы.

При появлении импульса 36, когда найден искомый узел, срабатывает элемент И 7, открывается группа 2 элементов И и искомые данные проходят на выход 46, генератор 41 останавливается, распределитель 34 и стек 22 обнуляются. После обновления содержимого регистров 25 и 26 устройство может быть использовано повторно.

В случае несравнения признаков на этом такте никаких операций не выполняется.

По импульсу 37, если на выходе дешифратора 18 логическая единица (левый указатель = 9), разряд 23 стека

22 устанавливается в единичное состояние. По импульсу 38, если на вьтходе дешифратора 19 логическая единйца (правый указатель = 9), разряд 24 стека 22 устанавливается в единичное состояние. Единицы в разрядах 23 и

24 запрещают выбор следующих за очередным узлов, если соответствующие указатели пустые.

Если разряды 23 и 24 или разряд

23 находятся в нулевом состоянии, то появляется сигнал на первом выходе

После этого по импульсу 35 начинается следующий цикл работы устройства ° Таким образом, сначала осущест-.

55 вляется просмотр дерева от узла, в который не входит ни одно ребро, только по левым указателям до тех пор, пока не будет найден искомый з 13255 дешифратора 17, подготавливая к открытию группу 3 элементов И. Если разряд 23 в нулевом состоянии, то сигналом с второго выхода дешифратора 17 -подготавливается к открытию

5 группа 4 элементов И. Если разряды

23 и 24 в единичном состоянии, то сигналом с третьего выхода дешифра тора 17 подготавливается к открытию группа 5 элементов И.

Импульсом 39 открывается одна из групп 3-5 элементов И, и код левого, правого или обратного указателей из регистра 25 записывается в регистр

26 и является адресом очередного узла в следующем цикле работы устройства. Если все указатели равны Р {все дерево просмотрено), то на выходе дешифратора 16 появляется сигнал, устанавливающий на входе 45 признак конца работы устройства, свидетельствуя об отсутствии в дереве узла с заданным признаком.

По импульсу 40 срабатывает один из элементов И 6,8,9. На этом такте модифицируется вершина стека в соответствии с принятым решением по дальнейшему просмотру дерева. Если срабатывает элемент И 8 {на предыщушем д0 такте выбран левый указатель), то через элемент ИЛИ 14 разряд 23 устанавливается в единичное состояние, а содержимое стека 22 погружается на одну ячейку. При этом в вершине стека

35 появляется свободная обнуленная ячейка. В ней отражаются результаты анализа указателей узла, который прочитывается из блока 33 памяти в следующем цикле. Если срабатывает элемент

И 6, то происходят аналогичные операции, но в единичное состояние устанавливается разряд 24. Если срабаты-. вает элемент И 9 {на предыдущем такте выбран обратный указатель), то содержимое стека 22 выталкивается на одну ячейку вверх. Вершина стека 22 отражает результаты анализа левого и правого указателей узла, а также результаты просмотра узлов, следующих

50 за ним. узел, либо не встретится пустой левый указатель.

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

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

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

Устройство для поиска информации, содержащее группу элементов ИЛИ, три группы элементов И, три регистра, блок памяти, элемент задержки, элемент сравнения, первый элемент И, первый дешифратор, первый элемент

ИЛИ и генератор импульсов, вход которого является входом запуска устройства, группа адресных входов которого соединена с первыми входами элементов ИЛИ группы, выходы которых соединены с входами первого дешифратора и информационными входами первого регистра, выход которого соединен с адресным входом блока памяти, выход которого соединен с информационным входом второго регистра, выходы разрядов данных которого соединены с первыми входами элементов И первой группы, выходы которых являются информационными выходами устройства, вход признака которого соединен с информационным входом третьего регистра, выход которого соединен с первым входом элемента сравнения, второй вход которого соединен с выходом признака второго регистра, выходы разрядов левого и правого указате- лей которого соединены с первыми входами элементов И второй и третьей групп соответственно, выходы которых соединены с вторыми и третьими входами элементов ИЛИ группы соответ5 13255 ственно, выход первого дешифратора является признаковым выходом устройства и соединен с первым входом первого элемента ИЛИ, выход которого соединен с входом останова генератора импульсов, выход элемента сравнения соединен с первым входом первого элемента И, выход которого соединен с вторыми входами элементов И первой группы и вторым входом первого элемента ИЛИ, о т л и ч а ю щ е— е с я тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения нахождения записи с заданным признаком в бинар - 15 ном дереве с произвольным размещением признаков в узлах, оно содержит с второго по четвертый дешифраторы, с второго по четвертый элементы ИЛИ, с второго по шестой элементы И, чет- 20 вертую группу элементов И, стековую амять и распределитель импульсов, первый выход которого соединен с входом разрешения записи второго регистра, выходы разрядов левого и правого указателей которого соединены с входами второго и третьего дешифраторов, выходы которых соединены с первыми входами второго и третьего элементов

И соответственно, выходы которых сое- ЗО динены с первыми входами второго и третьего элементов ИЛИ соответственно, выходы которых соединены с входами установки первого и второго разрядов стековой памяти, выход сбро< а 35 которой соединен с выходом первого

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

И соединены с вторыми входами второго и третьего элементов ИЛИ соответственно и с первым и вторым входом четвертого элемента ИЛИ соответствен-! но, выход .которого соединен с входом

< элемента задержки, выход которого соединен с входом обратного сдвига стековой памяти, вход прямого сдвига которой соединен с выходом шестого элемента И.

1325514

Составитель Н.Матвеев

Техред И.Попович

Редактор В.Петраш

Корректор И.Муска

Заказ 3112/46

Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4