Название: Инвариантно-параметрическое представление и обобщенная ассоциативная обработка символьной и смысловой информации(Токмаков Г. П)

Жанр: Информационные системы и технологии

Просмотров: 3093


1.1. ассоциативный принцип обработкиинформации и варианты его реализации

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

№ п/п Имя Адрес в памятиЧу — Элемент данных

Isabel 226 D(l)

Sophie 482 D(2)

Howard 196 D(3)

15. Harlow 182 D(15)

16. Hans 182 D(16)

Ь5С ж:

Рис.1.   Таблица соответствия имен и их физических адресовВ простейшем случае для преобразования имен в адрес можно отыскать входное имя в данной таблице путем последовательного просмотра. Но обращение к этой таблице происходит часто, поэтому были предложены более эффективные методы поиска. Эти методы, предложенные уже для первых достаточно развитых ЭВМ, базируются на размещении данных по адресу, значение которого вычисляется как функция соответствующего символьного имени или некоторой его части. При этом для поиска входного имени достаточно было бы одного обращения к памяти.Однако данному методу поиска присуща проблема "неуправляемости" ключа. Например, если в качестве имен используются русские слова длиною в 10 знаков, то адресное пространство, охватываемое этими словами, составит 3010 ключевых значений (где 30 - количество букв алфавита). На практике доступное адресное пространство всегда уже того диапазона чисел, получаемого из допустимых имен. Поэтому для формирования адресов используются не все знаки имен, а только их часть. В таблице из рис. 1 использованы два первых символа имени. Вычисление адресов, размещенных в колонке "Адрес в памяти", производится следующим образом. Пусть каждому символу соответствует код,равный его порядковому номеру. Тогда адрес имени, например, Isabel вычисляется какIs = 8*26J + 18*26° = 208 + 18 = 226.Этот метод частично решает проблему неуправляемости ключа, но привносит другую проблему, связанную с конфликтом адресов. Например, элементы таблицы с номерами 15 и 16 начинаются с одних и тех же букв и по ним вычисляются одинаковые адреса.В общем случае для поиска записи, удовлетворяющей некоторым условиям, могут быть использованы следующие три основных метода:Ассоциативный поиск - предполагает использование ассоциативной памяти. При этом затраты времени на поиск обычно постоянны и не зависят от количества записей.Последовательный поиск - наиболее простой метод, согласно которому п записей последовательно сравниваются с ключом поиска. Но при поиске в массивах большого размера требуются очень большие затраты времени на поиск требуемых данных.Поиск по дереву - для реализации этого метода строится древовидная структура, узлы которой связаны указателями.1.1.1. Принципы организации и технической реализации классических АЗУПервые работы в области ассоциативной памяти появились еще в 60-х годах в связи со стремлением смоделировать известное свойство человеческой памяти устанавливать взаимосвязи между различными информационными объектами. В ВТ под термином ассоциативная память подразумевается память с параллельным доступом ко всем ячейкам с использованием содержания данных, а не их адресов [34].Формально логику работы ассоциативной памяти, организация которой показана на рис. 2, можно описать следующим образом. Ассоциативная память состоит из двух частей: словаря (матрица X) и массива данных (матрица Y). Классический вариант ассоциативной памяти управляется с помощью слова-маски m1,m2,...,mi, которое задает подмножество разрядов, используемых для поиска, в ключевом слове wj,W2,...,wi. При этом считается, что значение разряда

w, nkj. xx: xxr; хк :хк

маски rrij, равное 1, означает разрешение операции сравнения по разряду аргумента Wj. Если содержимое wj, по которому производится сравнение, совпадает со значением xj, то в данном элементе матрицы X вырабатывается сигнал совпадения uj, равный 1. В случае запрещения сравнения в данном разряде фиксируется совпадение. Из описанного следует, что сигнал совпадения, вырабатываемый в каждом элементе матрицы X, представляет собой логическое произведение маски и сложения по модулю 2 аргумента и содержимого элементасловаря: u'j = mj,л (Vj © x'j). Значение сигнала совпадения для всей строки матрицы X представляет собой логическое произведение всех сигналов совпа-гдения элементов данной строки: и, = л и'-. Вектор U фиксирует совпадение внекоторой строке матрицы X и выделяет соответствующую строку в матрице Y как результата поиска.На примере ассоциативной памяти, структурная схема которой представлена на рис. 3, рассмотрим техническую реализацию описанных принципов. Данная ассоциативная память содержит запоминающий массив ЗМ, состоящий из N (п+1)-разрядных слов. Входная информация через входную шину ВхШ поступает в регистр ассоциативных признаков РгАП («-разрядный ассоциативный запрос) и в регистр маски РгМск. Ассоциативный поиск по запросу РгАП производится только для тех его разрядов, для которых в соответствующих разрядах РгМск установлено значение 1. Для тех слов ЗМ, разряды которых совпали с незамаскированными разрядами РгАП, комбинационная схема КС устанавливает в 1 соответствующие разряды регистра совпадения РгСвп и в О - остальные разряды. Значение /-го разряда РгСвп определяется согласно выражениюPzCen{j) = ' л ргАП[1] 0 ЗМ[у, i] v РгМск[г]},для всех 0 <j <N-1.Схема формирования совпадения СхФС по информации из РгСвп формирует сигналы а0, аь а2, которые используются при формировании результата ассоциативного поиска. При формировании сигналов а0, аь а2 СхФС реализует следующие булевы функции:(Xq = л РгСвп[Дах = РгСвп[ЩРгСвп[\]РгСвп[2..РгСвп[Л..РгСвп[Ы -1] vv РгСвп[0]РгСвп[\]РгСвп[2]...РгСвпУ]...РгСвп[М - 1] vv РгСвпЩРгСвп[\]РгСвп[2..РгСвп[]..РгСвп[К -1];ВхШРг АПМаскаРг МскКС

змРис. 3.   Структура ассоциативной памятиСчитывание результата производится под управлением значений, выработанных на выходе СхФС. При а0 = 1 считывание не производится, так как при этом в ЗМ не находится искомое слово. При а} = 1 в РгВых считывается содержимое слова ЗМ, разряды которого совпали с соответствующими разрядами РгАП. В случае, когда а2 = 1, в РгВых считывается слово из ЗМ с наименьшим адресом.1.1.2.   АЗУ для обработки символьных последовательностейАЗУ, рассмотренное выше, обеспечивает ассоциативный поиск отдельных слов. Однако во многих задачах, таких как распознавание и синтез речи, понимание и генерирование текста на ЕЯ, перевод с одного языка на другой и т.д., требуется ассоциативный поиск кодовых последовательностей произвольной длины. В работах [26,27,28,29,30,31,32,33] был разработан ряд устройств, решающих данную задачу. Сложность решения поставленной задачи заключается в том, что при этом емкость АЗУ должна быть достаточно большой, а искомые кодовые последовательности могут иметь произвольную длину. Для ознакомления с принципами, использованными в разработанных устройствах, рассмотрим одно из них, структура которого представлена на рис. 4.Устройство содержит регистровый блок РгБлк для хранения ключевой последовательности, адресное ЗУ АдрЗУ для хранения массива последовательностей, компаратор Кмп, в котором сравниваются соответствующие элементы ключевой последовательности из РгБлк и опросной последовательности из АдрЗУ. В АдрЗУ записаны последовательности, состоящие из двух подпоследовательностей А{ и В[,AjBj = {В1'1А1+1а,а.1,...,а1ьЬ11,Ъ12,...,Ъ1р}, где В1'1 - ссылка на подпоследовательность Ви1, А1+1 - ссылка на подпоследовательность Ai+1, i — 0,...,N, q,p - var. В РгБлк в зависимости от режима хранится либо подпоследовательность Af, либо подпоследовательность Bt Структуры данных РгБлк и АдрЗУ рассматриваемого устройства приведены на рис. 5. Каждый элемент в АдрЗУ снабжен признаком, идентифицирующим следующие типы элементов: а{ - А, вг - В, А, - С, В{ -D.Устройство работает в двух режимах:прямом, в котором происходит поиск подпоследовательности At и считывание подпоследовательности В, как результата поиска;обратном, в котором производится поиск подпоследовательности Bj и считывание подпоследовательности А, как результата поиска.В обоих режимах перед процедурой поиска, по алгоритму, приведенному на рис. 6, производится запись ключевой последовательности в РгБлк.Алгоритм работы устройства в режиме поиска последовательности А, приведен на рис. 7 и описывается следующим образом. В данном режиме в РгБлк записана последовательность At = {ai,a2,...,aq}. Исходное значение счетчика Сч1, отслеживающего текущую позицию в РгБлк, равно q-1 (устанавливается в процессе записи ключевой последовательности), а счетчик Сч2, являющийся счетчиком адреса АдрЗУ, сбрасывается в нулевое состояние. Перед началом поиска значение Сч1 запоминается в Рг1 и используется перед началом каждого цикла поиска как исходное значение Сч1. Сч2 при этом указывает наxl х2 хЗ х4

РгБлк yiу2

Кчп -А Рг1Рг2 -Л Сч1Сч2 <3 х5узу4У5 убУ7у8у9хбу10yllубу!2у!3у14х5х5у15 у1бу!7 х10 ж адI IО«5у 18

-ЬтАдресное ЗУРис. 4.   Структура АЗУ для поиска произвольных последовательностей

ЫЪ2ЪЗЪр_Содержимое РгБлк в режиме обратного поиска

Рис. 5.   Структуры данных РгБлк и АдрЗУ АЗУ последовательностейНачало

Подпись:  Сброс Сч 1, Сч 2

Сч2 = Сч1 + 1 Запись в Рг Блк

ЗаписьСравнениеРис. 6.   Блок-схема алгоритма записи в РгБлк

ячейку АдрЗУ, в которой хранится указатель на начало следующей последовательности. Этот адрес запоминается в Рг2 с тем, чтобы по первому же несовпадению при сравнении текущей последовательности перейти к началу следующей путем записи этого значения в Сч2.После проведения установочных операций начинается синхронный отсчет счетчика Сч2, и как только БУ обнаружит признак "А" начинается сравнение последовательностей в Кмп. При этом Сч2 ведет прямой отсчет, а Сч1 -обратный. В процессе сравнения последовательностей возможны следующие ситуации:В процессе сравнения происходит не совпадение сравниваемых последовательностей.При полном совпадении элементов сравниваемых последовательностей ключевая последовательность из РгБлк "короче" текущей последовательности из АдрЗУ. Данная ситуация возникает, когда Сч1 показывает на нуль, а признак следующего элемента последовательности из АдрЗУ не равен "В".

При полном совпадении элементов сравниваемых последовательностей ключевая последовательность из РгБлк "длиннее" текущей последовательности из АдрЗУ. Данная ситуация возникает когда значение признака очередного элемента АдрЗУ равно "В", значение Сч1 не равно нулю.Полное совпадение элементов сравниваемых последовательностей, Сч1 = О, а значение признака следующего элемента последовательности из АдрЗУ равно "В".

Подпись:

Рг2 =

 

 

Сч2 =

Сч2- 1

            £>

 

Вывод

 

 

Сч2 =

Сч2- 1

VПервые три ситуации соответствуют несовпадению сравниваемых последовательностей и приводят к записи значений Рг1 в Сч1, а Рг2 в Сч2. При этом Сч1 будет указывать на q-й элемент ключевой последовательности, а Сч2 - на q-й элемент следующей последовательности из АдрЗУ, после чего начинается новый цикл сравнения.Четвертая ситуация возникает в том случае, когда искомая последовательность находится в АдрЗУ, и как результат поиска требуется выдать последовательность Bi. Процесс считывания осуществляется одновременно с контролем признаковой части слова АдрЗУ, и как только будет обнаружен признак D, процесс считывания результирующей последовательности завершается.

Процедура поиска в обратном режиме, алгоритм которого приведен на рис. 8, описывается аналогично и отличается лишь тем, что в РгБлк при этом записывается ключевая последовательность В{ = {ehe2,-..,ep}, которая сравнивается с последовательностями {в,в'2,...,e'pj (i = 1,...,N) из АдрЗУ. В целом алгоритм работы устройства приведен на рис. 9.1.1.3.   АЗУ с древовидным представлением информацииАЗУ с древовидным представлением информации, блок-схема которого представлена на рис. 10, описано в [32] и предназначено для ассоциативного поиска информации. В отличие от предыдущего устройства, информация, хранящаяся в его памяти, имеет древовидную структуру. Древовидные структуры имеют важное значение для наших дальнейших построений. Поэтому здесь приведем основные положения и терминологию из теории древовидных структур, которой будем придерживаться в дальнейших изложениях. Дерево представляет собой иерархию элементов, называемых узлами. На самом верхнем уровне иерархии имеется только один узел - корневой. Каждый узел, кроме корневого, связан с одним узлом на более высоком уровне, называемым родительским или исходным узлом для данного узла. Каждый узел может быть связан с одним или несколькими узлами на более низком уровне. Они называются либо порожденными, либо потомками. Узлы, порожденные одним родительским узлом, называются подобными либо узлами-братьями. Узлы, расположенные в конце ветви, т.е. не имеющие порожденных узлов, называются листовыми или терминальными узлами. Иерархические отношения между узлами задаются с помощью дуг и в памяти компьютера моделируются с помощью указателей. Поиск начинается с верхних узлов и продолжается от узла к
узлу, пока не будет достигнута искомая запись. По пути в каждом узле осуществляется сравнение с ключом поиска, и дальнейший маршрут поиска определяется в зависимости от результатов сравнения. Таким образом, кроме указателей в каждом узле, должна быть помещена информация о значении ключа. Затраты времени на поиск зависят от высоты дерева и числа сравнений. Последовательность кодов символов, определяющая некоторый идентификатор или слово ЕЯ, определяется последовательностью дуг, называемой путем или маршрутом некоторой длины. Любой маршрут на дереве можно однозначно задать индексом концевого узла, и этот факт можно использовать для кодирования символьных последовательностей. В этом случае поиск некоторой символьной последовательности заключается в "прохождении" некоторого маршрута в древовидной структуре вплоть до достижения терминального узла и определении индекса этого маршрута. Следует отметить, что имеется целый ряд приложений, когда наряду с вышеописанным применением древовидных структур требуется обратная процедура, т.е. когда по индексу требуется восстановление исходной символьной последовательности. Для этого в древовидные структуры добавляют "обратные" дуги, которые выходят из порожденного узла и входят в родительский узел. Описанная разновидность древовидной структуры будет широко использоваться в наших дальнейших построениях.В ходе поиска устанавливается соответствие Wj={d j,d 2,...,dVQ}—>Aj, гдеj = 1,...,Р, аР - количество последовательностей в массиве;Щ       последовательность из массива последовательностей;Aj- элементы последовательности (буквы некоторого алфавита);v(j) - переменная величина, равная количеству элементов j-ik последовательности;Aj - адрес-код j-й последовательности.Устройство позволяет устанавливать и обратное соответствие Aj —^Wj-{d i,d 2,---,dv(j)}.Описываемое устройство содержит адресное ЗУ АдрЗУ, входной регистр ВхРг, компаратор Кмп, счетчик Сч и блок управления БУ. Содержимое АдрЗУ организовано в форме древовидной структуры, которая имеет вид, приведенный на рис. 11. Каждый узел древовидной структуры содержит признаковую, символьную и адресную части, причем символьная часть слова соединена с одним из входов Кмп, адресная - с входом АдрРг, а признаковая - с одним из входов БУ.В описываемой древовидной структуре записаны символьные последовательности, которые перед преобразованием в древовидную форму подвергаются предварительной сортировке. После этого последовательности, первые элементы которых одинаковы, объединяются в подмножества с общим первым элементом, для хранения которой выделяется одна ячейка АдрЗУ. В полученных подмножествах таким же образом формируются подмножества по общим вторым элементам, и т.д. пока не будут исчерпаны все уровни, количество которых зависит от количества символов в самой длинной последовательности массива. Ячейки узлов памяти, в адресной части которых содержится адрес перехода на последующий уровень иерархии, в признаковой части содержат признак 'А"; ячейки, в адресных частях которых содержится адрес перехода на предыдущий уровень иерархии, в признаковой части содержат признак "В".Устройство работает в двух режимах:в режиме поиска по последовательности Wj соответствующего ей адреса-кода Af,в режиме вывода последовательности Wj по адресу-коду Aj.

СмвА Смв Адр А   Смв АдрСмвАдрАдр

А

Смв

Абр

АU            1

Смвс            1

^            АдрU           

^            .j-           

           

ri           

А

Смв

Л            Адр

В

 

Адр

 

А

Смв

Адр

 

. . .

 

А

Смв

Адр

В

 

Адр

С Адр

А

Смв

Адр

А

Смв

Адр

А

Смв

Адр

 

. . .

 

А

Смв

Адр

В

 

Адр

 

А

Смв

Адр

А

Смв

Адр

А

Смв

Адр

 

. . .

 

А

Смв

Адр

В

 

Адр

 

А

Смв

Адр

 

. . .

 

А

Смв

Адр

В

 

Адр

 

А

Смв

Адр

 

. . .

 

А

Смв

Адр

В

 

Адр

 

А

Смв

Адр

 

. . .

 

А

Смв

Адр

В

 

Адр

Рис. 11. Структура информации АдрЗУФункционирование устройства в режиме поиска последовательности описывается с помощью алгоритма, блок-схема которого приведена на рис. 12. Сущность этого алгоритма заключается в том, что элементы ключевой последовательности поочередно заносятся в ВхРг выходами подключенного к одному из входов Кмп, где происходит их сравнение с текущими элементами некоторого выбранного блока узлов. Как только после очередного цикла сравнения происходит совпадение, в АдрРг заносится значение адресной части данного узла, которое затем переносится в Сч.После этого устройство готово к следующему циклу сравнения, который повторяется до тех пор, пока в ВхРг не появится код конца последовательности. Если же в ходе очередного цикла сравнения в процессе поиска входного символа в одном из блоков узлов АдрЗУ будет обнаружен признак "В", то это будет означать, искомый символ в данном блоке не обнаружен и что данная входная последовательность не содержится в массиве последовательностей, хранящихся в АдрЗУ.Работа устройства в режиме вывода последовательности по ее адресу-коду описывается с помощью алгоритма, блок-схема которой представлена на рис. 13. Процесс вывода последовательности начинается с установки Сч, на

Сч = Сч + 1

КонецРис. 13. Блок-схема алгоритма работы АЗУ в режиме вывода последовательностивход которого подается адрес-код данной последовательности, указывающий на последний ее элемент, и на шине ВыхСмвПсл появляется последний символ запрашиваемой последовательности. Затем начинается приращение Сч до появления признака "В", после чего адресная часть текущего узла через РгАдр заносится в Сч,и таким образом происходит переход на предыдущий уровень иерархии, причем именно в ту ячейку памяти, где хранится предпоследний символ последовательности. Далее процесс продолжается аналогично и завершается по обнаружении признака С, который содержится в признаковой части последней ячейки корневого блока.1.1.4.   АЗУ как средство моделирования интеллектуальных задачВ работах [35,36,37] на базе АЗУ был разработан ряд устройств, обеспечивающих распознавание и синтез речи. Все эти устройства реализованы по единой идеологии, поэтому чтобы получить представление о принципах, заложенных в их основу, ознакомимся с одним из них. Блок-схема устройства, описанного в [37] и обеспечивающего распознавание и синтез речи, приведена на рис. 14.Функционирование устройства осуществляется в двух режимах: распознавания и синтеза. Основу устройства, реализованного на трех уровнях, составляет A3 У, содержащее ассоциативные накопители АН1 и АН2, компараторы 3 и 4. Описанное АЗУ содержится на всех трех уровнях: фонем, морфем и лексем. Взаимодействие между уровнями осуществляется посредством регистров.В режиме распознавания регистр 5 является входным для уровня фонем и для всего устройства, регистр 6 - выходным для уровня фонем и входным для уровня морфем, регистр 7 - выходным для уровня морфем и входным для уровня лексем, регистр 8 - выходным для уровня лексем и для всего устройства. В режиме синтеза регистр 9 является входным для уровня лексем и для всего устройства, регистр 10 - выходным для уровня лексем и входным для уровня морфем, регистр 11 - выходным для уровня морфем и входным для уровня фонем, регистр 12 - выходным для уровня фонем и для всего устройства. К входу устройства в режиме распознавания подключен анализатор речевого сигнала 13, а к выходу устройства в режиме синтеза речи - синтезатор речевого сигнала 14.Функционирование устройства в режиме распознавания осуществляется следующим образом. Параметры речевого сигнала с выхода анализатора речи заносятся на вход регистра 5, после чего осуществляется ассоциативный поиск записанной информации в АН2, где содержатся эталонные параметры речевого сигнала. В ходе ассоциативного поиска информация с соответствующих ячеек регистра 5 и ячеек АН2 сравнивается в компараторах 4. При этом на выходе одного из компараторов 4, связанного с соответствующей ячейкой АН1, появляется сигнал совпадения, который и производит выборку ячейки в АН1. Содержимое выбранной ячейки АН1 заносится в одну из ячеек регистра 6.Таким образом, производится распознавание сегмента речи, соответствующего фонеме, и в ячейку регистра 6 заносится код фонемы. После каждого

2

 

2

2

 

2

2

 

2

 

 

4

i

 

 

 

 

3

 

 

4

i

 

 

 

 

h

 

 

3

N

 

4

 

i

* ... I i

 

 

 

3

—ч——

 

 

4

 

i

 

i

 

 

3

           ^