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

 

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

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

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

РЕСПУБЛИК

„„SU„, 1228116 А1 (5D4G0 F

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

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

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

БЩщ,<>., К АВТОРСКОМ У СВИДЕТЕЛЬСТВУ (21) 3748516/24-24 (22) 06.06.84 (46) 30.04.86. Бюл. У 16 (72) Б.С.Богумирский (53) 781.325(088 ° 8) (56) Авторское свидетельство СССР

11 342185, кл. G 06 F 7/22, 1969.

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

Ф 1 126972, кл. G 06 F 15/40, 1984. границ соответственно, сумматор, регистр ключа, первую и вторую схемы сравнения, регистр информации, блок памяти, в.котором хранится информация, выходной регистр, генератор импульсов, с первого по третий элементы ИЛИ, первую и вторую группы элементов ИЛИ, реверсивный счетчик, распределитель импульсов, первой и второй элементы И. Поиск записи инициируется IIO входу пуска устройства. На входы кода ключа адреса верхней и нижней границ предварительно подаются коды ключа искомой записи, адреса последней и первой записи в наборе данных соответственно, а по устано- щ

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

1 1228

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

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

На чертеже изображена блок-схема устройства. 10 устройство содержит - регистр 1 адреса верхней границы, регистр 2 адреса нижней границы,„сумматор 3, регистр 4 ключа, первую схему 5 сравнения, регистр 6 информации, блок 7 15 памяти, выходной регистр 8, генератор 9 импульсов, первый элемент ИЛИ

10, первую группу элементов ИЛИ 11, второй и третий элементы ИЛИ 12и 13 реверсивный счетчик 14, распредели- 20 тель 15 импульсов, вторую схему 16 сравнения, первый и второй элементы

И 17 и 18, вторую группу элементов

ИЛИ 19, вход 20 пуска устройства, установочный вход 21 устройства, вход 22 кода ключа устройства, вход

23 адреса верхней границы устройства, вход 24 адреса нижней границы устройства, выход 25 адреса устройства, выход 26 признака устройства. З0

Позициями 27, 28 и 29 обозначены выходы "Равно", "Меньше" и "Больше" первой схемы 5 соответственно. Позициями 30 — 33 обозначены первый, второй, третий и четвертый выходы распределителя 15 соответственно, Каждая запись набора данных состоит из ключа и информационной части. Предполагается, что записи набора данных, находящегося в блоке 7 памяти, отсортированы по возрастанию ключей. Требуется найти адрес записи с заданным ключом. Адрес ячейки (записи), разделяющей набор данных (или оставшуюся часть набора данных, в которой находится искомая запись) на две примерно равные части, называется рубежом.

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

В исходном состоянии счетчик 14 и регистры 6 и 8 обнулены, распределитель 15 установлен в исходное состояние. На входы 22, 23 и 24 подаются коды ключа искомой записи, адреса последней записи в наборе данных и адреса первой записи в наборе данных соответственно. По импульсу на

116 2 установочном входе 21 разрешается запись информации в регистры. 4, 1 и

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

1, а код адреса первой записи в наборе данных через вторую группу эле-. ментов ИЛИ 19 — в регистр 2. Будем называть адрес последней записи в наборе данных верхней границей (52 ), а адрес первой записи — нижней границей (НГ).

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

Импульсы с его выхода через распределитель 15 подаются в различные точки устройства. Первый импульс появляется на выходе 30 распределителя 15. Этот импульс разрешает запись информации в счетчик 14, в результате чего сумма НГ и ВГ с выходов сумматора 3 со сдвигом на один разряд в сторону младших разрядов заносится в счетчик 14. Этот код является первым (в последующем — очередным) рубежом. Таким образом, первый рубеж P(определяется следующим образом: где 2,х3 ближайшее целое, меньшее или равное х. После этого появляется импульс на выходе 31 распределителя

15, по которому запись, определяется рубежом, с выходов блока 7 памяти заносится в регистр 6. Первая схема 5 осуществляет сравнение кода ключа искомой записи, находящегося в регистре 4, с кодом ключа записи, считанной на регистр 6. При этом возможны . следующие ситуации.

Код считанной записи совпадает с искомым кодом ключа. В этом случае появляется сигнал "Равно" на выходе

27 первой схемы 5, по которому адрес искомой записи, находящийся в счетчике 14, заносится в регистр 8, а генератор 9 останавливается.

Код считанной записи меньше иско-, мого кода ключа. В этом случае возникает сигнал "Меньше" на выходе 28 первой схемы 5. Этим сигналом задается суммирующий режим счетчика 14 и открывается первый элемент И 27.

1228116

P = ((нг+ вг)/21, только одна иэ !!Г или Sl не равна соответствующему коду при формировании первого рубежа.

В дальнейшем устройство работает аналогично описанному.

Если искомая запись в наборе данных отсутствует, то наступит такой момент, когда BI станет меньше Нг (на единицу). Эту ситуацию фиксирует вторая схема.16 сравнения, выдавая сигнал на своем выходе, когда

55

Код считанной записи больше искомого кода ключа. Это приводит к появлению сигнала "Больше" на выходе 29 первой схемы 5, по которому задается вычитающий режим счетчика 14 и открывается второй элемент И 18.

По импульсу на выходе 32 распределителя 15 содержимое счетчика 14 увеличивается или уменьшается на единицу в зависимости от заданного режима fp работы.

После этого появляется импульс на выходе 33 распределителя 15, который проходит либо через первый элемент

И 17, либо через второй элемент И 18 15 и стробирует запись информации либо в регистр 2, либо в регистр 1. В результате этого в один из регистров

1 или 2 осуществляется запись кода, сформированного в счетчике 14. 20

Таким образом, если код ключа считанной из блока 7 записи меньше искомого кода ключа (т.е. в первой половине набора данных искомой записи нет), то к первому рубежу прибавляет- 25 ся единица и получившийся код записывается в регистр 2 в качестве нижней границы нового набора данных, содержащего искомую запись, если же код ключа считанной из блока 7 записи больше искомого кода ключа (т.е. во второй половине набора данных искомой записи нет), то из первого рубежа вычитается единица и получившийся код записывается в регистр 1 в

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

После этого снова появляется импульс на выходе 30 распределителя

15, по которому формируется второй рубеж по тому же правилу, 45 содержимое регистра 1 меньше содержимого регистра 2. Этот сигнал остановит генератор 9 и пройдет на выход 26, чем засвидетельствует отсутствие записи с искомым ключом.

Последующие обращения к найденной записи могут быть реализованы путем установки устройства в исходное состояние и загрузки i регистры 1 и 2 адре .а этой записи, а в регистр 4ее ключа. После этого на вход 20 подается импульс, по которому на регистр 6 будет считана требуемая запись, а генератор 9 импульсов остановится.

3а счет реализации в предлагаеМоМ устройстве другого принципа формирования рубежа на количество записей в наборе данных не накладывается никаких ограничений, Следовательно для обеспечения работы устройства нет необходимости искусственно увеличивать количество записей. Реальное число записей в этом случае совпадает с фактическим числом записей.

Это ведет к более экономному расходу памяти и к уменьшению количества обращений к блоку памяти для поиска требуемой записи.

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

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

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

ВНИИПИ Заказ 2288/50 Тираж 671 Подписное

Произв.-полигр. пр-тие, r. Ужгород, ул. Проектная, 4 дом адреса устройства, а адресный вход блока памяти объединен с информационным входом выходного регистра, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства за счет уменьшения количества обращений к блоку памяти для поиска требуемой записи, оно содержит второй, третий элементы ИЛИ, ревер- 10 сивный счетчик, распределитель импульсов, вторую схему сравнения, первый, второй элементы И и вторую группу элементов ИЛИ, причем входы адреса верхней границы устройства соединены 15 с первыми входами элементов ИЛИ первой группы, выходы которых соединены с информационными входами регистра адреса верхней границы, выходы которого соединены с входами первой груп- 20 пы второй схемы сравнения, вторая группа входов которой соединена с второй группой входов сумматора и с выходами регистра адреса нижней границы, информационные входы которого 25 соединены с выходами элементов ИЛИ второй группы, первые входы которых соединены с входами адреса нижней границы устройства, выход сумматора соединен с информационным входом ре- Ç0 версивного счетчика, выходы которого соединены с вторыми входами элементов ИЛИ первой и второй групп, установочный вход устройства соединен с первыми входами второго и третьего элементов ИЛИ, выходы которых соединены со стробирующими входами регистра адреса верхней границы и регистра адреса нижней границы соответственно, выход "Меньше" второй схемы сравнения соединен с выходом признака устройства и с вторым входом первого элемента ИЛИ, выход генератора импульсов соединен с входом распределителя импульсов, первый выход которого соединен с входом разрешения записи реверсивного счетчика, суммирующий вход которого соединен с первым входом первого элемента И и с выходом "Меньше" первой схемы сравнения, выход "Больше" которой соединен с вычитающим входом счетчика и с первым входом второго элемента И, выход которого соединен с вторым входом второго элемента ИЛИ, второй и третий выходы распределителя импульсов соединены со стробирующим входом регистра информации и со счетным входом реверсивного счетчика соответственно, четвертый выход распределителя импульсов соединен с вторыми входами второго элемента И и первого элемента И, выход которого соединен с вторым входом третьего элемента ИЛИ, установочный вход устройства соединен с входом стробирования регистра ключа, И