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

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

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

Алгоритм по методу Айверсона предназначен для поиска аргумента К в таблице записей Ri, R2,...,R(M, расположенных в порядке возрастания ключей Ki K2 ... Км.

Начальная установка I 1, U N.

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

неудачный конец алгоритма, иначе i n J

, ..

Сравнение. Если К Ki, то переход на 4. Если К Ki, то переход на 5. Если К KI, то удачный конец алгоритма. Если К 44, то переход на 6. Корректировка U.U 1-1, переход на 2,

Корректировка I.I i+1, переход на 2.

Начальная установка i I.

Сравнение. Если К Ki, то переход на 9.

Увеличение i.i i+1, переход на 7.

Сравнение. Если К Ki, то удачный конец алгоритма, иначе неудачный конец алгоритма.

Применение устройства оправдывается при поиске в небольших наборах с числом записей 28-29. При N 210 алгоритмическая трудоемкость снижается лишь на 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 адреса верхней грани(Л

С

00

ел

цы, вход 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, и поступает на вход 5ь, а через элемент ИЛИ 20 - на вход V сумматора-вычитателя 3, разрешая поступление в него уменьшаемого и вычитаемого. Разность поступает на вход схемы 8, где сравнивается с числом 44, поступающим с выхода регистра 4. При условии U -1 44 дальнейшая работа устройства аналогична.работе известного устройства. Импульс с выхода элемента 22 поступает на элемент 23, где задерживается на время выполнения операций вычитания и сравнения, в сумматор-вычитатель 3 и схему 8, соответственно, поступает на вход SM и через элемент ИЛИ 20 на вход V, разрешая поступление слагаемых в сумматор-вычитатель 1. Задержанный на элементе 24 на время выполнения операции суммирования в

мматоре-вычислителе 4, импульс разрешает запись кода с выхода сумматора-вычитателя 3, сдвинутого на один разряд в сторону младшего разряда, в счетчикиб и 7 и в счетчик 6 через элементы И группы 16, открытые единичным потенциалом с инверсного выхода триггера 26, и элементы ИЛИ группы 15. Задержанный на элементе 25 на время записи информации в счетчики 5-7, импульс поступает на входы С счетчиков 5 и 7, осуществляя уменьшение и увеличение на единицу их содержимого соответственно. Адрес с выхода счетчика 6 поступает на адресный вход блока 9, где по нему производится выборки записи с ключом, который поступает с выхода блока 9 на схему 11, где

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

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

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

12, после чего этот адрес появляется на выходе 35.

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

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

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

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

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

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

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

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

элементы И группы 17, открытые единичным потенциалом с прямого выхода триггера 26 и элементы ИЛИ группы 15.

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

Ключ считанной записи совпадает с

ключом искомой записи аналогично описанному.

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

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

Ключ искомой записи меньше ключа

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

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

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

распределителя импульсов, выход Больше первой схемы сравнения соединен с вторыми входами второго и третьего элементов И, первый вход третьего элемента И соединен с прямым выходом триггера, вторым входом первого элемента И и первыми входами элементов И второй группы, вторые входы, которых соединены с выходами регистра нижней границы, выходы сумматора-вычитателя соединены с вторым входом

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

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

элемента ИЛИ - с входом запуска устройства.

i

LSI I

Ј

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