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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 132551 51)4 06 Г 15/4 ИСАНИЕ ИЗОБРЕТЕНИЯ 3 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР В 1228116, кл. С 06 Р 15/40, 1984.Авторское свидетельство СССР В 1206810, кл. С 06 Г 15/40, 1984. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных. Цель изобретения - расширение функциональных возможностей уст-ройства за счет обеспечения нахождения записи с заданным признаком в бинарном дереве с произвольным размещением признаков в узлах. С этойцелью в устройство, содержащее группу элементов ИЛИ, группы элементовИ, регистры, блок памяти, элементзадержки, элемент И, дешифратор, элемент ИЛИ и генератор импульсов, введены три дешифратора, три элементаИЛИ, пять элементов И, группа элементов И, стековая память и распределитель импульсов, 1 ил.Каждый узел дерева занимает одну ячейку блока 33 памяти и состоит из полей данных (либо указателя на данные), признака левого, правого и об ратного указателей. Признак предназначен для идентификации данных, хранящихся в узле. Левый и правый ука" затели задают адреса узлов, следующих непосредственно за данным, а 45 обратный указатель - адрес предшествующего данному узлу. Произвольный узел может иметь пустой либо левый либо правый указателя. Пустой указатель задается кодом, расшифровывает- ВО ся дешифраторами 16, 18 и 19 и обозначается 9. Узел, в который не входит ни одно ребро, имеет пустой обратный указатель, а узлы, из которых не выходит ни одного ребра, содержат пустые левые и правые указатели. Устройство реализует поиск требуемого узла методом полного перебора в глу" бину. 1 13255Изобретение относится к вычислительной технике и может быть использовано в системах управления базамиданных.Цель изобретения " расширение5функциональных возможностей устройства за счет обеспечения нахождениязаписи с заданным признаком в бинарном дереве с произвольным размещением признаков в узлах,На чертеже приведена Функциональная схема устройства.Устройство содержит группу 1 элементов ИЛИ, группы 2-5 элементов И,элементы И 6-11, элементы ИЛИ 12-15,дешифраторы 16-19, элемент 20 сравнения, элемент 21 задержки, стековуюпамять (стек) 22, содержащую первый23 и второй 24 разряды, регистры 2527, разряды 28 данных и 29 признакалевого 30, правого 31 и обратного 32указателей регистра 27, блок 33 памяти, распределитель 34 импульсов, содержащий с первого по шестой выходы 2535-40, генератор 41 импульсов, грунпу 42 адресных входов устройства входы признака 43 и запуска 44 устройства, вход 45 признака конца работыустройства и информационные 46 выходы устройстваБинарное дерево представляет со,бой связный неориентированный граф,в котором из каждого узла выходитне более двух ребер.35 14 2Устройство работает следующим образом,В исходном состоянии генератор 41остановлен, выходы распределителя 34и стека 22 - нулевые. По группе 42входов в регистр 26 записывается адрес узла, в который не входит ни одно ребро, а по входу 43 в регистр25 - признак искомого узла. Устройство готово к работе,Цикл работы устройства состоит изшести тактов.Импульсом по входу 44 запускаетсягенератор 41, каждый такт определяется импульсом на соответствующем выходе распределителя 34. Если не найдентребуемый узел и дерево полностьюне просмотрено, начинается новыйцикл. В каждом цикле выполняются следующие действия,По импульсу 35 код узла дерева,адрес которого находится в регистре26, принимается в регистр 27, Признак этого узла сравнивается с признаком искомого узла, и в случае сравнения элемент 20 сравнения выцаетсигнал. Поля левого 30 и правого 31указателей анализируются дешифраторами 18 и 19 на И, при обнаружениикоторого эти. дешифраторы выдают сигналы,При появлении импульса 36, когданайден искомый узел, срабатывает элемент И 7, открывается группа 2 элементов И и искомые данные проходятна выход 46, генератор 41 останавливается, распределитель 34 и стек 22обнуляются. После обновления содержимого регистров 25 и 26 устройствоможет быть использовано повторно. В случае несравнения признаков на этом такте никаких операций не выполняется,По импульсу 37, если на выходе дешифратора 18 логическая единица (ле" вый указатель = 9), разряд 23 стека 22 устанавливается в единичное состояние. По импульсу 38, если на выходе дешифратора 19 логическая единйца (правый указатель = 9), разряд 24 стека 22 устанавливается в единичное состояние, Единицы в разрядах 23 и 24 запрещают выбор следующих за очередным узлов, если соответствующие указатели пустые.Если разряды 23 и 24 или разряд 23 находятся в нулевом состоянии, то появляется сигнал на первом выходе20 После этого по импульсу 35 начинается следующий цикл работы устройстваТаким образом, сначала осущест-.55 вляется просмотр дерева от узла, в который не входит ни одно ребро, только по левым указателям до тех пор, пока не будет найден искомый з 13255дешифратора 17, подготавливая к открытию группу 3 элементов И, Еслиразряд 23 в нулевом состоянии, тосигналом с второго выхода дешифратора 17 .подготавливается к открытию5группа 4 элементов И, Если разряды23 и 24 в единичном состоянии, тосигналом с третьего выхода дешифратора 17 подготавливается к открытию группа 5 элементов И.Импульсом 39 открывается одна изгрупп 3-5 элементов И, и код левого,правого или обратного указателей изрегистра 25 записывается в регистр26 и является адресом очередного узла в следующем цикле работы устройства. Если все указатели равны р (вседерево просмотрено), то на выходедешифратора 16 появляется сигнал,устанавливающий на входе 45 признакконца работы устройства, свидетельствуя об отсутствии в дереве узла с заданным признаком,По импульсу 40 срабатывает один 25из элементов И 6,8,9. На этом тактемодифицируется вершина стека в соответствии с принятым решением по дальнейшему просмотру дерева. Если срабатывает элемент И 8 (на предыщушем д 0такте выбран левый указатель), то через элемент ИЛИ 14 разряд 23 устанавливается в единичное состояние, а содержимое стека 22 погружается на одну ячейку. При этом в вершине стекаЗБпоявляется свободная обнуленная ячейка. В ней отражаются результаты анализа указателей узла, который прочитывается из блока 33 памяти в следующем цикле. Если срабатывает элементИ 6, то происходят аналогичные операции, но в единичное состояние устанавливается разряд 24. Если срабаты-.вает элемент И 9 (на предыдущем такте выбран обратный указатель), тосодержимое стека 22 выталкивается наодну ячейку вверх. Вершина стека 22отражает результаты анализа левого иправого указателей узла, а также результаты просмотра узлов, следующих50за ним. узел, либо не встретится пустой левый указатель.В первом случае устройство свои функции выполнило, во втором - осуществляется возврат на один шаг к предшествующему узлу и предпринимается попытка выбрать узел по правому указателю. Если правый указатель пустой, то снова осуществляется возврат на один шаг к предшествующему узлу, В противном случае выбирается узел по правому указателю и если он не является искомым, далее происходит просмотр дерева по левому указателю, если это возможно. В случае, когда в дереве узел с заданным признаком отсутствует, то после полного просмотра дерева осуществляется возврат к начальному узлу и при попытке выбрать предшествующий ему узел происходит остановка устройства с сигналом на выходе 45.Формула изобретенияУстройство для поиска информации, содержащее группу элементов ИЛИ, три группы элементов И, три регистра, блок памяти, элемент задержки, элемент сравнения, первый элемент И, первый дешифратор, первый элемент ИЛИ и генератор импульсов, вход которого является входом запуска устройства, группа адресных входов которого соединена с первыми входами элементов ИЛИ группы, выходы которых соединены с входами первого дешифратора и информационными входами первого регистра, выход которого соединен с адресным входом блока памяти, выход которого соединен с информационным входом второго регистра, выходы разрядов данных которого соединены с первыми входами элементов И первойгруппы, выходы которых являются информационными выходами устройства, вход признака которого соединен с информационным входом третьего регистра, выход которого соединен с первым входом элемента сравнения, второй вход которого соединен с выходом признака второго регистра, выходы разрядов левого и правого указате- лей которого соединены с первыми входами элементов И второй и третьей групп соответственно, выходы которых соединены с вторыми и третьими входами элементов ИЛИ группы соответ 5 13255 ственно, выход первого дешифратора является признаковым выходом устройства и соединен с первым входом первого элемента ИЛИ, выход которого соединен с входом останова генератора импульсов, выход элемента сравне" ния соединен с первым входом первого элемента И, выход которого соединен с вторыми входами элементов И первой группы и вторым входом перво го элемента ИЛИ, о т л и ч а ю щ е - е с я тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения нахождения записи с заданным признаком в бинар ном дереве с произвольным размещением признаков в узлах, оно содержит с второго по четвертый дешифраторы, с второго по четвертый элементы ИЛИ, с второго по шестой элементы И, чет вертую группу элементов И, стековую намять и распределитель импульсов, первый выход которого соединен с входом разрешения записи второго регистра, выходы разрядов левого и правого указателей которого соединены с входами второго и третьего дешифраторов, выходы которых соединены с первыми входами второго и третьего элементов И соответственно, выходы которых сое- ЗО динены с первыми входами второго и третьего элементов ИЛИ соответственно, выходы которых соединены с входами установки первого и второго разрядов стековой памяти, выход сброса 35 которой соединен с выходом первого 1 ч 6элемента ИЛИ,и входом сброса распределителя импульсов, второй выход которого соединен с вторым входом первого элемента И, вторые входы второго и третьего элементов И соединеныс третьим и четвертым выходами распределителя импульсов соответственно,выходы разрядов обратного указателявторого регистра соединены с первымивходами элементов И четвертой группы,выходы которых соединены с четвертымн входами элементов ИЛИ группы, выходы первого и второго разрядов сте-ковой памяти соединены с первым ивторым входами четвертого дешифратора, с первого по третий выходы которого соединены с первыми входами счетвертого по шестой элементов И со"ответственно и с вторыми входами элементов И с второй по четвертую группу соответственно, третьи входы которых соединены с пятым выходом распределителя импульсов, шестой выходкоторого соединен с вторыми входамис четвертого по шестой элементов И,выходы четвертого и пятого элементовИ соединены с вторыми входами второго и третьего элементов ИЛИ соответственно и с первым и вторым входомчетвертого элемента ИЛИ соответственно, выход .которого соединен с входомэлемента задержки, выход которого соединен с входом обратного сдвигастековой памяти, вход прямого сдвигакоторой соединен с выходом шестогоэлемента И.132554 оставитель Н,Мехред И.Попов твее И.Муска едактор В.Пе орре каз 3112/46 Тираж 672 НИИПИ Государственно по делам изобретени 13035, Москва, Ж, Подписио комитета СССРй и открытийРаушская наб., д П водственно-полиграфическое предприятие, г, Ужгород, ул. Проектная