Сайт Информационных Технологий

ПРЕДСТАВЛЕНИЕ СТРУКТУР ДАННЫХ В АССОЦИАТИВНОЙ НЕЙРОННОЙ СРЕДЕ

В. В. Борисов

Военный университет войсковой ПВО ВС РФ

Научно-исследовательский центр

Abstract — The Associative Neuron Medium are considered. The analysis of structures of data in Associative Neuron Medium is realized. The efficiency of using of Associative Neuron Medium in solution of tasks of data presentation and processing is shown.

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

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

В работах [3, 4] предложена концепция ассоциативной нейронной среды (АНС) для хранения и обработки информации, в основе которой лежат следующие основные принципы:

Эти принципы определяют перечисленные ниже АНС, позволяющие эффективно реализовать процедуры представления и преобразования структур данных.

Представление списковых структур данных в ассоциативной нейронной среде

Линейные списковые структуры отличаются порядком включения, исключения, замены или доступом к элементам данных. Обобщением линейных списков являются массивы. В p-мерном массиве каждый элемент принадлежит p линейным спискам. Эти структуры являются естественно описываемыми в АНС объектами, не требующими дополнительных приемов для их представления на основе определенных в АНС геометрических форматов [4].

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

Многие важные случаи работы с линейными списками требуют адекватности их представления в АНС. Типом решетки, отвечающим основным требованиям адекватности представления списковых структур данных является кубические решетки Zp. Вопрос адекватности представления треугольных матриц общего вида произвольной размерности (так называемых тетраэдральных массивов) в АНС решается выбором треугольной системы заполнения АНЯ пространства АНС соответствующей размерности с направлениями доступа к ячейкам, совпадающими с осями трансляции при организации этой решетки. Другое представление тетраэдральных массивов может быть осуществлено на решетках Zp АНС с диагональными направлениями доступа к АНЯ.

Из всех типов структур данных именно для линейных списков и, прежде всего, для многомерных массивов наиболее актуален вопрос их представления на решетках АНС 3-й и меньших размерностей, которые являются физически реализуемыми и визуально представимыми. Например, 4-мерный массив данных, в котором каждый элемент данных принадлежит 4-м линейным спискам, может быть представлен совокупностью 3-мерных геометрических форматов в 3-мерной кубической решетке Z3 с эмуляцией ассоциативных взаимосвязей между АНЯ, обеспечивающих связность, упорядоченность и принадлежность каждого элемента данных 4-м линейным спискам.

Представление деревьев в ассоциативной нейронной среде

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

Для древовидных структур данных существенным является обеспечение различных видов параллельного доступа к элементам данных: к 2t-1 элементам данных поддерева глубиной t; к различным совокупностям вершин дерева одного уровня; к вершинам дерева, определяемым порядком его прохождения.

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

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

В ряде случаев целесообразно использовать решетки АНС больших, чем 2D, размерностей. Использование для представления деревьев решеток АНС 3-й и больших размерностей позволяет:

Использование иерархических взаимосвязей между решетками АНС различных размерностей при представлении дерева является основой естественности такого представления.

В иерархически взаимосвязанных решетках АНС могут быть размещены r-арные деревья общего вида и снимаются ограничения накладываемые фиксированным числом ветвей дерева.

Для представления и эффективной реализации в АНС различных типов параллельного доступа в древовидных структурах данных предложен новый тип геометрических форматов - иерархических геометрических форматов [4]. Кроме того, в АНС могут быть одновременно размещены несколько деревьев. Причем вершины соответствующих уровней деревьев размещаются в одних и тех же решетках АНС соответствующих размерностей. Это обеспечивает эффективную реализацию быстрых алгоритмов поиска и сортировки для древовидных структур данных в АНС.

Представление многосвязных структур данных в ассоциативной нейронной среде

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

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

Заключение

Проведенный анализ основных структур данных позволяет выделить основные процедуры их представления и преобразования: 1) доступ к k-му элементу данных; 2) осуществление различных видов параллельного доступа к элементам данных структуры; 3) включение элементов данных в структуру; 4) исключение из структуры элементов данных; 5) замена элементов данных в структуре; 6) разбиение структуры данных на несколько структур; 7) объединение нескольких структур данных в одну; 8) изменение структурных отношений между элементами данных структуры; 9) копирование структуры данных или ее фрагментов; 10) поиск элементов данных в структуре в соответствии с заданным критерием; 11) сортировка элементов данных по заданному критерию; 12) поиск структур данных в соответствии с заданным критерием; 13) сортировка структур данных по заданному критерию.

Эти процедуры эффективно реализуются в АНС на основе следующих ее свойств: 1) обеспечение соответствия структур данных структурам их представления в АНС; 2) многокоординатность и параллелизм доступа к АНЯ по всем реализованным в решетках АНС направлениям; 3) многомерность пространства АНС; 4) многоформатность доступа к структурам данных в АНС; 5) многопортовость доступа к элементам структуры данных, предполагающая одновременность, коллективность и бесконфликтность обращения к соответствующим АНЯ; 6) реализация ассоциативных взаимодействий между АНЯ внутри и между решетками; 7) выполнение параллельного ассоциативного сравнения по заданным критериям; 8) маскирование АНЯ для выполнения различных операций над структурами данных; 9) реконфигурация решеток АНС при выполнения различных операций над структурами данных; 10) настройка и обучение как отдельных АНЯ, 11) так и АНС в целом на выполнение различных процедур представления и преобразования данных.

В табл. 1 показано соответствие основных процедур представления и преобразования данных и свойств АНС, необходимых для их реализации.

Соответствие процедур представления и преобразования данных и свойств АНС

Таблица 1.

 

Свойства АНС

   

1

2

3

4

5

6

7

8

9

10

11

 

1

+

+

+

+

+

           
 

2

+

+

+

+

+

+

 

+

+

 

+

 

3

+

+

+

+

+

+

+

 

+

+

+

 

4

+

+

+

+

+

+

+

+

+

+

+

 

5

+

+

+

+

+

+

+

+

+

+

+

 

6

+

+

+

+

+

+

+

+

+

+

+

 

7

+

+

+

+

+

+

+

+

+

+

+

 

8

+

+

+

+

+

+

+

+

+

+

+

 

9

+

+

+

+

+

   

+

   

+

 

10

+

+

+

+

+

+

+

       
 

11

+

+

+

+

+

+

+

+

 

+

+

 

12

+

+

+

+

+

+

+

+

 

+

+

13

+

+

+

+

+

+

+

+

+

+

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

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

Литература

  1. Метлицкий В.А., Каверзнев В.В. Системы параллельной памяти: Теория, проектирование, применение / Под ред. В.И.Тимохина.- Л., Изд-во Ленинградск. ун-та, 1989.
  2. Lawrie D.H, Voga C.R. The Prime Memory System for Array Access // IEEE Trans. on Computers, N5, vol. 31, 1985.
  3. Борисов В.В. Ассоциативная нейронная фрактальная среда для прикладных интеллектуальных систем. – Нейрокомпьютер, 1998, № 1-2. - С. 5-11.
  4. Борисов В.В. Исследование и разработка многокоординатных ассоциативных запоминающих устройств и среды хранения и обработки информации. – М.: МЭИ, 1997.

Site of Information Technologies
Designed by  inftech@webservis.ru.