Структуры данных

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

Самый простой способ. Когда в структуре кроме собственных данных хранится уникальный идентификатор (имя, номер, что угодно) другой структуры - это список.

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

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

Чтобы получить способ быстро обращаться к элементам списка, мы можем создать нумерованный массив со ссылками на объекты. Это индекс. Мы также можем создать несколько индексов, которые будут ссылаться на одни и те же элементы списка. Например, список слов может быть проиндексирован трижды - в прямом алфавитном порядке, в обратном и, например, по времени добавления элементов.

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

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

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

Стек это «очередь наоборот», в нем реализован принцип «первый зашел - последним вышел». Наиболее наглядный пример - автомат Калашникова. Первый патрон окажется в самом низу магазина, а выстрелит последним. Для этого новый элемент надо добавлять в конец списка и забирать его оттуда же.

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

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

Граф более универсальная структура и с его помощью можно организовать и список, и дерево. А если хранить не пару «элемент → элемент», а тройку «элемент → элемент : связь», то и несколько списков и деревьев одновременно. Даже из одних и тех же элементов.

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

Поэтому в названии этой структуры и присутствует слово «семантическая». Семантические сети используются для создания баз знаний.