Устройство для поиска информации Советский патент 1989 года по МПК G06F17/30 

1

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

. Цель изобретения повьшение быстродействия устройства за счет исключения дополнительной записи в стек,

На чертеже приведена схема устрой ства

Устройство содержит группу 1 элементов ИЛИ, группы 2-6 элементов И, элемент И 7, элементы ИЛИ 8 и 9, дешифраторы 10-12 левого, правого и обратного указателей,, дешифратор 13 состояния узла, компаратор 14, элемент 15 задержки, стёк 16, старший разряд 17 и младший разряд 18 вершины стека, регистр 19 ключа, регистр 20 адреса, регистр 21 информации, регистр поля 22 данных, per гистр 23 ключа, регистр 24 левого. указателя, регистр 25 гфавого указателя, регистр 26 обратного указа- теля регистра информации, блок 27 памяти, распределитель 28 импульсов генератор 29 импульсов, группу 30 адресных входов, группу 31 входов ключа, вход 32 запуска, группу 33 информационных выходов и выход 34 признака конца работы устройства. Позшдиями 35-39 обозначены входы, а позициями 40-43 - выходы дешифратора 13.

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

5 О

Q

5

ни одна дуга, назьшаются листьями дерева.

Код каждого узла дерева занимает одну ячейку блока 27 памяти и состоит из следующих полей; данных (либо поля указателя на данные), ключа (для идентификации узла), левого, правого и обратного указателей. Левый и правый указатели задают адреса кодов непосредственных потомков данного узла, а обратньш указатель - адрес непосредственного- предка данного узла. Корень дерева имеет пустой обратньш указателе и непустые левый и/или правый указатели. Каждый лист дерева содержит пустые левый и правый указатели и непустой обратньй указатель. Остальные узлы дерева имет непустые левьй и/или правьй указатели и непустой обрат- НЕлй указатель. Пустой указатель представляется уникальным кодом, распознаваемым дешифраторами 10-12, и обозначается через 0„

Возможные комбинации сигналов на входах дешифратора 13 и соответствующие им сигналы на выходах приведены в таблице.

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

В исходном состоянии генератор 29 импульсов заторможен; распределит тель 28 импульсов установлен в исходное состояние (ни на одном из его выходов сигнал не появляется)j стек 16 также установлен в исходное состояние (все ячейки обнулены), Цепь установки устройства в исходное состояние на схеме не показана. По группе 30 входов через группу 1 элементов ИЛИ в регистр 20 записывается адрес корня дерева, в котором будет осуществляться поиск, а по группе 31 входов в регистр 19 заносится код ключа искомого узла. Устройство готово к работе.

Поиск информации инициируется подачей импульса по входу 32, в ре зультате чего запускается генератор 29, который начинает выдавать импульсы тактовой частоты. Эти импульсы рассылаются распределителем 28 по управляющим точкам устройства. Работа устройства заключается в последовательном выполнении циклов, каждый из которых состоит из двух тактов. Первый такт определяется импульсом на первом выходе, а второй - на втором выходе распределителя 28.

По импульсу с первого выхода распределителя 28 код узла дерева, адрес которого находится в регистре 20 принимается в регистр 21.-Ключ этого узла посредством компаратора 14 сравнивается с ключом искомого узла, который хранится в регистре 19. В случае совпадения компаратор 14 выдает сигнал. Одновременно с этим поля левого указателя 24, правого указателя 25 и обратного указателя 26 анализируются дешифраторами 10-12 на 0. При обнаружении этого признака соответствующие дешифраторы 1012вьщают сигналы. При отсутствии

0 в каком-либо поле на выходе соот- ветствующего дешифратора сигнал не появляется. Дешифратор 13 анализирует состояние очередной (находящейся в регистре 21) вершины дерева, включающее сведения о прёдьщущих просмотрах текущего узла (разряды 17 к 18 вершины стека) и о пустых указателях данной вершины.

В каждом дикле поиска для дальнейшего просмотра будет выбран самый левый из еще не выбиравшихся указателей, если он существует. Если упомянутого указателя нет, то осуществляется возврат к непосредственному предку текущего узла. Так, если вершина стека 16 обнулена (т,е, очередной узел прочитан из блока 27 памяти первый раз), то дешифратор

13находит самый левый непустой указатель. В случае, когда таковым является севый указатель, то появляется сигнал на выходе 40, а если правый - то на выходе 41 дешифратора t3. Если же левый и правый указатели пустые, то появляется сигнал на выходе

10

5

0

42, а если все указатели пустые - то на выходе 43 дешифратора 13. Сигнал на выходе 40 определяет в последующем просмотр по левому указателю, на выходе 41 - по правому указателю, а на выходе 42 - по обратному указателю. Сигнал на выходе 43 свидетельствует об окончании просмотра дерева.

При просмотре дерева каждый его узел может выбираться от нуля до двух раз. Количество просмотров каждого узла фиксируетсй в соответствующих ячейках стека 16. Если в его вершине находится код числа 1 (разряд 17 обнулен, а разряд 18 установлен в единичное состояние) то это означает, что очередной узел прочитан из блока 27 памяти второй раз, т.е. что по самому левому непустому указателю просмотр уже произведен. В этом случае для дальнейшего просмотра нужно выбрать второй слева не- ° пустой указатель, если он существу- 5 ет, что и определяется дешифратором 13. Если в вершине стека 16 находится код числа 2 (разряд 17 установлен в единичное состояние, а разряд 18 обнулен), то это означает, что очередной узел прочитан из блока 27 памяти третий раз, т.е. что по левому и правому указателям просмотр дерева уже произведен. В этом случае для дальнейшего просмотра нужно выбирать обратньй указатель, если он не пуст. . В противном случае просмотр дерева завершен.

По импульсу на втором выходе распределителя 28 в случае, когда в регистре 21 находится искомый узел, срабатывает элемент И 7, в результате чего открывается группа 2 элементов И и искомые данные проходят на группу 33 выходов. Кроме.того, появляется импульс на выходе элемента ИЛИ 8, устанавливая устройство в исходное состояние. После обновления содержимого регистров 2 и/или 19 оно снова может быть запущено в работу. Одновременно с этим открывается группа 3 элементов И, в результате чего выбранный для дальнейшего просмотра указатель через одну из групп 4-6 элементов И и группу 1 элементов ИЛИ переписывается в регистр 20. Кроме того, обновляется содержимое стека 16. Если для дальнейшего просмотра выбран левьй или правый указатель, то появляется импульс (га

0

5

0

5

0

5

5

выходе элемента lUTO З который увеличивает содержимое эерЕгяны стека 16 на единицу, С задержкой необходимой для окончания переходньк процессов, содержимое стека 16 проталкивается (погружается) на одну ячейку рниз При этом в верыине стека 16 появляется свободная обнуленная ячейка, выделяемая узла, который будет про-читаи из блока 27 памяти в следугоЕ м цикле« Если же для дальнейшего просмотра .выбран обратный указатель.) то осущесгв ляется выталкивание содержзшого стека 16 на одну ячейку пзерх.:. При этом его вершина теряется,

После этого по И1ч:гг/льсу на пер вом выходе распределитэгя 28 начинается следующий цикл рабсть5 устрой- ства. Таким образоМэ устройство реализует алгоритм поиск э. з глубину, Сначала осуществляется просмотр рева от-корня только по левьм -указателям до тех пор, пока не будет найден искомьй узел, либо не встретится левый пустой указатель,. В первом случае считается,, что устройство свои функции выполнило„ Во вг: ором случае предпринимается попытка выбрать узел по правому указателю. Если правый: указатель пустой,, осуществляется возврат к непосредственному предку и предпринш 1ается попь::т :а поиска, по самому левому из еще i;:e выбиравшихся указателей. Если же правый указатель непустой,, то ана погично описанному -просматривается поддеревоg корень которого задается этим указателем, В случаеэ когда в дереве узел с заданным ключом отсутствует,; после полного просмотра дерева осуществлл™ ется возврат к корню и при выбрать его предка происходит оста™ новка устройства с на выходе 34.

Если дерево являе ся вырожден:яым (т.е. состоит из одного узла) и ключ этого узла назсодйтся :з регистре 195 то за один цикл работы устройства происходит одновреме г. зьщача яя 22 на группу 33 выходов и сигнала об отсутств.ш искоюго узла на в ход 34, Разрешить это г кон1|шикт можно двумя способамиj; захфетить использовать вырохзденные деревьяg от™ дать 11риоритет коду на группе 33 вы ходов внешним до отноше.нию к предло женному устройством

14

641736

В случае невырожденного дерева рассмотренная ситуация невозможна, так как до полного просмотра дерева его корень будет считан не менее одного раза Поэтому, если он является искомым узлом5 то работа устройства завершается успешно до этого момента (а точнее - на первом шаге),

Фор

У

а

изобретения

0

Устройство для поиска информации, содержгицее группу элементов ИЛИ, пять групп элементов И, элемент И, два элемента ИЛИ, дешифратор левого указателя, дешифратор правого указателя,, ..дешифратор обратного указате- ляд дешифратор состояния узла, ком- „ napaTopj элемент задержки, стек, регистр ключа, регистр адреса, регистр информации, блок памяти,, распределитель и 1пульсов и генератор импульсов, выход которого соединен с управля--: 5 ющим входом распределителя импульсов, первьй выход которого соединен с синхронизирующим входом регистра информации, входы которого соединены с выxoдa {и блока памяти, входы коюрого соединены с выходами регистра адреса, входы которого соедия йены с вь)ходами группы: элементов ИЛИ, первая группа входов которой является группой адресных входов устройства, вход запуска которого соединен с входом запуска генератора импульсов, вход останова.которого соединен с установочными входами распределителя импульсов и стека.-.и с выходом первого элемента ИЛИ, первый вход которого соединен с выходом признака конца работы устройства группа, входов ключа которого соединена с входаз и регистра ключа, выходы которого соединены с первой rpyji- пой входов компаратора, вторая па входов которого соединена с выхо-, дами поля ключа регистра информации, .:8ьшоды поля данных которого соединены с инфор1 1ационнш-1и входами первой группы элементов И выходы которой являются группой информационньк выходов устройства, выход компаратора соединен с первым входом элемента И, выход которого соединен с вторым входом первого элемента ИЛИ и с уп- равляю:щ:им входом первой группы элементов И, второй вход элемента И соединен с вторым вькодом распреде5

0

45

55

1464

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

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

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

счетчик и выход второго элемента ИЛИ соединен со счетным входом вершинь

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

Изобретение относится к вьгчис- 1ительной технике и может быть использовано в системах управления баг замк данных. Цель изобретения - по- вьшение быстродействия устройства за счет исключения дополнительной: