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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

342185

Сова Советских

Социалистических

Республик

Зависимое от авт. свидетельства №

Заявлено 08.IÕ.1969 (№ 1358146/18-24) с присоединением заявки №

Приоритет

Опубликовано 14.VI.1972. Бюллетень № 19

Дата опубликования описания 7ХП.1972

М. Кл. G 06f 7/22

Комитет по делаМ йзобоетений и открытий при Сдеете Министров

СССР

УДК 681.327.11(088.8) Авторы изобретения

В. Л. Волковыский и Л. М. Ройтбурд

Рязанский завод счетно-аналитических машин

Заявитель

УСТРОЙСТВО ДЛЯ ПОИСКА ИИФОРМАЦИИ

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

Информация в таких системах и устройствах обычно разделяется на отдельные смысловые участки, называемые записями, каждая из которых может состоять из нескольких слов. Обычно запись разделяют на две части — призначную (или шифр) и и формационную.

Известны устройства поиска информации, записанной в каком-либо запоминающем устройстве (ЗУ), путем сравнения заданного признака с призрачными частями записей, имеющихся в ЗУ. Если записи расположены в ЗУ упорядоченно, например в порядке возрастания или убывания численных значений призначных частей, рассматриваемых как двоичные коды, и все записи имеют различные признаки, то для ускоренного поиска может быть применено устройство, работающее по дихотомическому методу или методу последовательных приближений.

Такие устройства содержат блок управления обменом информацией с ЗУ, схему сравнения признаков выбранной записи и заданного, а также блок формирования адреса записи, построенный на основе дихотомического счетчика и предназначенный для многократных обращений к найденной записи при обработке ее содержимого без повторений процесса поиска.

5 Если информация хранится в многодоро жечном ЗУ циклического типа (магнитный барабан или магнитный диск), то применение устройства, работающего по дихотомическому методу, не рационально, так как в общем слу10 чае требуется многократное обращение к од ой и той же дорожке, причем для каждого обращения требуется время, не меньшее одного цикла.

Когда записи имеют переменную длину, и заранее неизвестно, сколько записей размещено на той или иной дорожке, то возникают затруднения в установлении соответствия между двоичным кодом адреса записи с одной стороны и номером дорожки и порядковым но20 мером записи на дорожке — с другой.

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

25 Блок-схема предложенного устройства изображена на чертеже.

Устройство содержит регистр 1 для приема и хранения заданного признака, по которому производится поиск, схему сравнения 2, один

30 вход которой соединен с выходом регистра 1, 342185

3 а второй — с выходом регистра 8 для приема и хранения призначной части записей, выбираемых блоком управления 4.

Схема сравнения 2 имеет три выходных канала 5, Ь и /, подключенных к логическому 5 блоку 8 и соответственно определяющих случай равенства содержимого регистров l и д, случай, когда содержимое регистра l больше содержимого регистра д, и случаи, когда содержимое регистра 1 меньше содержимого 10 регистра 8. Выход 5 соединен с блоком управления 4.

Входы 9, 10 и 11 блока 8 связаны с выходами блока управления 4. Выходы 12 — 15 блока 8 подключены к блоку формирования адре- 15 са дорожки 1Ь, который является дихотомическим счетчиком и имеет два выхода 17 и 18.

Выход 17 блока 1б, предназначенный для сигнализации о выполнении последнего шага поиска, соединен со входом блока 8. Выход18 20 блока 16 формирования адреса дорожки предназначен для вывода кода сформированного адреса дорожки и присоединен к олоку управления 4.

Выход 19 блока 8 закоммутирован со вхо- 25 дом блока 20 для формирования адреса числа, представляющего собой обычный двоичный счетчик, выход 21 которого соединен с блоком управления 4.

Для выбора переменной части записи слу- 30 жит блок 22, вход 28 и выход 24 которого подключены к блоку управления 4, В блок 22 выбора переменной части записи поступает код адреса переменной части внутри записи.

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

Код призначной части записи и код адреса положения этой части внутри записи засылаются соответственно в регистр 1 и блок 8.

Из блока управления 4 на вход 9 блока 8 поступает сигнал, который появляется на вы- 40 ходе 12 блока 8 и устанавливает счетчик бло-. ка 1б в начальное состояние. При этом в счетчике формируется адрес средней дорожки применяемого запоминающего устройства.

С выходов 18 и 21 блоков 1б и 20 сформиро- 45 ванный адрес средней дорожки и нулевой адрес числа поступают в блок управления 4, где по принятому адресу дорожки подключается нужная дорожка. Так как переданный адрес числа равен нулю (что соответствует первой 50 записи на подключенной дорожке), блок управления 4 выработает сигнал совпадения адреса числа, который позволит выдать из блока управления 4 на вход 28 блока 22 метки разделения слов внутри первой записи. Сравнивая номер метки с кодом адреса призначной части внутри записи, блок 22 на своем выходе 24 выдает сигнал в случае их совпадения.

По этому сигналу блок управления 4 передает код призначной части в регистр 8. Схема 60 сравнения 2 сравнивает этот выбранный код с хранящимся в регистре 1 заданным кодом призначной части.

Возможны три результата сравнения:

1) коды равны; 65

2) код из регистра 1 больше йода из реги стра 8;

3) код из регистра 1 меньше кода из регистра 8.

Сигналы соответственно этим результатам появляются на выходах 5, б и 7 схемы сравнения 2.

Если код в регистре 1 больше кода из регистра 8, то сигнал с выхода 5 схемы сравнения 2 появляется на выходе 18 этого блока и воздействует на счетчик блока 1б таким образом, что он увеличивает свое состояние на

2 - (К вЂ” номер последнего младшего разряда, в котором записана единица).

Если код в регистре 1 меньше кода из регистра 8, то сигнал с выхода 7 схемы сравн=ния 2 поступает на его выход 14 и далее на счетчик блока 1б, который уменьшает свое состояние на 2 — .

Вновь сформулированный адрес дорожки совместно с нулевым адресом числа передается в блок управления 4, и процесс повторяется.

В том случае, если íà i-м шаге на выходе 5 схемы сравнения 2 появляется сигнал, означающий, что запись с заданным признаком является первой на выбранной дорожке, т. е. имеет нулевой адрес, режим поиска заканчивается, так как этот сигнал поступает в блок управления, который прекращает дальнейший поиск информации и переключается на режим выборки найденной записи.

Если же запись расположена не в начале дорожки, то процесс поиска продолжается до тех пор, пока не будет произведено Й=1орт сравнений заданного п выбранного признаков, где m — число дорожек применяемого запоминающего устройства.

Сигнал о выполнении К-го шага (или К-ro сравнения) вырабатывается счетчиком блока

1б и с. выхода 17 поступает на вход блока 8.

При этом имеют место два варианта дальнейшей работы устройства:

1) код из регистра 1 больше кода призначной части первого числа выбранного на К-ом шаге, 2) код из регистра 1 меньше кода призначной части первого числа, выбранного на К-ом шаге.

Рассмотрим случай, когда записи в ЗУ расположены в порядке возрастания величины их призначной части.

В первом случае на выходе б схемы сравнения 2 появляется сигнал, и устройство переводится в режим поиска адреса числа.

С блока управления 4 на вход 11 блока 8 поступают сигналы разделительных меток записей на дорожке. Эти сигналы проходят в блок 20, который является обычным двоичным счетчиком-. Одновременно с выделением разделительных меток записей производится сравнение кода призначной части записи .последовательно, начиная с начала дорожки, с заданным признаком, хранящимся в регистре 1, 342185

Предмет изобретения

Составитель И. Фролова

Техред T. Ускова

Редактор Л, Утехина

Корректоры: А. Николаева и E. Давыдкина

Заказ 2004/13 Изд. И а20 Тираж 406 Подписное

ЦНИИПИ Кол итета по делал изобретений и открытий при Совете Министров СССР

Москва, Ж-35, Раув скан наб., д. 415

Типография, пр. Сапунова, 2

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

Сформированные таким образом в блоках

1б и 20 адреса дорожки и числа соответственно передаются в блок управле .пя 4, подготавливая его к режиму выборки найденной записи или ее переменной части. После окончания процесса выборки и, возможно, записи обработанной информации, блок управления 4 в "tдаст сигнал на вход 10 блока 8, после чего устройство готово и повторению процесса поиска.

В случае, если код из регистра 1 меньше кода призначной части первого числа, выбранного на 1(-ом шаге, засланной в регистр 8, схема сравнения выраоатывает на выходе 7 сигнал, которь|й поступает на выход 15 блока 8, По сигналу на выходе 15 блока 8 счетчик блока 20 уменьшает свое состояние на единицу, т. е. возвращается на ранее просмотренную дорожку с номером BB единицу меньшим.

Далее процесс протекает как в предыдущем слх чае.

Устройство для поиска информации, содержащее регистры, подключенные к схеме сравнения, блок управления, соединенныи с логнским блоком, блоками формирования адресов дорожки и числа, с однил1 и" регистров и блоком выборки перемечной части числа, отличаюи ееся тем, что, с целью сокращения времени поиска, в нем выходы схемы сравнения подключены к соответствующим входам логи20 чес oro блока, выходы которого соединены с олоками формирования адресов дорожки и кисла.