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

СОЮЗ СОВЕ СОЦИАЛИСТ РЕСПУБЛИК СКИХСКИХ 10087 6 Г 15/4 фЩЪв ъма ОПИСАНИЕ ИЗОБРЕТЕНИ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ахотенкоСР 00 м блоорой информационный выход б вания адреса подключен ному входу регистра ад единичного признака бл ния адреса соединен с памяти последователь ормир ормац н к и еса вход а Ф рмиров м блок ыход о до мент но докьнои выход блока памят СУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(56) 1. Черный А.И, Введение в теорию информационного поиска, М.,Наука", 19752. Авторское свидетельство СССР й 454561, кл. О 06 Г 15/40, 1972 (прототип).(54)(57) 1. УСТРОЙСТВО ДЛЯ ПОИСКА ИН. ФОРМАЦИИ, содержащее регистр ввода, блок памяти, информационные вход и выход которого соединены соответственно с первыми информационными выходом и входом регистра числа, блок памяти документальной информации, адресный вход которого соединен с выходом регистра адреса блок анализа условий перехода, первый вход которого соединен с выходом признака регистра числа, регистр вывода, управляющий вход которого и управляющие входы регистра ввода, блока памяти, регистра адреса, регистра числа, блока памяти документальной информации, регистра вывода и блока анализа условий перехода соединены с соответствующими выходами блока микропрограммного уп равления, выход регистра вывода является информационным выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повыщения быстродействия и экономии объема памяти для хранения поисковых признаков, в него введены блок памяти последовательного доступа, блок формирования адреса, блок сложения-умножения,блок памяти магазинного типа, блокбуферной памяти, счетчик, управляющие входы которых соединены с соот"ветствующими выходами блока микропрограммного управления, и дещифра"тор, выход котооого подключен к входу выбора регистра ввода,. выходыкоторого соединены соответственнос адресными входами блока памяти,информационные входы регистра вводасоединены с выходом блока буфернойпамяти, информационный вход которого является информационным входомустройства, выход счетчика соединенс входом дешифратора и с вторым входом блока анализа условий перехода,выход которого подключен к первомувходу блока микропрограммного управления, второй вход которого соединенс управляющим выходом блока формирования адреса, информационный входкоторого соединен с первым информационным выходом блока сложения-умножения, первый информационныйвход и второй информационный выход которого соединены соответственно с вторыми информационными выходом и входом регистра числа, второй информационный вход и третий инФормационный выход блока сложения-умножения соединены соответственно синформационным выходом и входака памяти магазинного типа, вт1 ОО 8752 1 О 15 Формации соединен с информационным входом регистра вывода.2. Устройство по и, 1, о т л ич а ю щ е е с я тем, что блок форми рования адреса содержит вычитающий и суммирующий счетчики, элементы И, ИЛИ, дешиФратор нулевого состояния и регистр выходы которого являются информационным выходом блока, информационные входы регистра соединены соответственно с выходами суммирующего счетчика, управляющий вход реги стра подключен к выходу первого элемента И,. выход дешифратора нулевого состояния подключен к первому входу первого элемента Ии к управляющему выходу блока, входы соединены соот-ветственно с выходами вычитающего счетчика, второй вход первого элемента И соединен с выходом элемента ИЛИ, вход которого и первый вход втр рого элемента И соединены с входом единичного признака блока, первые входы вычитающего и суммирующего счетчиков соединены с первым управ" Изобретение относится к вычислительной технике,Известны системы для поиска инФормации, построенные на основеприменения Электронных вычислительных машин,В этих системах поисковое предписание представляет собой, как правило, неупорядоченный набор признаков. Поиск по заданным признакамосуществляют путем многократногопоследовательного просмотра массивазаписи, либо путем многократного про.смотра цепей ссылок1. Недостатком устройства является требование большого количества машинного времени при решении задач, связанных с многоступенчатым поиском информации в больших массивах данных, большой объем памяти внешних устройств, большая сложность и высокая стоимость всей системы, сложность процедур обновления информации и особенно удаление исключаемых записей, когда они связаны с другими записями системой сложных ссылок; тру. ляющим входом блока, второй управляющий вход которого подключен к второму входу второго элемента И и к второму входу вычитающего счетчика, информационные входы которого соединены с информационным входом блока, выход второго элемента И подключен к второму входу суммирующего счетчика.3. Устройство по и. 1, о т л иц а ю щ е е с я тем, что блок анализа условий пеоехода содержит элемент ИЛИ, дешифратор нулевого состояния и элементы И, первые входы которых и управляющий вход дешифратора нулевого состояния соединены с управляющим входом блока, вторые входы элементов И подключены к первому входу блока, информационные входы дешифратора нулевого состояния соединены с вторым входом блока, выход дешифратора нулевого состояния и выходы элементов И соединены соответственно с входами элемента ИЛИ, выход которого является выходом блока. доемкая процедура индексации и составления поисковых предписаний,Наиболее близким к предлагаемому является устройство для информацион 5 ного поиска по признаку в памяти с произвольным доступом, содержащеевходной регистр, запоминающее устройство произвольной выборки для хранения служебной информации и поисковых признаков, подключенное к регистру цисла, запоминающее устройство произ.вольной выборки для хранения документальной информации, подключенноек регистру адреса, блок анализа,подключенный к регистру числа, блок управления и выходной регистр.В этом устройстве поиск информации производится по составному признаку в памяти с произвольным доступом, имеющей многоступенчатую организацию массива данных путем последовательного многоступенчатого сравнения признаковых частей входногокода с признаковыми частями массиваданных 2. Недостатком этого устройства является невысокое быстродействие при3 1 оо 87решении информационно-поисковых задач, что связано с большим количеством операций последовательного перебора и сравнения и большой объемпамяти, обусловленный необходимостью 5раздельного хранения повторяющихсячастей различных поисковых признаков., Цель изобретения - повышение быст.родействиА и экономия объема памяти 1 вдля хранения, поисковых признаков.Поставленная цель достигается тем,что в устройство для поиска информации, содержащее, регистр ввода, блокпамяти, инФормационные вход и выход 1которого соединены. соответственно спервыми информационными выходом ивходом регистра числа, блок памятидокументальной информации, адресныйвход которого соединен с выходом ре- щгистра адреса, блок, анализа условийперехода, первый вход которого соединен с выходом признака регистрачисла, регистр вывода, управляющийвход которого и управляющие входы ре згистра ввода, блока памяти, регистраадреса, блока памяти документальнойинформации, регистра .вывода и блокаанализа условий перехода соединеныс соответствующими выходами блокамикропрограммного управления, выходрегистра вывода является информационным выходом устройства, введены блокпамяти йоследовательного доступа,блок Формирования адреса, блок сложения-умножения, блок памяти магазинного типа, блок буферной памяти,счетчик, управляющие входы которыхсоединены с соответствующими выходами блока микропрограммного управле 40ния, и дешифратор, выход которогоподключен к входу. выбора регистра.ввода,.выходы которого соединенысоответственно с адресными входамиблока памяти, информационные входырегистра ввода соединены с выходом4блока буферной памяти, информационный вход которого является информационным входом устройства, выходсчетчика соединен с входом дешифратора и с вторым входом блока анализа фусловий перехода, выход которого под.ключен к первому входу блока микропрограммного управления, второй входкоторого соединен с управляющим выходом блока формирования адреса, информационный вход которого соединенс первым информационным входом блока сложения-умножения, первый инфор 52 4мационный вход и второй информационный выход которого соединены соответственно с вторыми информационными выходом и входом регистра числа, второй информационный вход и третийинформационный выход блока сложенияумножения соединены соответственно с информационными выходом и входом блока памяти магазинного типа, второй информационный выход блока формирования адреса подключен к информационному входу регистра адреса, вход единичного признака блока формирования адреса соединен с выхоЮдом блока памяти последовательногодоступа, выход блока памяти документальной информации соединен с инФормационным входом .регистра выво-да.Кроме того, блок формирования адреса содержит вычитающий и суммирующий счетчики, элементы И, ИЛИ, дешифратор нулевого состояния и регистр, выходы которого являются инФормационным выходом блока, информационные входы регистра соединены соответственно с выходами суммирующего счетчика, управляющий вход регистра подключен к выходу первогоэлемента И, выход дешифратора нулевого состояния подключен к первому входу первого элемента И и к управляющему выходу блока, входы соединены соответственно с выходами вычитающего счетчика, второй вход пер-вого элемента И соединен с выходом элемента ИЛИ, вход которого и первый вход второго элемента И соединены с входом единичного признака блока, первые входы вычитающего и суммирующего счетчиков соединены с первым управляющим входом блока, второй управляющий вход которого подключен к второму входу второго элемента И и к второму входу вычитающе го счетчика, информационные входы которого соединены с информационным входом блока, выход второго элемента И подключен к второму, входу суммирующего счетчика.Блок анализа условий перехода в устройстве содержит элемент ИЛИ, дешифратор нулевого состояния и элементы И, первые входы которых и управляющий вход дешифратора нулевого состояния соединены с управляющим входом блока, вторые входы элементов И подключены .к первому входу блока, информационные входы дешиф В 10087ратора нулевого состояния соединены с вторым входом блока, выход дешифратора нулевого состояния и выходы элементов И соединены соответственно с входами элемента ИЛИ, выход 5которого является вйходом блока.На фи . 1 представлена блок-схе-ма устройства; на фиг, 2 - схемаблока формирования адреса; на фиг. 3схема блока анализа условий перехода; на Фиг; 4 - схема блока микропрограммного управления; на. Фиг, 5приведен алгоритм работы устройства.Устройство содержит блок 1 буферной памяти, регистр 2 ввода, блок 3памяти, регистр 4 числа, блок 5 сло-,жения-умножения, блок 6 памяти магазинного типа, блок 7 памяти последовательного доступа, блок. 8 памяти до- уокументальной информации, блок 9 Формирования адреса, регистр 10 адреса,счетчик 11, дешифратор 12, блок 13анализа условий перехода, регистр 14вывода, блок 15 микропрограммного 25управления, информационный выход 16устройства, вычитающий счетчик 7,суммирующий счетчик 18, дешифратор19 нулевого состояния, регистр 20,элементы И 21, 22, элементы ИЛИ 23,дешифратор 24, группа элементов И 25,элемент ИЛИ 26, узел 27 памяти, регистр 28, дешифратор 29 номера полямикроопераций, генератор 30 тактовыхимпульсов, элементы И 31, 32, группыэлементов И 33-35, элементы И 36,37, элементы ИЛИ 38, 39, выходы 40управляющих сигналов, шаги 4 1-69 алгоритма работы устройства.На Фиг. 5 обозначены: поисковыепредписания - ПП для информации,хранящейся в ячейке блока 3 памяти;значение - д служебного элемента"Конец серии", которое равно единице, если рассматриваемый символ по 45следний в серии, в противном случаеравно нулю; значение - дкп служебного элемента "Конец признака", равное .единице, если рассматриваемый символопределяет висячую вершину, в против 50ном. случае равно нулю; значениедот служебного элемента, хранящегосяв ячейке корневой вершины и равноеединице, если символы серии нижележащего уровня, выходящей из даннойвершины, находятся в,конъюнктивныхотношениях, в противном случае равное нулю; значение - до служебногоэлемента, хранящегося в ячейке корне 52 4вой вершины, связанной с серией символов (вершин) нижележащего уровня, находящихся в конъЮнктйвных отношениях друг .с другом и равное единице, если было обращение к этой серии при расчете добавки Ф для данной корневой вершины; в противном случае равное нулю; числовое значение - с 1 ын хранящееся в информационной части ячейки и используемое для расчета э на чений доба вки 0Для составных частей устройства приняты обозначения: регистр 2- ВхРг счетчик 11 - СчУр; блок 1 БФПр; запоминание служебной информации в блоке 3 - ЗУС; регистр 4 Ргц: блок 5 - ЬСУ; блок 6 - ЗУМ; блок 7 - ЗУПД; блок 8 - ЗУДИ; блок 9 - СхфА; вычитающий счетчик блока 9 - СхФА 1; суммирующий счетцик блока 9 - СхФА 2; регистр 14- ВыхРг.В основу этого алгоритма положена возможность сведения информационного поиска к вычислениям. Эта возможность реализуется, если в каждой конкретной совокупности объектов превращаются отдельные признаки объектов в своеобразные разряды системы счисления - в цифры в этих разрядах, В этом случае набору свойств любого объекта будет поставлено в соответствие определенное натуральное число - только ему присущий номер в естественной системе счисления. И наоборот, по номеру всегда можно воссоздать набор свойств соответствующего объекта.Данный алгоритм основан на использовании системы счисления, имеющий много оснований и древовидные Фигуры числа, так называемой обобщеннополиадической системе счисления. Такой подход позволяет построить новый механизм памяти, в котором удается избежать создания массивов и использования .процесса информационного поиска. Запоминающая система с этим механизмом не является хранилищем пообъективных записей, поэтому нет массивов и, как следствие, нет основы для процесса поиска.В целом механизм памяти состоитв следующем.Все признаки и градации признаков, которые могут встретиться хотя бы у двух объектов запоминаемой совокупности, объединены в структурекомбинаторного дерева, где призна7 1008752 8ки и их альтернативные градации про- ПОД задается совонумерованы, йоэтому набор признаков ных признаков, находобъекта, который надо запоминать, тивных отношениях дробозначится как дерево номеров. Ино- дый признак, состоитжеству объектов соответствует мас- э имеет иерархическуюсив таких деревьев. Каждое дерево дый символ определяеномеров рассматривают как фигуру хических уровней даннекоторого числа в обобщенно-полиа- ПОД графически можнодической системе счисления и пере- виде древовидной стрводят это число в десятичную (двой любой иэ составных иную и т.п.) систему. Получают деся- ных ПОД с верхнего утичный номер Ф - естественный номер либо из нижележащихданного объекта. Иножеству объек- общие символы с другтов, таким образом, соответствует Совокупность ПОД храмассив естественных ноюеров этих И бинаторного дерева,объектов. Но массив номеров не соз- чески предствляет содают, Вместо него берут запоминающую структуру, полученнустроку битов, первоначально сплошь друг на друга древовзаполненную нулями. В эту строку в ПОД. Таким образом,соответствии с десятичным номером в 20 дерево представляет4-й по счету бит от начала строки лективный портрет созасылают битовую единицу,чем.и завер- на котором различныешается запоминание признаков данно- идентичным частям иго объекта, В конечном итоге в за- от друга оригинальныпоминающей строке можно будет обна щими) признаками илиружить столько битов единиц, сколь- В этом случае каждыйко объектов было предъявлено для за- вого признака будетпоминания, Каждый объект запоминает- которую вершину комбся как своеобразная битовая точка, рева.находящаяся в строке на вполне опре- зв Такой способ хранделенном расстоянии от ее начала. ти ПОДов позволяет иЭто расстояние всегда равно номеру признаков получать иобъекта. Каждый номер и массив номе- соответствующие новыров можно восстановить, измерив рас- но возможным, но ранстояние всех битовых единиц от нача- ным ПОДам. Различныела строки, Те признаки, которые свой- и того же уровня, прственны только данному объекту, не признакам, которыевключают в комбинаторное дерево, а символы на всех вышехранят отдельно в виде фактографи- образуют серию симвоческого паспорта объекта, Паспортов этой серии находятсястолько, сколько запомнено объектов ных (альтернативных)и, следовательно, сколько единиц с другом, если они ихранится в запоминающей строке битов. накам, которые не моКоличество битовых единиц, от нача- нены в один ПОД, в ила запоминающей строки битов опреде- символы серии находяляет номер паспорта в упорядочненном ных отношениях.спике паспортов. Паспорт извлекают Любая вершина, вхпо этому номеру (адресу) методом пря- наторное дерево призмого доступа. некоторое комбинаторЭти особенности обеспечивают высо" Это поддерево можеткое быстродействие устройства и зовано определенной,.уменьшение объема памяти для хране- ристйкой - комбинатания поисковых признаков, Комбинато ная м нос Перед описанием работы предлаемого устройства рассмотрим особеннос- фф ти задания и хранения поисковых предписаний и поисковых образов документов (ПОД) . купностью составящихся в.конъюкуг с другом. Кажиз символов иструктуру. Кажт один иэ иерарного признака.представить вуктуры, т.е.ризнаков заданровня до какогоуровней иметьими признаками.нится в виде комкоторое графибой древовиднуюю от наложенияидных структуркоь 6 инаторноесобой как бы кол"вокупности ПОДов,ПОД совпали поотличаются другми (не совпадаюих частями.символ поискоопределять неинаторного деения совокупносри выделениих комбинации,м принципиальее не записансимволыодногоинадлежащиеимеют общиележащих уровнях,лов. Символыв дизъюнктивотношениях другринадлежат призгут быть объедиротивном случается в конъюнктив- одящая в комбинаков, выделяетное поддерево.быть охарактеричисловой характе.рной мощностью.р ощ ть - это макси"мально возможное количество древовидных структур, если признаки (символы), определяющие эти структуры,могут быть объединены в одном ПОД.Такая характеристика правомерна идля комбинаторных поддеревьев, что,(е)д =7. и 1 (О 1),.ели для вершины вышележащего уровняЬт:О,010 1(Ед и ке ф ( О А 1:1 ф 1 если для вершины вышележащего уровНЯ Ьвт = 11Работу устройства можно описатьследующими шагами.а) Прием признаков поискового предписания в блок 1 (БФПр).б) Начальная. установка. Обнуление 20 ВхРг, СчУр, регистров БСУ.в) Прием очередного признака поискового предписания во ВхРг и определение числа уровней рассматриваемого 1признака путем подсчета в нем количества символов в СчУр.г) Обращение к ячейке ЗУС, соответствующей корневой вершине вышележащего уровня, для определения принадлежности данного символа (вершины) к конъюнктивной или дизъюнктивной серии если символ принадлежитк конъюнктивной серии, то переходк шагу 7 (содержимое СчУр, .считывание содержимого ячейки ЗУС в РгЧ упо адресу заданному во ВхРг, еслидо.=1, то перейти к шагу 4 ж).д) Обращение к ячейке ЗУС, соответствующей рассматриваемым символам, сложение Ьн с содержимым БСУ. 40 (Содержимое СчУр+1, считывание ячейки ЗУС в РгЧ по адресу заданному во ВхРг, ,Ь 11+содержимое БСУ).е) Если рассматирваемый символ (вершина) принадлежит первому уров ню, то перейти к шагу 5 с, в противном случае перейти к шагу 4 г). (Содержимое СчГр, проверка блоком анализа содержимого СчУр-на равенство нулю. Если содержимое СчУр=0, то я перейти к шагу 5 с, в противном случае к шагу 4 г).ж) Если обращения к рассматриваемой серии не было, то перейти к шагу 5 м (если Ь в = О, топереход к шагу Иов =5 м) .1и) Содержимое ЗУМ сложить с содержимым БСУ. 12к) Если рассматриваемый конъюнктивный символ последний в серии, топерейти к шагу О,(Содержимое СчГу+1, считывание ячей.ки ЗУС в РгЧ по адресу, заданномуво ВхРг, Если Ь = 1, то переход кшагу О).л ) Содержимое БСУ записать в ЗУИ,перейти к шагу б).м) Зайиксировать обращение к данной конъюнктивной серии, перейти кшагу К,(В элемент РгЧ для хранения Ьо записать единицу, -.одержимое РгЧ пе"реписать в ячейку ЗУС по адресу, заданному во ВхРг, перейти к шагу к);о) Если рассматриваемый символ(Содержимое СчУр 1, проверка блокоманализа содержимое СчУр на равенство нулю, Если содержимое СчУр=0, топерейти к шагу с).и) Обращение к ячейке ЗУС соответствующей корневой вершине вышележащего уровня, перемножение ЬИ с содержимым в БСУ.(Считывание содержимого ячейки ЗУСв РгЧ по адресу, заданному во ВхРг.Ь 1,н умножить на содержимое .БСУ).р) ЗаФиксировать конец обращенияк данной конъюнктивной серии, перейти к шагу г.(В элемент РгЧ для хранения Ь Б Эа"писать содержимое РгЧ переписать в .ячейку ЗУС по адресу, заданному воВхРг Перейти к шагу г).с ) Считывание из запоминающейстроки битов, записанной в ЗУПД,бита инФормации, местоположение которого определяется результатом вычислений, хранящимся в БСУ. Одновременное определение количества би- -товых единиц от начала запоминающейстроки до данного бита. Если значение считанного бита равно единице,то перейти к шагу т, в противном случае - к шагу у.(Содержимое БСУ переписывается вСхФА, производится последовательноесчитывание инФормации иэ ЗУПДг Еслизначение последнего считаныого битаравно единице, то адрес сФормированный СхФА выдается в РгА и переходк шагу т, Если значение считанногобита равно нулю, то переход к шагу у).т ) Считывание из памяти ЗУДИ ФактограФического паспорта по адресуопределенному в шаге С и соответ08752 14 5 10 Каждая микрокоманда содержит информацию о микрооперациях, выполняемых в течении одного такта, а также информацию, обеспечивающую формирова ние адреса очередной микрокоманды,Каждый шаг алгоритма работы устройства реализуется микропрограммами, которые состоят из нескольких микрокоманд. При выполнении микропрограмм в каждом такте производится выборка одной микрокоманды и ее преобразование в набор управляющих сигналов. Каждая микрокоманда разделяется на ряд частей или полей, преобразуемых в управляющие сигналы автономно. Элементы И и дешифратор осуществляют преобразование части микрокоманд, содержащей информацию о микрооперациях и хранящейся в узле 27 в управляющие сигналы, Регистр 28 устанавливается в нулевое состояние при начальной установке, наращивается на единицу в случае естественного перехода, принудительно устанавливается в соответствии с адресом перехода хранящимся в узле 27 памяти в случае наличия управляющих сигналов: безусловного перехода УС (БП), условного перехода по результатам анализа сигналов из блока 9 Формирования адреса УС условного перехода по результатам анализа сигналов из блока 13 анализа условий перехода.Работа блока 15 осуществляется по тактовым импульсам, формируемым схемой генератора тактовых импульсов.При поступлении на вход счетчика 17 управляющего сигнала с блока 15 30 13 10 ствующему количеству битовых единиц в строке битов. Выдать информацию о найденном документе и перейти к шагу а.(Считывание информации из ЗУДИ по ад ресу, хранящемуся в РгА, выдача ее в ВыхРг, переход к шагу а).у) Выдача информации об отсутствии документа..(Считывание информации из ЗУДИ по ну левому адресу, заданному в РгА).Основные управляющие сигналы вырабатываются в блоке 15 за счет последовательного считывания и расшифровки информационных слов (микрокоманд), располагающихся в ячейках отдельного постоянного (полупостоянного) узла 27 памяти (фиг. 4). информация с выхода блока 5 записывается в счетчик 17 одновременно обнуляется счетчик 18Затем по управляющим сигналам с блока 15 производится последовательное уменьшениена единицу содержимого счетчика 17и одновременное считывание информации из ячеек блока 7 памяти последовательного доступа, начиная с нулевой. При появлении нэ выходе блока 7 единицы, содержимое счетчика 18увеличивается на единицу. Сигнал обобнулении содержимого счетчика 17вырабатывается дешифратором и выдается в блок 15. По этому сигналу из блока 15 выдается управляющий сигнал для переписи информации со счетчика 18 в регистр 10 адреса. Однако, если при этом на выходе блока 7присутствует нуль (отсутствие документа в блоке 8), то регистр 10 адреса обнулится, а записи информации со счетчика 18 не произойдет,По следующему управляющему сигналу с блока 7 производится считывание из блока 8 информации по адресу,содержащемуся в регистре 10 адресаи выдача ее в регистр 14. Таким образом, в зависимости от содержимого регистра 10 адреса в регистр 14 поступит информация о найденном в блоке 8 документе, либо (РгА=О) об отсутствии документа.Блок 13 служит для выработки условий перехода при работе устройства по алгоритму, На выходах элементов И 25 появляется сигнал о состоянии разрядов регистра 4 числа адекватных служебных элементов ок 1 1 до, дКс, при наличии соответствующих управляоцих сигналов из бло.ка 15, причем в любой микрокомандеможет присутствовать лишь один изэтих управляющих сигналов, На выходеэлемента ИЛИ 26 появляется сигналпри выполнении любого из условий,проверяемых блоком 13. Устройство позволяет заменить процесс поиска информации путем последовательного перебора и сравнения заданных признаков на процесс непосредственного вычисления адреса этой информации по заданным признакам, а также сократить объеМ памяти, не;.обходимой для хранения поисковых признаков, за счет использования комбинатооного подхода при их хранении.