Устройство для поиска информациипО пРизНАКу B блОКАХ пАМяТи СпРОизВОльНыМ дОСТупОМ Советский патент 1981 года по МПК G06F17/30 

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

в предлагаемом устройстве используется организация поиска информации типа дерево . Количество деревьев равно количеству храни1«1х коцов и равно 2. Корнями деревьев являются первые, га разрядов признака, разряды (т+1) и (т+2) признака определяют 4 дочерных ветви поискового дерева, разряды (т+3) и (т+4) признака определяют следующие 4 дочер- . них ветви и т.д.

Количество уровней (узлов) дерева определяется по формуле

,

где Р - количество узлов;

К - количество разрядов признака;m - количество разрядов признака, определяющее, количество деревьев.

На чертеже изображена структурная схема устройства.

Устройство содержит входной п-разрядный регистр 1, первый.. (т+ Н)-{разрядный регистр адреса 2, первый iH а копи те ль .3, первый Рт-разряцный регистр числа 4, второй (m+l)разрядиый регистр адреса 5, второй накопитель 6, второй Рт-разрядный регистр числа 7., третий п-разрчдный регистр числа 8, третий накопитель 9, третий, (т+1)-разрядный регистр адреса 10, основные 11 и 12 и дополнительные 13 регистры адресов свободных ячеек, (на чертеже изображен один дополнительный регистр) блока управления 14, выходной регистр 15; блок местного управления 16, входной канал 17, канал 18 передачи информации из входного регистра 1 в регистр адреса 2 разрядностью (т+1) , каналы 19 и 20 ... (всего - каналов) передачи содержимого, соответственно (т+1)-го и (т+ 5)-го ... разрядов входного регистра в первый разряд регистра адреса 2, подключенного к накопителю 3, каналы 21 и 22, ... (всего - каналов) передачи содержи.мого, соответственно (т+3)-го, (т+7)-го, ... разрядов входного регистра в первый разряд регистра адреса 5, подключенного к накопителю б, каналы 23-25.. ..., 26 (всего Р-каналов) передачи содержимого соответственно (т+2)-го (т+4)-го, (т+6)-го ..., к-го разряйов входного регистра 1 в блок управления 14,, канал 27 передачи информации из накопителя 3 в Ртразрядный регистр числа 4, выходы которого по каналу передачи 28 подключены ко входам накопителя 3, каналы 29 и 30 ... передачи и форма ции из (ifm)-ro и (m+l7-2m)-ro ,,. разрядов регистра числа 4 соответственно на входы разрядов со второго по (т+1)-ный регистра адреса 5, каналы 31 и 32 передачи информации с (Р-2) по (Р-1)т-ый и с (Р-1) по. Рт-ый разряды регистра числа 4 на входы разрядов со второго по ( регистра, адрес, 5, если Р - число четное, каналы 33 и 34 передачи информации соответственно с разрядов с (Р-2)т

nj-ro по (Р-1)т-ый и с (P-l) по Рт-ый на входы с первого по т-ый разрядов регистра адреса 10, если Р - число нечетное, каналы 35 и 36 ..., 37 и 38 передачи информации из регистра числа 4 группами по m разрядов на соответствующие входы схем сравнения блока 16, накопитель 6i, входы которого подключены к каналу 39 по входам Рт-разрядного регистра числа 7,канс1л 40 передачи информации из регистра числа 7 в накопитель 6, каналы 41 и 42, ,.. передачи информации с первого т-ый, с (т+1)-го по 2 т-ый, ... разрядов регистра 7 на входы со второго по (т+1)-ый разряд регистра гщреса 2, каналы 43 и 44 передачи информации с (P-i) по (P-l)mый и с (Р-l)m+ll-ro по Рт-разряды регистра 7 на регистр адреса 10 с первого по т-ый разряды, если Р число четное; каналы 45 и 46 передачи информации соответственно с {(P-2) по (Р-1)т-ый и с () по Рт-ый разряды регистра 7 на регистр адреса 2, если Р число нечетное, каналы связи 47 и 48, ... 49 и 50 передачи информа цни с выходом всех разрядов регистра числа 7 группами по т-разрядов

на cxeMJ сравнения блока анализа, регистр адреса 10,. подключенный к накопителю 9, канал 51, связывающий накопитель 9 с регистром числа 8| канал 52, подключающий выходы

регистра числа 8 ко входам накопителя 9, и канал 53, подключающий выходы регистра числа 8 ко входам . п-разрядного выходного регистра 15, который имеет связь с внш1ним объектом по каналу 54, каналы 55-57, подключающие основные 11 и 12 и дополнительные 13 регистры адресов свободных ячеек количество всех регистров равно Р) к регистру адреса 10; канал 58 передачи информации с разрядов l-rm регистра числа 8 в регистр адреса 5 (разряды 2т(т+1)) и в регистр числа 4 (разряды Irin и ( (m+l)-:-2m) , канал 59 передачи информации с регистра числа 8 (разряды (т+1-т21п) ) в регистр адреса 2 (разряды 27(т+1)) и в регистр числа 7 (разряды 1тт и (т+1) f2in) ,канал 60 передачи информации с разрядов (P-2)m+lf,{Р-1)т регистра числа 8, если Р - число четное, или канал 61 передачи информации с разрядов (P-Dm+lrPm регистра числа 8, если Р - число нечетное, в регистр числа 4 (разряды (P-2)m+l-r(P-l)ra и (Р-1)тч1тР1п и в. регистр адреса5 (разряды 2т()) , канал 62 передачи информации из регистра числа 8 (разряды (P-l)m+lfPm)) или канал 63 передачи информации из регистра числа 8(разряды (Р-2)т4-1т (Р-1)га в регистр числа 7 (Р-2)т+1т(Р-1)т и разряды (P-l)m+l-rPm) в регистр адреса 2 (разряды 2т(т+1)), канал 64 передачи информации из разрядов (P-l)m+lfPm регистра 8 в регистр гщреса 10 (разряды -ifm) , канал 65 передачи информации из регистрюв числа 4 (разряды 1тт и (m+l)f2in) в регистр числа 8 (разряды Irm), канал 66 передачи информсщии из регистра числа 7 (разряды (Irm), (m+l)-r2m) , канал 67 передачи информации из регистра числа 4 (разряды (Р-2)1п+1т(Р-1)т и (P-l)mr lfPin в регистр, числа 8 (разряды (P-2)m+lr(P-l)m), если Р - число четное, или канал 68 передачи информации из регистра числа 4 (разряды (Р-2)т+1т(Р-1)т и (P-Dm+lfPm) в per гистр числа 8, 1разряды (P-Dm+lfPm) если Р- число нечетное, канал 69 передачи информации из регистра числа 7 (разряды (P-2)m+l7(P-l)m и (Р-Dm+lfPm) в регистр числа 8 (разряды (P-DmrPm) , если Р- число четное или канал 70 передачи информации из регистра числа 7 (разряды (P-2)m+lf т(Р-1)т и (P-Dm+lT i) в регистр числа 8 (разряды (P-2)m+lf(P-l)m), если Р -число нечетное, каналы связи 71-73, ... , передающие сигналы с выхода блока упрг ления на входы регистров 11-13, ..., каналы 74 и

75 передгиоцие информацию с шлходов схем сравнения 76 и П блока 16 в .блок управления 14, канал связи 78 передачи информации из входного регистра 1 в регистр числа 8.

Устройство работает в следующих режимах;

режим приема кода; режим стирания кода; режим обмена информгщией с объектом, подключенным к каналу 5.

o

Поиск п-разрядиого кода по к-разрядной ПЕЖЗиаковой части в накопителе 9 начинается с нахождения корня поискового дерева по (т+2) разрядному признаку в накопителе 3, m

5 разрядов признака определяют адре-са четырех ячеек, в кото{&1х находятся четыре возможных корня, (т+1) разряд определяет размещение двух корней в адресах () или двух корней

0 в адресах (2 -Ит2 ) йакопителя 3, () разряд - конкретный корень дерева (1тт или (т+1) г2т разряды регистра числа 4), т.е. адрес ячейки, в которой записан гщрес четырех-пер5 вых ветвей данного признака в накопителе 6, (т+З) разряд признака определяет нахсякдение двух ветвей в адресах с первого по 2 -ый или двух ветвей в адресах с по накопителя 6, (ш+4)гразряд определяет кон® кретную первую ветвь дерева (Ifm или разряды регистра числа 7), т.е. адреса ячейки, в которой записан адрес четырех вторых ветвей данного признака в накопителе 3,

5

конкретную ветвь соответствующую

(.т+6 -разрядам П1 1знака, определяют разряды (т+5) и (т+6) признака и т.д. если Р - число нечетное, то ветви последнего уровня размещают0 с:я в накопителе 3 (разряды (Р-2)т+ +lf(P-i) или (P-Dm+l-rPm) , где указаи конкретный адрес ячейки накопителя 9, в которсМ записан код с поступившим юэизнаком, если Р число четное, то ветви последнего уровня размещаются в накопителе 6

(разряды (P-2)in+lr(P-l)m и (Р-1)т+ «тРга) .

Перед ыачгшом рабоп устройства

производится запись списков свободных ячеек в накопитель 9 в ячейки с адресом по , причем списки свободных ячеек первого уровня размещешл в разрядах с первого по

f ш-ый, списки свободных ячеек второго уровня в разрядах с (т+1) по 2т-ый и т.д.списки свобсщных ячеек Р уровня - в разрядах (Р-1)т+1тРт. Списки свободных ячеек организованы таким образом, что в каждой предыдущей ячейке записаны адреса следующих свободных ячеек. Адреса первых свободных ячеек должны храниться в регастрах адресов свободных ячеек 11-1Заорганизованных на счетчиках

5 еяиниц.

В режиме приема кеда, п-разрядный код поступает на входной регистр 1 по каналу 17, Поступивший код необходимо записать в ячейку накопителя 9 или найти в накопителе 9 ранее поступивший код с такой же признаковой частью. Поиск информации с данной признаковой частью или поиск адреса свободной ячейки для записи данного кода ведется по признаку разрядностью К и Р : этапов. На первом этапе объединяются все коды по (т+2) разрядам признака образуя так называемое корни дерева поиска, размещенные в накопителе 3 по адресу ,. причем с первого по т-ый разряды признака являются непосредственным адресом корня. Информация с первого по т-ый разряды признака со входного регистра 1 по кансшу 18 поступает на входы регистра адреса 2, информация с разряда (т+1) признака поступает по каналу 19 на первый разряд регистра 2, определяя первую или вторую половину накопителя, в ячейке которой будет записан корень дерева, разряд (т+2) признака определяет разряды Irm или (in+l)-r2m накопителя 3, в указанных разрядах записан адрес четырех первых ветвей дерева поиска. На втором этапе определяется размещение одной из четырех первых ветвей дерева поиска и нахождение адреса четырех следующих ветвей, информация с первого по т-ый или с (т+1).по 2т-ый разряды регистра 4 поступает на разряды 2-7 (т+1) регистра адреса 5 по каналу 29 или 30, информация с разряда (т+3) входного регистра 1 по кангшу 21 поступет на вход первого разряда регистра адреса 5 и определяет адрес двух первых ветвей дерева поиска,по состоянию разряда (т+4), который расшифровывается блоком управления 14. определяется группа разрядов tlrm) или (т+1)т2т накопителя б, где хранится первая ветвь дерева для (т+4)разрядов признака, в указанных разрядах записан адрес четырех следующих ветвей дерева поиска.

Натретьем этапе определяется размещение одной из четырех ветвей второго уровня и нахождение адреса четырех ветвей третьего уровня инфомации с первого по т-ый или с (т+1) по щ-ый разряд регистра числа 7 поступает на разряды 2rm+l регистра адреса по каналу 41 или 42, информация с разряда (т+5) входного регистра 1 по каналу 20 поступает на вход первого разряда регистра адреса 2 и определяет адрес двух ветвей второго уровня дерева поиска, по состоян разряда (т+6) входного регистра 1, которвой расшифровывается блоком управления 14 определяется группа разрядов (2m+l)f3m) или (3m+l)f4m накопителя 3, где хранится ветвь второго уровня для (т+6) разрядов признака, в указанных разрядах записан адрес четырех ветвей третьего уровня в накопителе 6 и т.д. На последнем Рэтапе находятся последние четыре ветви дерева, которые хранятся в накопителе 3, Ацрес одной из четырех последних; ветвей, относящихся к К-разрядному признаку, определяет разряды (К-1) и К-ый входного регистра 1, В выбранной ячейке хранится адрес кода с признаком К, записанного в накопителе 9, информация с регистра числа 4 по каналу 33 или 43 и 44 поступает в регастр адреса 10.

5 По этому адресу производится обращение к накопителю 9 и выбранный код с поступившим К-образным признаком передается из 1 егистра числа 8 по каналу 51 на выход 1ой регистр

0 1Ь.

Наличие ветви на любом уровне определяется наличием числа, отличительного от нуля в разрядах (),

5 (m+lv2m) , (2m+lt3m), . . . ( (P-Dm+lfrPm) регистров числа 4 или 7 в зависимости от этапа поиска. Определение наличия ветви выполняется схемами сравнения 76 и 77 блокаiaHajiH0 за 16, Наличие ветви на всех Р уровнях означает наличие кода с поступившей признаковой частью в накопителе кодов 9, в противном случае код новый и следует определить его

5 место в накопителе кодов 9, т.е,

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

0 ветвями, соответствующими (К-т) разрядам признака.Если на первом этапе поиска в выбранной группе разрядов регистра числа 4 записано число равное нулю, что означает отсут5 ствие кодов с (т+2) разрядной признаковой частью в накопителе кодов 9, по адресу, который хранится в регистре 11 производится обращение за адресом свободной ячейки в раз0 РЯДЫ (1тт) накопителя 9, адрес свободной ячейки из разрядов (ifm) регистра числа 8 по каналу 56 записывается в разряды (ifm) или (m+l-f72ш) регистра числа 4 и соответст- венно в накопитель 3, в зависимости от состояния (т+2) разряда признака в регистр адреса 5, К числу, .записанному в регистре 11 прибавляется единица. По адресу, который хранится в регистре 12, производит0 ся обращение за адресом свободной ячейки к накопителю 9, адрес свободной ячейки из регистра числа 8 записывается в регистр числа 7 по ка;налу 59 и соответственно в накопи5 1тель бив регистр адреса 3 для

занесения адреса ветви третьего уровня, К числу,записанному в регистре 12 прибавляется единица.

На последнем Р этапе по адресу, который хранится в регистре 13 производится обращение к накопителю 9 за адресом, свободной ячейки, адрес свободной ячейки из регистра числа 8 записывается по каналу 61 в регистр числа 4, в зависимости от состояния К разряда признака., и соответственно в накопитель 3, если Р число начетное, или из регистра числа 8 записывается по каналу 60 в регистр числа 7 и соответственно в накопитель 6, если Р -. число четное и в регистр адреса 10 для занесения в накопитель 9 вновь поступившего кода. К числу,записанному в регастре 13,прибавляется единица. Дополнять дерево поиска можно с любого уровня, как только обнаружено, что, поступивший код с К-разрядным признаком новый.

В режиме стирания код, записанный в накопителе 9,стирается и соответственно стираются ветви в дереве поиска, относящиеся именно к ксщу с данным признаком. Для этого на регистр 1 записывается стираемый код с К - разрядной призначной частью. По описанному выше алххэритму находится корень дерева, в котором записан адрес четырех первых ветвей дерева поиска, по данному адресу производится обращение к накопителю б и если, в накопителе б хранится только одна ветвь первого уровня,соответствующая коду с поступившим признаком, то содержимое разрядов Ifra или m+1-r -г2т регистра числа 4 (в зависимости от состояния m-f-2-ro разряда признака) переписывается в регистр числа 8 и соответственно в накопитель 9 по адаесу, предшествующему адресу, который Х1 анится в регистре 11 и адрес первой ветви дерева в накопителе 3 стирается, если в накопителе б хранится две или более первых ветвей, то информация, соответствующая данному коду сохраняется. По описанному выше алгоритму находится первая ветв гае хранится адрес следующей ветви, по данному адресу производится об ращение к накопителю 3 и ,если в накопителе 3 хранится одна ветвь второго уровня, соответствующая ксэду с поступившим признаком, то содержимое разрядов ifm или (m+l)r2m регистра числа 7 (в зависимости от состояния (т+4) разряда признака) переписывается в регистр числа 8 (разряды m+l72m) и соответственно в накопитель 9 по адресу, предшествутещему адресу, которлй хранится в регистре 12 и адрес ветви второго уровни в накопителе 6 стирается, если в накопителе 3 хранится две или более ветвей третьего уровня, то информация, соответствующая данному признаку сохраняется и т.д.

На уровне Р адрес из разрядов (P-2)m+l7(P-l)m или (P-Dm+lrPm регистров числа 4 или 7, в зависимости от состояния разряда К - признака и от четности числа Р переписывается в регистр числа 8 (разряды (Р-1)т+1тРт) и соответственно в накопитель 9 по адресу, предшествующему адресу, который хранится в регистре 13, выбранный адрес соответственно в накопителе 3 или б стирается, стирается и код,соответствующий признаку К в накопителе- 9.

В режиме обмена информацией на регистр 1 поступает код или его призначная часть, по алгоритму поиска определяется адрес поступившего ранее кода с таким же признаком. Данный код выбирается из накопителя 9 и с .регистра 8 информация выдается на выходной регистр 15.

Предлагаемая организация информационного массива значительно увеличивает быстродействие данного устройства. Так, например при (K-in)5 быстродействие устройства при данном техническом решении увеличивается примерно в 10 раз,по сравнению с известным, при {К-т)б - примерно в 20 раз, при (к-т)7 - примерно в 30 раз, при (К-т)8 - в 60 раз и т .д.

Формула изобретения

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

нительные регистры адресов свободных ячеек и третьи регистр адреса, накопитель и регистр числа, причем входы третьего регистра числа подклюЧены соответственно к другим информационным выходам первого и второго регистров числа, другому выходу входного регистра и выходу третьего иакопителя, выходы третьего регистра числа соединены соответстве нно с други1«и входами регистров адреса и регистров числа, соединены соответственно с первым входом третьего накопителя, со вхоцом выходного регистра и с одним из входов третьего регистра адреса, иаход которого соединен со вторым входом третьего накопителя, другие входы треГг

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР № 407315, кл. G Об Р 1/00, 1971. 2. Авторское свидетельство СССР № 454561, кл. G 06 F 15/40, 1972 (прототип).

ITT

52

5И