SU342185A1 - УСТРОЙСТВО дл ПОИСКА ИНФОРМАЦИИ - Google Patents

Description

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

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

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

чика и предназначенный дл  многократных обращений к найденной записи при обработке ее содержимого без повторений процесса поиска .

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

Когда записи имеют переменную длину, и

заранее неизвестно, сколько записей размещено на той или иной дорожке, то возникают затруднени  в установлении соответстви  между двоичным кодОлМ адреса записи с одной стороны и номером дорожки и пор дковым номером записи на дорожке - с другой.

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

Блок-схема предложенного устройства изображена на чертеже. а второй-с выходом регистра 3 дл  приема и хранени  призначной части записей, выбираемых блоком управлени  4. Схема сравнени  2 имеет три выходных канала 5, 6 и У, подключенных к логическому блоку 3 и соответственно определ ющих случай равенства содержимого регистров 1 и J, случай, когда содержимое регистра / больше содержимого регистра о, и случай, когда содержимое регистра 1 меньше содержимого регистра 3. Выход 5 соединен с блоком управлени  4. Входы Я 10 и 11 блока 8 св заны с выходами блока управлени  4. Выходы 12-15 блока 8 подключены к блоку формировани  адреса дорожки 16, который  вл етс  дихотомическим счетчиком и имеет два выхода 17 и 1 Выход 17 блока 16, предназначенный дл  сигнализации о выполнении последнего шага поиска, соединен со входом блока 8. Выход 1 блока 16 формировани  адреса дорожки предназначен дл  вывода кода сформированного адреса дорожки и присоединен к олоку управлени  4. Выход 19 блока 8 закоммутирован со входом блока 20 дл  формировани  адреса числа, представл юш,его собой обычный двоичный счетчик, выход 21 которого соединен с блоком управлени  4. Дл  выбора переменной части записи служит блок 22, вход 23 и выход 24 которого подключены к блоку управлени  4. В блок 22 выбора переменной части записи поступает код адреса переменной части внутрн записи. Устройство работает следуюш,им образом. Код лризначной части записи и код адреса положени  этой части внутри записи засылаютс  соответственно в регистр 1 и блок 8. Из блока управлени  4 на вход 9 блока 8 поступает сигнал, который по вл етс  на выходе 12 блока 8 и устанавливает счетчик бло- ка 16 в начальное состо ние. При этом в счетчике формируетс  адрес средней дорожки примен емого запоминаюш,его устройства. С выходов 18 и 21 блоков 16 и 20 сформированный адрес средней дорожки и нулевой адрес числа поступают в блок управлени  4, где по прин тому адресу дорожки .подключаетс  нужна  дорожка. Так как переданный адрес числа равен нулю (что соответствует первой записи на подключенной дорожке), блок управлени  4 выработает сигнал совпадени  адреса числа, который позволит выдать из блока управлени  4 на вход 23 блока 22 метки разделени  слов внутри первой записи. Сравнива  номер метки с кодом адреса призначной части внутри записи, блок 22 на своем выходе 24 выдает сигнал в случае их совпадени . По этому сигналу блок управлени  4 передает код призначной части в регистр 3. Схема сравнени  2 сравнивает этот выбранный код с хран ш,имс  в регистре 1 заданным кодом призначной части. 2)код из регистра / больше кода из регистра 3; 3)код из регистра / меньше кода из регистра 3. Сигналы соответственно этим результатам по вл ютс  на выходах 5, 5 и 7 схемы сравнени  2. Если код в регистре J больше кода из регистра 3, то сигнал с выхода б схемы сравнени  2 по вл етс  на выходе У5 этого блока и воздействует па счетчик блока 16 таким образом , что он увеличивает свое состо ние на 2«:-1 (/(-номер последнего младшего разр да , в котором записана единица). Если код в регистре 1 меньше кода из регистра 3, то сигнал с выхода 7 схемы сравнени  2 поступает на его выход 14 и далее на счетчик блока 16, который уменьшает свое состо ние на . Вновь сформулированный адрес дорожки совместно с нулевым адресом числа передаетс  в блок управлени  4, и процесс повтор етс . В том случае, если на i-м шаге на выходе 5 схемы сравнени  2 по вл етс  сигнал, означающий , что запись с заданным признаком  вл етс  первой на выбранной дорожке, т. е. имеет нулевой адрес, режим поиска заканчиваетс , так как этот сигнал поступает в блок управлени , который прекращает дальнейший поиск информации и переключаетс  на режим выборки найденной записи. Если же запись расположена не в начале дорожки, то процесс поиска продолжаетс  до тех пор, пока не будет произведено k og2tn сравнений заданного и выбранного признаков, где т - число дорожек примен емого запоминающего устройства. Сигнал о выполнении /С-го шага (или Л-го сравнени ) вырабатываетс  счетчиком блока 16 и с выхода 17 поступает на вход блока 8. При этохм имеют место два варианта дальнейшей работы устройства: 1)код из регистра / больше кода призначной части первого числа выбранного на /С-ом шаге, 2)код из регистра 1 меньше кода призначной части первого числа, выбранного на /С-ом шаге. Рассмотрим случай, когда записи в ЗУ распололсены в пор дке возрастани  величины их призначной части. В первом случае на выходе 6 схемы сравнени  2 по вл етс  сигнал, и устройство переводитс  в режим поиска адреса числа. С блока управлени  4 на вход 11 блока 8 поступают сигналы разделительных меток заисей на дорожке. Эти сигналы проход т в блок 20, который  вл етс  обычным двоичным четчикоМ: Одновременно с выделением раздеительных меток записей производитс  сравение кода призначной части записи последоательно , начина  с начала дорожки, с заданым признаком, хран щимс  в регистре 1,

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

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

В случае, если код из регистра / меньше кода призначной части первого числа, выбранного на /С-ом шаге, засланной в регистр 3, схема сравнени  вырабатывает на выходе 7 сигнал , который поступает на выход 15 блока 5.

По сигналу на выходе 15 блока 8 счетчик блока 20 уменьшает свое состо ние на единицу , т. е. возвращаетс  на ранее просмотренную доролчку с номером «а единицу меньшим.

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

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

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