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

342188 Сома Соеетских Социалистических РеспубликЗависимое от авт. свидетельстваЗаявлено 08.1 Х,1969 ( 1358146/18-24 М. Кл, 6 061 7/22 присоединением заявкиПриоритет Комитет по делам йзобоетений и открытий при Сдаете Мииистрое СССРОпубликовано 14.И.1972, Бюллетень19 Дата опубликования описания 7,И 1.1972 К 681.327,11(088,8 Авторыизобретени Л, Волковыский и Л, М, Ройтбур 3 аявител Рязанский за етно-аналитических м УСТРОЙСТВО ДЛЯ ПОИСКА И МАЦИИ 1Изобретение относится к области вычислительной и информационной техники и можетбыть использовано в информационно-поисковых системах и устройствах для сортировкиданных,Информация в таких системах и устройствах обычно разделяется на отдельные смысловые участки, называемые записями, каждаяиз которых может состоять из несколькихслов. Обычно запись разделяют на две части - призначную (или шифр) и информационную.Известны устройства поиска информации,записанной в каком-либо запоминающем устройстве (ЗУ), путем сравнения заданного признака с призрачными частями записей, имеющихся в ЗУ. Если записи расположены в ЗУупорядоченно, например в порядке возрастания или убывания численных значений призначных частей, рассматриваемых как двоичные коды, и все записи имеют различные признаки, то для ускоренного поиска может бытьприменено устройство, работающее по дихотомическому методу или методу последовательных приближений,Такие устройства содержат блок управленияобменом информацией с ЗУ, схему сравненияпризнаков выбранной записи и заданного,а также блок формирования адреса записи,построенный на основе дихотомического счетчика и предназначенный для многократных обращений к найденной записи при обработке ее содержимого без повторений процесса поиска.5 Если информация хранится в многодорожечном ЗУ циклического типа (магнитный барабан или магнитный диск), то применение устройства, работающего по дихотомическому методу, не рационально, так как в общем слу чае требуется многократное обращение к одной и той же дорожке, причем для каждого обращения требуется время, не меньшее одного цикла.Когда записи имеют переменную длину, и 15 заранее неизвестно, сколько записей размещено на той или иной дорожке, то возникают затруднения в установлении соответствия между двоичным кодом адреса записи с одной стороны и номером дорожки и порядковым но мером записи на дорожке - с другой,Целью изобретения является уменьшениевремени поиска информации при сохранении достаточно простой схемы устройства и для случая переменной длины записи.25 Блок-схема предложенного устройства изображена на чертеже.Устройство содержит регистр 1 для приемаи хранения заданного признака, по которому производится поиск, схему сравнения 2, один 30 вход которой соединен с выходом регистра 1,3а второй - с выходом регистра 3 для приемаи хранения призначной части записей, выбираемых блоком управления 4,Схема сравнения 2 имеет три выходных канала 5, Ь и 7, подключенных к логическому 5блоку 8 и соответственно определяющих случай равенства содержимого регистров 1 и д,случай, когда содержимое регистра 1 большесодержимого регистра д, и случаи, когда содержимое регистра 1 меньше содержимого 10регистра д. Выход 5 соединен с блоком управления 4.Входы 9, 10 и 11 блока 8 связаны с выходами блока управления 4. Выходы 12 - 15 блока 8 подключены к блоку формирования адреса дорожки 16, который является дихотомическим счетчиком и имеет два выхода 17 и 18.Выход 17 блока 1 б, предназначенный длясигнализации о выполнении последнего шагапоиска, соединен со входом блока 8. Выход 18 20блока 1 б формирования адреса дорожки предназначен для вывода кода сформированногоадреса дорожки и присоединен к олоку управления 4.Выход 19 блока 8 закоммутирован со входом блока 20 для формирования адреса числа,представляющего собой обычный двоичныйсчетчик, выход 21 которого соединен с блокомуправления 4,Для выбора переменной части записи служит блок 22, вход 23 и выход 24 которого подключены к блоку управления 4, В блок 22 выбора переменной части записи поступает кодадреса переменной части внутри записи.Устройство работает следующим образом. З 5Код призначной части записи и код адресаположения этой части внутри записи засылаются соответственно в регистр 1 и блок 8.Из блока управления 4 на вход 9 блока 8поступает сигнал, который появляется на вы Сходе 12 блока 8 и устанавливает счетчик блока 1 б в начальное состояние, При этом в счетчике формируется адрес средней дорожки применяемого запоминающего устройства,С выходов 18 и 21 блоков 1 б и 20 сформированный адрес средней дорожки и нулевой адрес числа поступают в блок управления 4, гдепо принятому адресу дорожки подключаетсянужная дорожка. Так как переданный адресчисла равен нулю (что соответствует первой 50записи на подключенной дорожке), блок управления 4 выработает сигнал совпадения адреса числа, который позволит выдать из блокауправления 4 на вход 23 блока 22 метки разделения слов внутри первой записи. Сравнивая номер метки с кодом адреса призначнойчасти внутри записи, блок 22 на своем выходе 24 выдает сигнал в случае их совпадения.По этому сигналу блок управления 4 передает код призначной части в регистр 3, Схема 60сравнения 2 сравнивает этот выбранный кодс хранящимся в регистре 1 заданным кодомпризначной части,Возможны три результата сравнения:1) коды равны; 65 2) код из регистра 1 больше кода из регистра 3;3) код из регистра 1 меньше кода из регистра 3,Сигналы соответственно этим результатампоявляются на выходах 5, б и 7 схемы сравнения 2.Если код в регистре 1 больше кода из регистра 3, то сигнал с выхода б схемы сравнения 2 появляется на выходе 13 этого блока ивоздействует на счетчик блока 1 б таким образом, что он увеличивает свое состояние на2- (К - номер последнего младшего разряда, в котором записана единица).Если код в регистре 1 меньше кода из регистра 3, то сигнал с выхода 7 схемы сравн=ния 2 поступает на его выход 14 и далее насчетчик блока 1 б, который уменьшает свое состояние на 2 - ,Вновь сформулированный адрес дорожкисовместно с нулевым адресом числа передается в блок управления 4, и процесс повторяется,В том случае, если на -м шаге на выходе 5схемы сравнения 2 появляется сигнал, означающий, что запись с заданным признаком является первой на выбранной дорожке, т. е. имеетнулевой адрес, режим поиска заканчивается,так как этот сигнал поступает в блок управления, который прекращает дальнейший поискинформации и переключается на режим выборки найденной записи.Если же запись расположена не в началедорожки, то процесс поиска продолжается дотех пор, пока не будет произведено й=1 ортсравнений заданного п выбранного признаков,где т - число дорожек применяемого запоминающего устройства.Сигнал о выполнении К-го шага (или К-госравнения) вырабатывается счетчиком блока1 б и с выхода 17 поступает на вход блока 8.При этом имеют место два варианта дальнейшей работы устройства:1) код из регистра 1 больше кода призначной части первого числа выбранного на К-омшаге,2) код из регистра 1 меньше кода призначной части первого числа, выбранного на К-омшаге.Рассмотрим случай, когда записи в ЗУ расположены в порядке возрастания величины ихпризначной части. В первом случае на выходе б схемы сравнения 2 появляется сигнал, и устройство переводится в режим поиска адреса числа,С блока управления 4 на вход 11 блока 8 поступают сигналы разделительных меток записей на дорожке. Эти сигналы проходят в блок 20, который является обычным двоичным счетчиком; Одновременно с выделением разделительных меток записей производится сравнение кода призначной части записи последовательно, начиная с начала дорожки, с заданным признаком, хранящимся в регистре 1,342185 Предмет изобретения Составитель И, ФроловаТехред Т. Ускова Редактор Л, Утехина Корректоры: А, Николаева и Е. ДавыдкинаЗаказ 2004/13 Изд. И а 20 Тираж 406 Подписное ЦНИИПИ Колитета по делал изобретений и открытий при Совете Министров СССР Москва, Ж, Раунскан наб., д. 4/5 Типография, пр, Сапунова, 2 1 огда в последовательности записей на дорожке будет найдена искомая запись, схема сравнения 2 выработает сигнал равенства кодов на своем выходе 5, который прекращает поступление разделительных меток записей на вход блока 20. По этому сигналу 11 а выходе 5 схемы сраьнения 2, поступающему в блок управления 4, прекращается процесс поиска.Сформированные таким образом в блоках 1 б и 20 адреса дорожк 11 и числа соответственно передаются в блок управле:;пя 4, подготавливая его к режиму выборки найденной записи или ее переменной части. После окончания процесса выборки и, возможно, записи обработанной информации, блок управления 4 выдаст сигнал на вход 10 блока 8, после чего устройство готово и повторению процесса поиска.В случае, если код из регистра 1 меньше кода призначной части первого числа, выбранного на 1 х-ок 1 шаге, заслан 11 ой в регистр 3, схема сравнения вырабатывает на выходе 7 сигнал, которь 1 й поступает на выход 15 блока 8,По сигналу на выходе 15 блока 8 счетчик блока 20 уменьшает свое состояние на един;1- цу, т. е. возвращается на ранее просмотренную дорожку с номером яа единицу меньшим.Далее процесс протекает как в предыдущем слх чае. Устройство для поиска информации, содержащее регистры, подключенные к схеме сравнения, блок управления, соединенныи с логпским блоком, блоками формирования адресов 15 дорожки и числа, с однил 1 пз регистров и оло.ком выборки перемечной части числа, отличаюиееся тем, что, с целью сокращения времени поиска, и нем выходы схемы сравнения подключены к соответствующим входам логи ческого блока, выходы которого соединены солоками формирования адресов дорожки и числа.