УСТРОЙСТВО для ПОИСКА ИНФОРМАЦИИ Советский патент 1972 года по МПК G06F7/22 

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

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

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

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

Если информация хранится в многодорожечном ЗУ циклического типа (магнитный барабан или магнитный диск), то применение устройства, работающего по дихотомическоЛ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 уменьшает свое состояние на единицу, т. е. возвращается на ранее просмотренную доролчку с номером «а единицу меньшим.

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

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

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