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

(57) ганк лител ССС198СР198 аль за с ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕ(56) Авторское свидетельствоР 1228116, кл. С 06 Г 15/40,Авторское свидетельство СВ 1325514, кл, С 06 Р 15/40,ЯО 1464173 Изобретение отньной технике иовано в системаданных. Цель изие быстродействет исключения д осится к вычисможет быть нс=х управления баобретения - поя устройстваополнительной1464173 записи В стек, Для достижения указанной цели в устройство, содержащеегруппу 1 элементов ИЛИ, пять групп2-6 элементов И, элемент И 7, дваэлемента ИЛИ 8, 9, дешифратор 10 левого указателя, дешифратор 11 правого указателя, дешифратор 12 обратного указателя, дешифратор 13 состояИзобретение относится к вычислительной технике и может быть использовано в системах управления базамиданньгх,. Цель изобретения - повьппениебыстродействия устройства за счет исключения дополнительной записи встек.На чертеже приведена схема устройства.Устройство содержит группу 1 элементов ИЛИ, группы 2-6 элементов И,элемент И 7, элементы ИЛИ 8 и 9,дешифраторы 10-12 левого, правого иобратного указателей, дешифратор 13состояния узла, компаратор 14,элемент 15 задержки, стек 16, старший разряд 17 и младший разряд 18 .вершины стека, регистр 19 ключа,регистр 20 адреса, регистр 21 информации, регистр поля 22 данных, ре-.гистр 23 ключа, регистр 24 левогоуказателя, регистр 25 правого указателя, .регистр 26 обратного указателя регистра информации, блок 27памяти, распределитель 28 импульсов,генератор 29 импульсов, группу 30адресных входов, группу 31 входовключа, вход 32 запуска, группу 33информационных выходов и выход 34признака конца работы устройства.Позициями 35-39 обозначены входы,а позициями 40-43 - вьпходы дешифратора 13.Бинарное дерево представляет собой связный ориентированный граф,в котором в каждый узел входит неболее одной дугиа выходит не болеедвух. Узел, в который не входитни одна дуга, называется корнем дерева (корень в дерезе всегда единственен), Узлы, из которых не выходит 5 10 15 20 25 30 35 40 ния узла, компаратор 14, элемент 15задержки, стек 16, реги"тр 19 ключа,регистр 20 адреса, регистр 21 информации, блок 27 памяти распределитель 28 импульсов и генератор 29 импульсов, дополнительно введено построение ячеек стека на счетчиках.1 ил., 1 табл. ни одна дуга, называются листьямидерева.Код каждого узла дерева занимаетодну ячейку блока 27 памяти и состоит из следующих полеи: данных(либо поля указателя на данные),ключа (для идентификации узла), левого, правого и обратного указателей.Левый и правый указатели задают адреса кодов непосредственных потомковданного узла, а обратный указатель -адрес непосредственногс предка данного узла, Корень дерева имеет пустой обратный указателю и непустыелевый и/или правый указатели, Каждый лист дерева содержит пустые левый и правый указатели и непустойобратный указатель. Остальные узлыдерева имет непустые левый и/или .правый указатели и непустой обратный указатель. Пустой указательпредставляется уникальным кодом,распознаваемым дешифраторами 10-12,и обозначается через 9Возможные комбинации сигналов навходах дешифратора 13 и соответствующие им сигналы на выходах приведеныв таблице,Устройство работает следующим образом.В исходном состоянии генератор29 импульсов заторможен; распредели-.тель 28 импульсов установлен в исходное состояние (ни на одном из еговыходов сигнал не появляется); стек16 также установлен в исходное состояние (все ячейки обнулены). Цепьустановки устройства в исходное состояние на схеме не показана. Погруппе 30 входов через группу 1 элементов ИЛИ в регистр 20 записывается адрес корня дерева, в котором бу 1464173дет осуществляться поиск, а по группе 31 входов в регистр 19 заносится код ключа искомого узла. Устройство готово к работе.Поиск информации инициируется по-. дачей импульса по входу 32, в результате чего запускается генератор 29, который начинает выдавать импульсы тактовой частоты, Эти им" пульсы рассылаются распределителем 28 по управляющим точкам устройства. Работа устройства заключается в последовательном выполнении циклов, каждый из которых состоит из двух так тов, Первый такт определяется импульсом на первом выходе, а второй - на втором выходе распределителя 28.По импульсу с первого выхода распределителя 28 код узла дерева, адрес которого находится в регистре 20, принимается в регистр 21. Ключ этого узла посредством компаратора 14 сравнивается с ключом искомого узла, который хранится в регистре 19. В 25случае совпадения компаратор 14 выдает сигнал. Одновременно с этим поля левого указателя 24, правого указателя 25 и обратного указателя 26 анализируются дешифраторами 10-12 30 на 9. При обнаружении этого признака соответствующие дешифраторы 10- 12 выдают сигналы. При отсутствии9 в каком-либо поле на выходе соответствующего дешифратора сигнал не появляется. Дешифратор 13 анализирует состояние очередной (находящейся в регистре 21) вершины дерева, включающее сведения о предыдущих просмотрах текущего узла (Разряды 17 40 и 18 вершины стека) и о пустых указателях данкой вершины.В каждом ,цикле поиска для дальнейшего просмотра будет выбран самый левый из еще не выбиравшихся указателей, если он существует, Если упомянутого указателя нет, то осуществляется возврат к непосредственному предку текущего узла. Так, если вершина стека 16 обнулена (т.е. очередной узел прочитан из блока 27 памяти первый раз), то дешифратор 13 находит самый левый непустой указатель. В случае, когда таковым является левый указатель, то появляется сигнал на выходе 40, а если правый - то на выходе 41 дешифратора 13. Если же левый и правый указатели пустые, то появляется сигнал на выходе 42, а если все указатели пустые - то ка выходе 43 дешифратора 13. Сигнал на выходе 40 определяет в последующем просмотр по левому указателю, на выходе 41 " по правому указатепо, а на выходе 42 - по обратному указателю. Сигнал на выходе 43 свидетельствует об окончании просмотра дерева,При просмотре дерева каждый его узел может выбираться от нуля до двух раэ, Количество просмотров каждого узла фиксируется в соответствующих ячейках стека 16. Если в его вершине находится код числа 1 (разряд 17 обнулен а разряд 18 установлен в единичное состояние) то это означает, что очередной узел прочитан из блока 27 памятивторой раз, т,е, что по самому левому непустому указателю просмотр уже произведен. В этом случае для дальнейшего просмотра нужно выбрать второй слева не- ф пустой указатель, если он существует, что и определяется дешифратором 13. Если в вершине стека 16 находится код числа 2 (разряд 17 установлен в единичное состояние, а разряд 18 обнулен), то это означает, что очередной узел прочитан из блока 27 памяти третий раз, т.е, что по левому и правому указателям просмотр дерева уже произведен. В этом случае для дальнейшего просмотра нужно выбирать обратный указатель, если сн не пуст. В противном случае просмотр дерева завершен.По импульсу на втором выходе распределителя 28 в случае, когда в регистре 21 находится искомый узел, срабатывает элемент И 7, в результа.те чего открывается группа 2 элементов И и искомые данные проходят на группу 33 выходов. Кроме того, появляется импульс на выходе элемента ИЛИ 8, устанавливая устройство в исходное состояние. После обновления содержимого регистров 2 и/или 19 оно снова может быть запущено в работу. Одновременно с этим открывается группа 3 элементов И, в результате чего выбранный для дальнейшего просмотра указатель через одну из групп 4-6 элементов И и группу 1 элемен" тов ИЛИ переписывается в регистр 20, Кроме того, обновляется содержимое стека 16. Если для дальнейшего просмотра выбран левый или правый указатель, то появляется импульс навыходе элемента ИЛИ Э, который увеличивает содержимое Верцны стека1 б на единицу, С задеря:кой, необходимой для окончания переходных процессов, содержимое стека 16 проталкивается (погружается) на одну ячейкуВниз, При этом В вершине стека 1 бпоявляется свободная обнуленнаяячейка, выделяемая для спедующегоузла который будет прочитан из блока 27 памяти в следующем цикле, Если же дяя дапьнейшего просмотра Выбран обратный указатель то осуществляется выталкивание содержимого сте.ка 1 б на одну ячейку пзерх При этомего вершина теряется.ПОсле этого пс иму,ьсу на 1 ер"Вом Вьходе распределителя 28 нац.".нается следующий цикл работы устройства. Такм образом, ," тройство раализует алгоритм поиск в глубину,Сначала осуществляется просмотр де."рева от корня только по левым указателям до тех пор, пока :е будет най- рден искомый узел, либо не встретится левый пустой указаель,.В первомслучае считаетсячто устройство своифункции вь"полнило, Во в Ором случаепредпринимается попытка выбрать узеппо правому указа елю. Если правьн".:указатель пусто:"1. то осуществляе 1 сявозврат к непосредственному предкуи предпринимается пэьтка поиска посамому левому из еще 1:е вь.биравшихся указателей, Если жс равый указатель непустой то ааогично описанному просматривает:.я поддерево,корень которого загается этим указателем, В случае, когда в дереве узелс заданным ключом ото тствует, послеполного просмотра дерева о ушеств 1 яется возврат к корню и при попыткевыбрать его предка происходит оста=нОВка устройства с си."Налом ка Вьхо-де 34.Если дерево является вырожденным(т.е. состоит из однос узла) и ключэтого узла находится з регистре 19,то за, один цикл работы устройствапроисходит одновреме.:а:я вь 1 дача по ля 22 на группу 33 вькодов и сигнала Об Отсутствии Рсолого узла на выход 34, Разрешить этот конфликт можно двумя способам запретить использовать вьгрожден 1 ь.с деревья; отдать приоритет коду на группе 33 выходОВ Внешним по Отношени 0 к предлО":женному устройством, В случае невырожденного дерева рассмотренная ситуация невозможна, так как до полного просмотра дерева его корень будет считан не менее Одного раза. Поэтому, если он является искомым узлом, то работа устройства завершается успешно до этого момента (а точнее - на первом шаге).с формула изобретения Устройство для поиска информации, содержащее группу элементов ИЛИ, пять груп элементов И, элемент И, два элемента ИЛИ, деифратор левого указателя, дешифратор правого ука. зателя дешифратор обратного указателя, дешифратор состояния узла, компаратор, элемент задержки, стек, регистр ключа, регистр адреса, регистр информации блок памяти, распределитель импульсов и генератор импульсов, выхоц которого соединен с управля-. ющим входом распределителя импульсов, первый выход которого соединен с синхронизирующим вхоцом регистра информации входы которого соединены с вь;ходами блока памяти, входы коорого соединены с выходами регистра адреса, входы которого соеди иены с выходами группы элементов ИЛИ, первая группа входов которой является группой адресных входов устройства, вход запуска которого соединен с входом запуска генератора импульсов, вход останова которого соедичен с установочными входами распределителя импульсов и стека.и с выходом первого элемента ИЛИ, первый вход которого соединен с выходом признака конца работы устройства, группа входов ключа которого соединена с входами регистра ключа, выходы которого соединены с первой груп- . пой входов компаратора, вторая груп па входов которого соединена с выхо- . дами поля ключа регистра информации, выходы поля данных которого соединены с информационными входами первой группь элементов И, выходы которой являются группой информационных выходов устройства, выход компаратора соединен с первым входом элемента И, выход которого соединен с вторым входом первого элемента ИЛИ и с управляющим входом первой группы элементов И, второй вход элемента И соединен с вторым Выходом распреде7 14641 лителя импульсов, выходы полей левого, правого и обратного указателей регистра информации соединены с информационными входами второй, третьей и четвертой групп элементов И соответственно, выходы которых соединены с второй, третьей и четвертой группами входов группы элементов ИЛИ соответственно, выходы полей левого и правого указателей регистра информации соединены с входами дешифраторов левого и правого указателей соответственно, выходы старшего и младшего разрядов вершины стека соединены с первым и вторым входами де" шифратора состояния узла соответственно, первый, второй и третий выходы которого соединены с первым, вторым и третьим информационными входами пятой группы элементов И соответственно, первый, второй и третий выходы которой соединены с первым и вторым входами второго элемента ИЛИ и с входом прямого сдвига стека 25 73 Вьп оды 40 41 42 43 35 36 37 38 39 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 0 О 1 0 0 1 0 00 0 1 0 1 0 0 1 О 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 0 О О 0 О 1О О 0 0 1 1 0 1 1 0 0 01 0 1 1 О О 0 10 0 0 1 соответстеенно,выход второго элементаИЛИ соединен с входом прямого сдвигастека,о т л и ч а ющ е е с я тем, что,с целью повышения быстродействия засчет устранения промежуточной записи в стек ячейками стека являютсясчетчик и выход второго элемента ИЛсоединен со счетным входом вершиныстека, выходы дешифраторов левого,правого и обратного указателей соединены с третьим, четвертым и пятымвходами дешифратора состояния узла ,соответственно, четвертый выход которого соединен с четвертым информаци"онным входом пятой групг элементовИ, первый, второй и третий выходыкоторой соединены с управляющими входами второй, третьей и четвертойгрупп элементов И соответственно,второй выход распределителя импульсовсоединен с управляющим входом пятойгруппы элементов И, четвертый выходкоторой соединен с первым входом первого элемента ИЛИ. 1 0 0 0 1 0 О О0 0 0 1 0 0 0 0 1 0 0 О 1 О 0 0 0 1 0 0 0 0 0О 0 00 0 0 0 1 0 О 0 1 О 0 О 0 1 О 0О 0 . О 0 1