Ассоциативное запоминающее устройство Советский патент 1992 года по МПК G11C15/00 

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

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

На фиг.1 представлена блок-схема устройства; на фиг.2 - структура поискового дерева, записанная в адресном накопителе; на фиг.З - алгоритм ассоциативного поиска последовательностей произвольной длины. Основу устройства составляет регистр 1, вход которого является информационным входом устройства, а выход подключен к первому информационному входу компаратора 2, блок 3 памяти, каждая ячейка 4 памяти которого содержит поле 5 символов, поле 6 указателей и поле 7 признаков, причем выход поля 6 указателей 6 подключен к первому информационному входу сумматора 8, второй информационный вход которого является входом Единичное приращение, а к третьему информационному входу подключена его информационная выходная шина, подключенная также к адресному входу блока 3 памяти и информаци- онному устройству и одновременно является информационным входом устройства, выход поля 7 признаков подключен к входу Признак поиска блока 9 управления, управляющие входы Запись, Признак конца последовательности, Поиск и управляющие входы Положительный результат поиска, Ошибка, Запрос являются управляющими входами и выходами устройства, выходы х1 и х2 подключены к управляющим входам записи и чтения входного регистра 1, выход хЗ соединен с управляющим входом компаратора 2,

управляющий выход которого соединен с входом Наличия совпадения у4 блока 9 управления, выход х4 подключен к управляющему входу выборки 3 памяти вход Признак поиска у5 является информационным

входом и соединен с выходом поля 7 признаков, выход хб соединен с входом Код операции сумматора 8, а выходы х5, х7, х8 подключены к управляющим входам приема информации соответственно с первого,

второго и третьего входом сумматора 8.

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

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

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

На первом уровне поискового дерева, начиная с нулевого адреса, выделены 32

ячейки, которые и составляют первый уровень.

На втором уровне выделены 32 блока каждый по 32 ячейки, а на третьем уровне содержится 1024 блока по 32 ячейки.

Причем в ячейках первого уровня содержатся начальные адреса блоков второго уровня, в 1024 ячейках второго уровня содержатся начальные адреса блоков третьего уровня, а в 32768 ячейках третьего уровня

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

В полях символа 5 и указателя 6 ячеек 4 первых трех уровней содержатся начальные адреса соответствующих блоков ниже- лежащих уровней, а для ячеек четвертого и ниже уровней в поле символов 5 хранятся коды букв хранимых последовательностей, в поле 6 указателей приращения адресов между соседними ячейками 4 блока ячеек 4.

В поле 7 признаков всех уровней хранятся признаки конца последовательности и конца блока.

Фрагмент структуры поискового дерева для хранения корневых морфем приведен на фиг.2. Здесь показаны те участки структуры, в которых хранятся морфемы:

БА

БАЛ

БАЛАБОЛ

БАЛАБОШ

БАЛАГАН

БАЛАГУР

БАЛАК

БАЛАЛА

БАЛАМУТ

БАЛАМУЧ

БАЛАНД

БАЛАХОН

БАЛБЕС

БАЛД

БАЛ К

БАЛМОШ

БАЛМОЧ

БАЛТ

БАЛЯС

г

ГРОБ

ГРОЖ

ГРОЗ

ГРОЗД

ГРОМ

ГРОМАД

ГРОМОЖД

ГРОМОЗД

ГРОХ

ГРОШ

Проведенные морфемы взяты из книги 2.

Для повышения быстродействия устройства использовано следующее обстоятельство.

В современных вычислительных устройствах для кодирования букв использует- ся стандартный 8-разрядный код (например, КОИ-8).

Младшие 5 разрядов этого кода определяют конкретные буквы некоторого алфавита, а три старших разряда определяют алфавит (латинский или русский) и характер буквы (строчная или прописная). Таким образом, буква в некотором алфавите однозначно определяется пятью разрядами. Поэтому на первом уровне код буквы явля- ется адресом ячейки, в которой хранится указатель на начальный адрес блока второго уровня. Код второй буквы последовательности рассматривается как приращение относительно начального адреса выделенного блока второго уровня, в которой хранится указатель на начало блока третьего уровня.

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

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

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

С внешнего устройства на шину ввода- вывода данных устройства в сопровождении сигнала Запись поступает код первой буквы опросной последовательности. Для более наглядного описания принципа действия устройства в качестве примера возьмем буквенную последовательность, составляющую корневую морфему БАЛАГУР. Код первой буквы б в КОИ-8 - 11000010.

Младшие пять разрядов этого кода используются в качестве адреса ячейки 4 блока первого уровня.

В устройстве управления ведется счет импульсам сигнала Запись и, если это число не больше трех, то младшие пять разрядов записываются в сумматор 8 по третьему входу и складываются с нулевым кодом по четвертому входу сумматора 8. Затем результат, сложения с выхода сумматора поступает на адресный вход блока 3, памяти.

Для этого на вход х7 подается управляющий сигнал записи по третьему информационному входу сумматора 8, затем на выход х9 подается инструкция сложения.

В этом случае мы получаем адрес третьей ячейки 4 блока первого уровня (код 00010), в полях указателей 6 и символа 5 которой хранится начальный адрес блока второго уровня, соотнесенного с первой буквой б искомой последовательности.

Содержимое полей указателя и символа данной ячейки 4 заносится в сумматор 8 по четвертому информационному входу, для чего на выход х8 подается сигнал выборки четвертого входа сумматора 8, а на выход х9 - инструкция записи. После этого содержимое поля признаков 7 через вход у2 проверяется на наличие признака конца последовательности.

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

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

Так как это будет второй сигнал Запись, то снова младшие 5 разрядов кода второй буквы (код 00001) заносятся по третьему входу сумматора 8, а затем складывается с содержимым по четвертому входу. При этом мы получаем адрес второй ячейки 4 блока второго уровня, выделенного в первом цикле работы устройства (Адрес Начальный адрес + код 00001). В соответствующих полях ячейки 4 по вычисленному адресу хранится начальный адрес некоторого блока третьего уровня. Далее вышеописанный процесс повторяется. В данном цикле при проверке поля признаков обнаруживается признак конца последовательности (для морфемы БА), однако с внешнего устройства выдается очередной сигнал Запись после чего начинается третий цикл работы устройства, который протекает аналогично второму циклу.

После выдачи четвертого сигнала Запись функционирование устройства совпадает с основным изобретением. При этом код буквы записывается во входной регистр 1. На адресном входе блока 3 памяти в этот момент установлен начальный адрес блока четвертого уровня в ячейках которого записаны коды 4-х букв, которые могут иметь для последовательности БАЛ.

Затем с блока 9 управления на управляющие входы блока 3 пяти и входного регистра 1 поступают сигналы чтения, а на управляющий вход компаратора 2 - сигнал сравнения. В результате в компараторе 2 производится сравнение содержимых поля 5 символов текущей ячейки 4 и входного регистра 1.

Если совпадения при этом не произошло, в сумматоре 8 складываются значения на выходе сумматора 8, поступающее на его третий вход и значение с выхода поля 6 указателей текущей ячейки 4, поступающее на первый вход сумматора 8.

Для этого с блока 9 управления на управляющие входы сумматора 8 подаются

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

содержимое поля 5 символом которой также сравнивается в компараторе 2 с содержимым входного регистра 1, и т.д. Описанная последовательность операций продолжается до тех пор, пока содержимое поля 5 сим0 волов некоторой ячейки 4 данного блока не совпадает с содержимым входного регистра 1.

Как только совпадение произошло (для нашего примера это происходит в первом

5 цикле сравнения), содержимое сумматора 8 получает единичное приращение. Для этого с блока 9 управления на выходы хб и х7 подаются сигналы выборки второго и третьего входов сумматора 8, а на выход х9 0 инструкция сложения. При этом в сумматоре 8 складываются текущее содержимое с выхода сумматора 8 и число 1, поступающее на второй вход сумматора 8.

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

0 производится аналогичная процедура поиска этого символа в данном блоке.

Процедура поиска адресной последовательности продолжается до тех пор, пока в блок 9 управления с поля признаков 7 соот5 ветствующей ячейки 4 блока 3 памяти и с внешнего устройства не поступят соответственно признак конца последовательности и сигнал конца опросной последовательности. В этой ситуации сумматор 8 указывает

0 на ячейку 4, в которой записан последний символ последовательности, хранимой в блоке 3 памяти и тождественной опросной последовательности. Этот адрес однозначно определяет данную последовательность

5 и служит ее кодом, Поэтому блок 9 управления выдачей сигнала Положительный результат поиска оповещает внешнее устройство о том, что на выходе устройства имеется результат поиска опросной по0 следовательности в виде кода-адреса. На этом ассоциативный поиск опросной последовательности завершается.

В ходе ассоциативного поиска возможна такая ситуация, когда при сравне5 нии очередного элемента опросной последовательности ни один элемент опрашиваемого блока не совпадает с данным входным элементом. Эта ситуация выявляется тогда, когда после очередного несовпадения в поле 7 признаков данной ячейки 4

обнаруживается признак конца блока. При этом блок 9 управления вырабатывает для внешнего устройства сигнал Ошибка и работа устройства на этом завершается.

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

0

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

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

:иг. i

-Э1 fc| I5

со

sT

со If)

СО

ГЭ|

f

§g§

о о о

О О О II

КШЕЦ

Фиг.З