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

 

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

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

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

РЕСПУБЛИК (51)5 G 06 F 15/40

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4696215/24 (22) 05.04,89 (46) 07.02.92. Бюл. N. 5 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) А.В.Пришибской, В.М.Глушань и

В.М,Курейчик (53) 681.325(088.8) (56) Авторское свидетельство СССР

N 1278891, кл. G 06 F 15/40, 1985.

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

N1621049,,кл. G 06 F 15/40, 1989. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ

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

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

Алгоритм по методу Айверсона предназначен для поиска аргумента К в таблице записей R1, R2,... RN, расположенных в порядке возрастания ключей К1< K2 « „, KN, Начальная установка = 1, U = N.

Нахождение середины, Если U< 1, то

i+0 неудачный конец алгоритма, иначе i=() к=U-1, Сравнение. Если К < К;, то переход на 4.

Если К> Кь то переход на 5, Если К = К, то удачный конец алгоритма.

Если К < 44, то переход на 6.

Корректировка U.U = i-1, переход на 2, „„5U „„171 1 185 А1 (57) Изобретение относится к вычислительной технике. Цел ь изобретения — уп рощение и повышение быстродействия устройства за счет реализации поиска по методу Айверсона. Устройство содержит регистры верхней и нижней границ, три элемента И, блок памяти, две схемы сравнения, три счетчика, регистр ключа, выходной регистр, три группы элементов ИЛИ, четыре элемента ИЛИ, сумматор-вычитатель, регистр стратегии поиска, две группы элементов И, четыре элемента задержки, триггер с соответствующими связями. Устройство наиболее эффективно при поиске в небольших наборах. 1 ил.

Корректировка !Л = i+1, переход на 2, Начальная установка i = i, Сравнение, Если К < К;, то переход на 9.

Увеличение!л = i+1, переход на 7, Сравнение. Если К = Кь то удачный ко- — 1 нец алгоритма, иначе неудачный конец ал- горитма. ф

Применение устройства оправдывается при поиске в небольших наборах с числом записей 2 — 2 . При N = 2 алгоритмическая

1О трудоемкость снижается пиша íà 11%.

На чертеже лриеедена структурная скема устройства.

Устройство содержит регистр 1 верхней границы, ремстр 2 нижней границы, сумматор-вычитатель 3, регистр 4 стратегии поиска, вычитающий счетчик 5, суммирующие счетчики 6 и 7, схему 8 сравнения, блок 9 памяти, регистр 10 ключа, схему

11 сравнения, выходной регистр 12, группы

13 — 15 элементов ИЛИ, группы 16, 17 элементов И, элементы ИЛИ 18 — 21, элементы 22 — 25 задержки, триггер 26, элементы И 27 — 29, вход

30 запуска, вход 31 адреса верхней грани1711185 цы, вход 32 адреса нижней границы, вход33 кода критерия смены стратегии поиска, вход 34 ключа, выход 35 адреса, выход 36 признака отсутствия информации. Элементы 22 — 25 задержки объединены в распределитель 37 импульса.

Устройство начинает работать по методу поиска делением пополам.

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

13, в регистр 2 кода адреса нижней границы, поступающего с входа 32 через элементы ИЛИ группы 14, в регистр 4 кода критерия смены стратегии поиска, поступающего с входа 33, в регистр 10 кода ключа искомой записи, поступающего с входа 34, и обнуление триггера 26. После записи информация с входов 31 и 32 снимается. Одновременно импульс проходит через элементы ИЛИ 21 и 22, где задерживается на время поступления информации в регистры 1 и 2, и поступает на вход Sb, а через элемент ИЛИ 20— на вход V сумматора-вычитателя 3, разрешая поступление в него уменьшаемого и вычитаемого, Разность поступает на вход схемы 8, где сравнивается с числом 44, поступающим с выхода регистра 4. При условии U - l > 44 дальнейшая работа устройства аналогична, работе известного устройства.

Импульс с выхода элемента 22 поступает на элемент 23, где задерживается на время выполнения операций вычитания и сравнения, в сумматор-вычитатель 3 и схему 8, соответственно, поступает на вход SM и через элемент ИЛИ 20 на вход V, разрешая поступление слагаемых в сумматор-вычитатель 1. Задержанный на элементе 24 на speмя выполнения операции суммирования в

=умматоре-вычислителе 4, импульс разрешает запись кода с выхода сумматора-вычитателя 3, сдвинутого на один разряд в сторону младшего разряда, в счетчики5 и 7 и в счетчик 6 через элементы И группы 16, открытые единичным потенциалом с инверсного выхода триггера 26, и элементы ИЛИ группы

15. Задержанный на элементе 25 на время записи информации в счетчики 5 — 7, импульс поступает на входы С счетчиков 5 и 7, осуществляя уменьшение и увеличение на единицу их содержимого соответственно.

Адрес с выхода счетчика 6 поступает на адресный вход блока 9, где по нему производится выборки записи с ключом, который поступает с выхода блока 9 на схему 11, где сравнивается с ключом искомой записи, поступающим с выхода регистра 10.

При этом возможны следующие ситуации.

Ключ искомой записи совпадает с ключом считанной записи. Сигнал с выхода

"Равно" схемы 11 разрешает запись адреса искомой записи с выхода счетчика 6 в регистр

5 12, после чего этот адрес появляется на выходе 35, Ключ искомой записи меньше ключа считанной записи, Сигнал с выхода "Меньше" схемы 11 поступает через элемент ИЛИ

10 18 на вход V регистра 1, разрешая запись в него через элементы ИЛИ группы 13 содер>кимого с выхода счетчика 5.

Ключ искомой записи больше ключа считанной записи, Сигнал с выхода "Больше"

15 схемы 11 проходит через элемент И 28, открытый единичным потенциалом с инверсного выхода триггера 26, и поступает через элемент ИЛИ 19 на вход V регистра 2, разрешая запись в него через элементы ИЛИ

20 группы 14 содержимого счетчика 7. Также сигнал с выходов "Меньше" или "Больше" схемы 11 проходит через элемент ИЛИ 21 и поступает на распределитель импульсов, состоящий из элементов 22 — 25. При условии

25 U — I .< 44 появляется сигнал на выходе

"Меньше или равно" схемы 8, по которому триггер 26 устанавливается в единичное состояние. При этом происходит смена стратегии поиска, и устройство начинает

30 работать по методу последовательного поиска.

При поступлении сигнала с выхода элемента 24 на вход V счетчика 6 в него записывается содержимое регистра 2 через

35 элементы И группы 17, открытые единичным потенциалом с прямого выхода триггера 26 и элементы ИЛИ группы 15, При работе схемы 11 в этом режиме возможны следующие ситуации.

40 Ключ считанной записи совпадает с ключом искомой записи аналогично описанному, Ключ искомой записи больше ключа считанной записи. Сигнал с выхода "Больше"

45 схемы 11 проходит через элемент И 27, открытый единичным потенциалом с прямого выхода триггера 26 и поступает на вход С счетчика б, увеличивая его содержимое на еди н и цу.

50 Ключ искомой записи меньше ключа считанной записи. Сигнал с выхода "Меньше" схемы 11 проходит через элемент И 29, открытый единичным потенциалом с прямого выхода триггера 26, на выход 36, сигнали55 зируя об отсутствии информации с искомым ключом, Формула изобретения

Устройство для поиска информации, содержащее регистр верхней гра1711185

15

45

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

"Меньше" первой схемы сравнения соединен с первым входом первого элемента И и вторым входом первого элемента ИЛИ, триггер, инверсный выход которого соединен с первым входом второго элемента И, выход которого соединен с вторым входом второго элемента ИЛИ, третий элемент И, четвертый и пятый элементы ИЛИ, распределитель импульсов, первую и вторую группь элементов И, выходы которых соединены с входами элементов ИЛИ третьей группы, о т л и ч а ю щ е е с я тем, что, с целью упрощения и повышения быстродействия, сумматор выполнен с возможностью вычитания, причем выход сумматора-вычитателя соединен с информационными входами первого и второго счетчиков со сдвигом на один разряд в сторону младших разрядов, а первый счетчик выполнен вычитающим, причем в устройство дополнительно введены вторая схем сравнения, третий счетчик и регистр стратегии поиска, информационный вход которого является входом стратегии поиска устройства, вход запуска которого соединен с управляющим входом регистра стратегии поиска, выход которого соединен с первым входом второй схемы сравнения, второй вход которой соединен с выходом сумматора-вычитателя, входы управления сложением и вычитанием которого соединены с первым и вторым входами третьего элемента ИЛIË и с первым и вторым выходами распределителя импульсов, третий и четвертый выходы которого соединены соответственно с входом управления записью первого счетчика и с объединенными синхровходами первого и второго счетчиков, выход третьего счетчика соединен с адресным входом блока памяти, выход которого соединен с вторым входом первой схемы сравнения, выходы "Больше" и "Меньше" которой соединены с первым и вторым входами четвертого элемента ИЛИ, выход которого соединен с входом запуска распределителя импульсов, выход "Больше" первой схемы сравнения соединен с вторыми входами второго и третьего элементов И, первый вход третьего элемента И соединен с прямым выходом триггера, вторым входом первого элемента И и первыми входами элементов И второй группы, вторые входы которых соединены с выходами регистра нижней границы, выходы cóììàòopa-вычитателя соединены с вторым входом второй схемы сравнения, вторыми входами элементов И первой группы, вторые входы которых соединены с инверсным выходом триггера, установочный вход которого соединен с выходом второй схемы сравнения, 40 вход сброса триггера соединен с входом запуска устройства, выход признака отсутствия информации которого соединен с выходом первого элемента И, выход третьего элемента И соединен с синхровходом третьего счетчика, вход управления записью которого соединен с третьим выходом распределителя импульсов, а информационные входы — с выходами элементов ИЛИ третьей группы, третий вход четвертого элемента ИЛИ вЂ” с входом запуска устройства.

1711185

Составитель В. Чистобородов

Техред М.Моргентал Корректор О.Кундрик

Редактор С.Патрушева

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

Заказ 341 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5