Орынтаева Г.А., Бренер А.М.

ЮКГУ имени М.О. Ауезова, г. Шымкент

Электронные хранилища информации

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

- первоначальный сбор литературы в электронном виде, или сканирование литературных источников;

- разработка систематического каталога, сортировка электронных источников по разделам систематического каталога;

- создание динамического иерархического дерева каталога;

- добавление новых данных в каталог посредством операций поиска и вставки в нужный раздел систематического каталога;

- удаление некоторых данных из каталога по каким-либо причинам;

- разработка операций навигации по систематическому каталогу;

- поиск информации в каталоге по фамилии автора, по названию источника, по ключевым словам.

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

генеалогическое дерево, организацию спортивных состязаний среди футбольных команд, организационную структуру государственных органов и учреждений, в области компьютерной техники примером является файловая система хранения информации на жестком диске. Все многообразие различных типов деревьев можно сгруппировать в следующие понятия: а) деревья без выделенного корня; б) деревья с выделенным корнем; в) упорядоченные деревья; г) бинарные деревья; д) m – арные деревья. С математической точки зрения дерево без выделенного корня представляет собой связный ациклический неориентированный граф. Дерево с выделенным корнем получается, если в дереве без выделенного корня (связном ациклическом неориентированном графе) выделить одну какую-либо вершину. Эту вершину называют корнем дерева, остальные вершины, в зависимости от расположения могут быть предками или потомками других вершин. Вершины, которые не имеют потомков, называются листьями дерева. Упорядоченное дерево имеет дополнительный порядок среди потомства: точно известно для каждого узла дерева порядок следования его потомков. Следующим этапом уточнения понятия дерева являются бинарные деревья. Бинарное дерево – это упорядоченное дерево, которое имеет два типа узлов: внешние и внутренние. У внешних узлов нет потомков. У внутренних узлов имеется ровно два потомка: левый и правый. Дальнейшим обобщением бинарных деревьев являются m – арные деревья, у которых внутренние узлы имеют ровно m упорядоченных потомков.

Одной из наиболее общей функцией обработки деревьев является обход дерева. Для бинарных деревьев существуют три способа их обхода:

- прямой обход, когда сначала заходят в узел, затем в левое, а потом в правое поддерево;

- поперечный обход, при котором посещения происходят в порядке левое поддерево – узел - правое поддерево;

- обратный обход, здесь порядок посещений следующий: левое поддерево - правое поддерево - узел.

Программная реализация этих обходов в рекурсивной форме достаточна проста:

void obhod(link x, void kiru(link))

{if (x==0) return; kiru(x); obhod(x->solga, kiru); obhod(x->solga, kiru);}

Здесь для каждого узла вызывается функция kiru. В данном виде функция

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

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

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

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

- на каждом шаге сканирования текущий обозреваемый файл должен быть отсортирован по ключевым словам в нужный раздел систематического каталога;

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

- поиск и навигация по виртуальному систематическому каталогу.

Таким образом, рассмотрены основные принципы и алгоритмы построения электронных хранилищ информаций.

Литература

1. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. 2-е издание. : Пер. с англ. — М.: Издательский дом "Вильяме", 2005. — 1296 с.

2. Р. Седжвик. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - К.: Издательство «ДиаСофт», 2001.- 688 с.