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

 

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

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

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

РЕСПУБЛИК

Al (5 ) 4 G 06 F 15j40

50KMl33A3

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4173539/24-24 (22) 14.11.86 (46) 07.03.89. Бюл. № 9 (72) Б.С.Бугумирский и В.М.Цыганков (53) 681. 3 (088.8) (56) Авторское свидетельство СССР № 1228116, кл. G 06 Р 15t40, 1984.

Авторское свидетельство СССР № 1325514, кл. G -06 Р 15/40, 1985.

„„SU „„3464173 (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике и может быть ис= пользовано в системах управления ба» зами данных. Цель изобретения — повышение быстродействия устройства за счет исключения дополнительной..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

1 адресных входов, группу 31 входов ключа, вход 32 запуска, группу 33 информационных выходов и выход 34 признака конца работы устройства.

Позициями 35-39 обозначены входы, а позициями 40-43 — вьпходы дешифратора 13.

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

10 15

40 ния узла, компаратор 14, элемент 15 задержки, стек 16, реги"тр 19 ключа, регистр 20 адреса, регистр 21 информации, блок 27 памяти„ распределитель 28 импульсов и генератор 29 импульсов, дополнительно введено построение ячеек стека на счетчиках.

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

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

Левый и правый указатели задают адреса кодов непосредственных потомков данного узла, а обратный указатель— адрес непосредственногс предка данного узла. Корень дерева имеет пустой обратный указателю и непустые левый и/или правый указатели, Каждый лист дерева содержит пустые левый и правый указатели и непустой обратный указатель. Остальные узлы дерева имет непустые левый и/или . правый указатели и непустой обратный указатель. Пустой указатель представляется уникальным кодом, распознаваемым дешифраторами 10-12, и обозначается через 9„

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

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

В исходном состоянии генератор

29 импульсов заторможен; распредели-. тель 28 импульсов установлен в исходное состояние (ни на одном из его выходов сигнал не появляется); стек

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

Поиск информации инициируется по-. дачей импульса по входу 32, в результате чего запускается генератор

29, который начинает выдавать импульсы тактовой частоты, Эти импульсы рассылаются распределителем

28 по управляющим точкам устройства.

Работа устройства заключается в последовательном выполнении циклов, каждый из которых состоит иэ двух так- 15 тов. Первый такт определяется импульсом на первом выходе, а второй — на втором выходе распределителя 28.

По импульсу с первого выхода распределителя 28 код узла дерева, ад- 20 рес которого находится в регистре 20, принимается в регистр 21. Ключ зтого узла посредством компаратора 14 сравнивается с ключом искомого узла, который хранится в регистре 19. В 25 случае совпадения компаратор 14 вы" дает сигнал. Одновременно с этим поля левого указателя 24, правого указателя 25 и обратного указателя 26 анализируются дешифраторами 10-12 30 на 9. При обнаружении этого признака соответствующие дешифраторы f0f2 выдают сигналы. При отсутствии g в каком-либо поле на выходе соот ветствующего дешифратора сигнал не появляется. Дешифратор 13 анализирует состояние очередной (находящейся в регистре 21) вершины дерева, включающее сведения о предыдущих просмотрах текущего узла (разряды 17 40 и 18 вершины стека) и о пустых указателях данкой вершины.

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

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

Если же левый и правый указатели пустые, то появляется сигнал на выходе

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

При просмотре дерева каждый его узел может выбираться от нуля до двух раэ. Количество просмотров каждого узла фиксируется в соответствующих ячейках стека 16. Если в его вершине находится код числа 1 (разряд

i7 обнулен а разряд 18 установлен в единичное состояние) то это означает, что очередной узел прочитан из блока 27 памяти второй раз, т.е. что по самому левому непустому указателю просмотр уже произведен. В этом случае для дальнейшего просмотра нужно выбрать второй слева непустой указатель, если он существует, что и определяется дешифратором

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

В противном случае просмотр дерева завершен.

По импульсу на втором выходе распределителя 28 в случае, когда в регистре 21 находится искомый узел, срабатывает элемент И 7, в результа.те чего открывается группа 2 элементов И и искомые данные проходят на группу 33 выходов. Кроме. того, появляется импульс на выходе элемента

ИЛИ 8, устанавливая устройство в исходное состояние. После обновления содержимого регистров 2 и/или 19 оно снова может быть запущено в- работу.

Одновременно с этим открывается группа 3 элементов И, в результате чего выбранный для дальнейшего просмотра указатель через одну из групп

4-6 элементов И и группу 1 элементов ИЛИ переписывается в регистр 20.

Кроме того, обновляется содержимое стека 16. Если для дальнейшего просмотра выбран левый или правый указатель, то появляется импульс на ф <«p и у гт зО выходе элемента ИЛИ 3, к«зторый увеличивает содержимое Верш:<ны стека

16 на единицу. С задержкзй, неооходимой для окончания перез«однь«х процессов, содержимое стека 16 проталкивается (погружается) на сдну .«чет":ку

Вниз. При этом в вершинe сcтека 1б понВля< тся сВободная с«бнуленна«< ячейка, выделяемая для спедующе!.

ПОсле этОГО пс импу,<ьсу на iIep-"

BQN выходе «заспред<.лит.ля 28 ется следующий цикл pH<3c TI: устройства. Таким образом, .":. тройство рe-ализует алгоритм поиск» в .-лубину, Сначала осуществлнется грось<отр,IIe" рева от корня только .-НО лев ьм указателям до тех пор, пока «:е будет найден искомый узел, либо не встретится левый пустой указа<ель. В первом слУчае считаетсЯ„что зстРОйство свои функции вь".полнило. БО в., ором случае предпринимается попытка выбрать узел по правому указа. елю. Е<:ли правьн".: указатель пустой„ <о Ос«ществляе!ся возврат к непосредс.твекному предку и предпринимается пзпь т!са поиска по самому левому из еще I.e вьбиравшихся указателей, Если жв правый указатель непустой то g.:апогично описанному просматривает:.я поддерево, корень которого задается эти«-. . указателем. В случае, когда в дереве узел с заданным ключом отс. тствует, после полного просмотра дерева осушествлн-ется возврат к корню и при попытке

Выбрать его предка происходит оста= нОВка устройства c cII. H eII« »I «III выходе 34.

Если дерево являе -,ся вырожденным (т.е. состоит из одно с узла) и клю.-I этого узла находится з регистре 19, то за. один цикл работ. устройства происходит одновреме::-:а:я выда.-.а по-ля 22 на группу 33 вьтк<здов и сигнала об отсутствии †.-:<ско.«ого узл::.. На вы=ход 3«4. Разрешить этот конфликт мож" но двумя способами,, запретить использовать вырожденнь.с деревья; отдать приоритет коду на группе 33 вы- ходОВ Внешним ПО Отношению к 1цзедлО": женному устройством, В случае невырожденного дерева рассмотренная ситуация невозможна, так как до полного просмотра дерева его корень будет считан не менее Одного раза. Поэтому, если он является искомым узлом, то работа устройства завершается успешно до этого момента (a точнее — на первом шаге). с изобретения устройство для поиска информации, содержащее группу элементов ИЛИ, пять групп элементов И, элемент И, два элемента ИЛИ, дешифратор левого указателя, дешифратор правого указателя„ дешифратор обратного указателя,„ дешифратор состояния узла, компаратор, элемент задержки, стек, регистр ключа, регистр адреса, регистр информации,, блок памнти, распределитель импульсов и генератор импульсов, выхоц которого соединe«I с управлн- ющим входом распределителя импульсов, первый выход которого соединен с синхронизирующим вхоцом регистра информации„ входы которого соединены с вь ходами блока памяти, входы ко<орого càåä«Iíåíû с выходами регистра адреса, входы которого соеди иены с выходами группы элементов

ИЛИ, первая группа входов которой является группой адресных входов устройства, вход запуска которого соединен с входом запуска генератора импульсов, вход останова которого соедичен с установочными входами распределителя импульсов и стека-.и с выходом первого элемента ИЛИ, первый вход которого соединен с выходом признака конца работы устройства, 1руппа входов ключа которого соединена с. Входами регистра ключа, выходы которого соединены с первой груп-пой входов компаратора, вторая груп» па входов которого соединена с выходами г<сля ключа регистра информации, выходы поля данных которого соединены с инфор <ационными входами первой группь< элементов И, выходы которой являются группой информационных выходов устройства, выход компаратора соединен с первым входом элемента И, выход которого соединен с вторым входом первого элемент" ИЛИ и с управляющим входом первой группы элементов И, второй вход элемента И сОединен с вторым выходом распреде7 14641 лителя импульсов, выходы полей левого правого и обратного указателей регистра информации соединены с информационными входами второй, третьей и четвертой групп элементов И соответственно, выходы которых соединены с второй, третьей и четвертой группами входов группы элементов ИЛИ соответственно, выходы полей левого и правого указателей регистра информации соединены с входами дешифраторов левого и правого указателей соответственно, выходы старшего и младшего разрядов вершины стека соединены с первым и вторым входами дешифратора состояния узла соответственно, первый, второй и третий выходы которого соединены с первым, вторым и третьим информационными входа- 2<> ми пятой группы элементов И соответственно, первый, второй и третий выходы которой соединены с первым и вторым входами второго элемента ИЛИ и с входом прямого сдвига стека 25

f3 Т

Вьп оды

40 41 42 43

35 36 37 38 39

2 3 4 5 6 7 8 9

0 0 0

0 0 0

0 0 0

0 0 0

0 0 1

0 0 1

0 0

0 0 1

0 1 0

0 1 0

0 1 0

0 1 0

0 1

0 1 1

1 0 0

1 0 0

0 0

0 1

I 1

0 0

0 I

1 0

1 1

0 0

1 0

1 1

0 0

0 1

0 0

0 1

cooтветстеенно, выход второго элемента

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

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

1 0 0 0

1 0 0 0

0 0 0

1 0 0 0

0 1 0 0

0 1 0 0

0 0 l 0

0 0 0

0 0 0

0 1 0 0

0 0 1 0

0 0 0

0 0 1 0

0 0 0 1

0 0 1 0

0 . 0 0 1