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

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

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

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

Основу устройства составляет регистр 1, вход которого является информационным входом устройства, а выход подключен к первому информационному входу компаратора 2, блок 3 памяти, каждая ячейка 4 памяти которого содержит поле 5 символов, поле 6 указателей и поле 7 признаков, причем выход поля 5 символов подключен к

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

Блок 9 управления имеет входы Запись, Поиск, Признак конца последовательности, Наличие совпадения и Признак поиска, причем сигналы, поступающие на указанные входы, обозначены Yi-Ys (фиг. 1). Блок 9 управления имеет выходы Положительный результат поиска, Ошибка и Запрос, являющиеся одноО

1 о ел ел

-N

именными выходами устройства. Сигналы на этих и других выходах блока 9 обозначены Х-|-Хц (фиг.1).

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

Для формирования этой структуры рассматриваемое множество символьных последовательностейподвергаетсяпредварительной сортировке в установленном порядке. Например, приведенные слова отсортированы в алфавитном порядке:

абажур

аббат

абрикос

актер

армия

асфальт

база

базальт

базар

берег

бугор

бык

вольер

вольт

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

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

Аналогичное разбиение проводят для второго и третьего классов первого уровня.

Затем описанным образом производят разбиение на классы третьего уровня последовательности классов второго уровня и т.д.

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

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

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

5 каждый блок второго уровня относится к какому-либо узлу первого уровня.

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

0 следующим образом, Каждый блок (п+1)-го уровня относится к некоторому узлу (элементу) блока п-го уровня.

Описанная структура формируется в процессе записи отсортированного множе5 ства последовательностей по алгоритму, схема которого изображена на фиг.2. Этот алгоритм может быть реализован на внешней ЭВМ в виде программы, а структура, сформированная в некоторой области ее па0 мяти, затем может 5ь;ть перезаписана в блок 3 памяти устройства с помощью программатора.

Сначала рассмотрим процесс записи в память внешней ЭВМ (на фиг,1 не показана)

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

0

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

После этого счетчик адрес внешней

5 ЭВМ увеличивается на единицу.

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

и остальных символов первой последовательности приводятся аналогично.

После записи последнего элемента последовательности вводится символ признака конца последовательности. При этом проверка введенного символа на равенство коду признака конца последовательности дает положительный результат. Это приводит к уменьшению содержимого счетчика адрес на единицу (при зтом он будет указывать на ячейку, в поле символов которой записан последний символ последовательности), и в поле признаков соответствующей ячейки в дополнение к признаку конца блока запишется признак конца последовательности.

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

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

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

Затем вводится второй символ второй последовательности, и описанный процесс полностью повторяется, так как вторые символы первой и второй последовательности также совпадают. Далее вводится третий

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

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

После этого в поле указателей ячейки, с содержимым поля символов которой сравнивался код третьего символа, записывзет0 ся содержимое счетчика приращения. Таким образом, устанавливается связь между двумя соседними элементами блока, после чего адрес следующего элемента блока определяется сложением значений счетчи5 ка адресов и поля указателей данной ячейки памяти. Затем счетчик лрираа ния обнуляется. Увеличением счетчика адреса программа подготавливается к приему очередного символа последовательности.

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

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

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

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

Итак, мы рассмотрели все возможные ситуации, которые могут иметь место при формировании структуры поискового дерева. На фиг.З описана структура поискового дерева для множества слов, приведенного в нашем примере, сформированного по описанному алгоритму.

Полученная структура переписывается к блок 3 памяти. Ассоциативное запоминающее устройство готово к работе.

Устройство работает следующим образом.

С внешнего устройства на информационный вход устройства поступает первый элемент опросной последовательности и записывается в регистр 1. Сумматор 8 установлен при этом в исходное состояние. Затем с блока 9 управления на входы блока

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

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

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

Как только совпадение произошло, содержимое сумматора 8 получает единичное приращение. Для этого с блока 9 управления подаются сигналы X Vi Ха приема ин5 формации, а затем Xs - код операции сложения, При этом в сумматоре 8 складываются текущее содержимое с выхода сумматора 8, поступающее на/ третий вход и значение 1, поступающее на второй вход

0 сумматора 8.

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

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

0 Затем производится поиск третьего и последующих элементов опросной последовательности до тех пор, пока в блок 9 с поля признаков 7 соответствующей ячейки 4 блока 3 и с внешнего устройства не поступят

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

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

Ошибка и работа устройства на этом завершается.

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

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

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

Запись

JL

ойН

оиск

Признан каниа ггаслеЛайатем. -

поста.

ill/1

Яоши/пельнш

результат

поиска 4Ои/иЈка4Janpoc r

слеЛайатем. -

5 5 7

9

J

-Ч

И

8

гт

4L

У5 5

V

Х7 S Ь

Хю

7/

Фие.1

Фаг 2

Уст. см

СцмВ -. Рв

Сравнение

и+ д CM

Указ Адр - 38хСгг

Нет

нет

Да

/ Ошибка

/Конец jj ФиеМ

1

Ј

1

п . лп

+/ см

Нет

Нет