Ассоциативное запоминающее устройство

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

< (51)5 G 11 С 15/00

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

llO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ. ол:",л

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4622825/24 (22) 22.12:88 (46) 23.09.91. Бюл, М 35 (72) Г.П.Токмаков (53) 681.327 (088.8) (56) Авторское свидетельство СССР

М 1174988, кл. G 11 С 15/00, 1983.

Авторское свидетельство СССР

М 1587586, кл. G 11 С 15/00, 1988. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и может быть использовано в ассоциативных процессорах, устройствах символьной обработки информации, например в устройствах морфологического анэлиИзобретение относится к вычислительной технике, а именно к ассоциативным запоминающим устройствам.

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

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

Основу устройства составляет регистр

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

„„S U; 1679554 А1 зэ словоформ. Цель изобретения — повышение быстродействия устройства. Устройство содержит регистр 1, компаратор 2, блок 3 памяти, содержащий ячейки 4 памяти, каждая из которых содержит поле 5 символов, поле 6 указателей и поле 7 признаков. Устройство также содержит сумматор 8 и блок

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

Блок 9 управления имеет входы "Запись", "Поиск", "Признак конца последовательности", "Наличие совпадения" и

"Признак поиска", причем сигналы, поступающие на указанные входы, обозначены

У -УБ(фиг.1). Блок 9 управления имеет выходы "Положительный результат поиска", "Ошибка" и "Запрос", являющиеся одно1679554 именными выходами устройства. Сигналы на этих и других выходах блока 9 обозначены Х1-Х11 (фиг.1).

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

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

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

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

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

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

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

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

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

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

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

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

Сначала рассмотрим процесс записи в память внешней 3ВМ (на фиг,1 не показана) первой последовательности первого класса, т.е. рассмотрим ситуацию, когда перед записью последовательности область памяти, отведенная для записи структуры поискового дерева, пуста.

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

10

35

45

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

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

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

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

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

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

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

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

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

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

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

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

10

25

35

45

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

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

Полученная структура переписывается к блок 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 блока первого уровня не совпадает с содержимым регистра 1.

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

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

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

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

1679554

"Ошибка" и работа устройства на этом завершается, Формула изобретения

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

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

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

1679554

Фиг Ф

Составитель В.Рудаков

Техред М. Моргентал Корректор Q.Êðàâöoâà

Редактор О.Стенина

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 3218 Тираж 320 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5