Проблема создания и сжатия больших информационных массивов, информационных хранилищ и складов данных

Использование бинарных деревьев.

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

Полезность тех или иных компьютерных систем, основанных на ис­пользовании БД, во многом определяется количеством хранимых данных, необходимых для решения прикладных задач. Однако возрастающая сложность решаемых задач, приводящая каждые 8 лет к удвоению необхо­димой для решения информации, сохраняет перед разработчиками аппа­ратных средств ПК проблему увеличения емкости накопителей информации для ее хранения. Ограниченные размеры НЖМД современных ПК заставляют искать радикальные приемы уменьшения количества хранимой ин­формации за счет ее обработки, Использование методов сжатия данных позволяет достичь высокой экономии как в пространстве для хранения данных, так и в скорости их обработки и передаче.

Методы сжатия данных можно разделить на три категории:

1. Методы, зависящие от прикладной области. Их обычно нельзя
встроить в программное обеспечение. Они позволяют использовать достоинства интеллектуальных терминалов и распределенного интеллекта.

2. Методы редактирования и подстановки. Такие методы можно
встраивать в СУБД и общесистемное универсальное программное обеспечение.

3. Методы кодирования данных, которые допускают аппаратную
и программную реализацию.

Рассмотрим некоторые из методов сжатия данных, находящих приме­нение при разработке БД.

Значительная часть информации, представляемой на экране дисплея в виде слов и фраз запросов к БД и сформированных ответов, состоит из слов, помогающих пользователю ориентироваться в данных. Хранить их в БД не обязательно. Их можно хранить в отдельном файле. Вместо форми­рования длинной типовой фразы можно сформировать или считывать из таблицы ее идентификатор, Состоящий всего из одного или нескольких би­тов.

В БД, где слова и фразы естественного языка составляют существен­ную часть данных, вместо этих слов и фраз могут храниться кодирующие их символы. Некоторые комбинации битов в каждом 8-битовом байте мо­гут представлять около 200 наиболее употребительных слов. Если данный байт не определяет кода интересующего слова, его можно расширить за счет следующего байта. Таким образом, оказываются закодированными другие слова. Получив закодированный текст, специальная программа-дешифратор может при помощи простых просмотров таблиц легко преоб­разовать его в обычную цепочку алфавитно-цифровых символов. Для многих форм диалога с БД вполне хватает словарного запаса в 256 слов.

По этой же схеме можно кодировать не только слова, а целые фразы,

В тех случаях, когда какой-либо параметр принимает значения из не­большого множества значений, нет необходимости выписывать это значе­ние полностью. Вместо него можно воспользоваться его кодом. Для неко­торых элементов данных, например таких как «тип» коды обычно исполь­зуются. Другие элементы, такие как «имя», часто выписываются буква за буквой. Однако, большинство имен, встречающихся в элементах данных, принадлежат относительно небольшому множеству. Имя человека вполне можно закодировать одним байтом. В число 256 допустимых имен войдут практически все встречающиеся имена. Первый бит может выполнять до­полнительную функцию по кодированию пола. Тогда можно иметь 128 женских и 128 мужских имен. Если трудно уложиться в такую схему коди­рования, то одна 8-битовая комбинация должна служить байтом-исключением, говорящим, что в последующих байтах имя выписано полно­стью. Фамилию не удается заменить кодом, особенно в странах, где живут выходцы из самых разных мест. Но, тем не менее даже в США 128 фамилий составляют 80 % всех фамилий, а 256 - более 90 %. Они представляются од­ним байтом. Два байта могут отобразить почти все фамилии, но таблица подстановок оказалась бы слишком громоздкой.

Когда поля в записях БД хранятся в привычной для человека форме, в них почти всегда символов больше, чем нужно. Так в файлах дата часто хранится в виде поля из 6 байт. Однако в машине для представления меся­ца, дня и года достаточно 16 бит, т.е. 2 байта по 4, 5 и 7 бит соответственно. Преобразование этих двух байтов в удобочитаемую для человека форму может выполнять совсем короткая программа.

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

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

Рассмотренные выше приемы сжатия данных - это по сути примеры редактирования данных. СУБД могут предоставлять широкий набор воз­можностей редактирования, позволяющих получить удобочитаемые, хо­рошо структурированные выдачи на бумаге и на экране и в то же время компактные формы хранения данных.

Существуют два вида редактирования - видимое и невидимое (про­зрачное). Пользователь СУБД может и не знать, что отбрасываются зна­чащие нули или упаковываются цепочки пробелов. Однако может оказать­ся полезным знание языка редактирования, с помощью которого можно описать структуру документа или воспользоваться уже имеющимися фор­матами и шаблонами. Форматы и шаблоны можно хранить в отдельном модуле. Вместо шаблонов и форматов в СУБД циркулируют закодирован­ные ссылки на них. Их число может быть в сотни раз меньше, чем количе­ство закодированных символов. В общих случаях интерфейс для пользова­теля остается тем же.

Кадры, высвечиваемые при экранном диалоге с БД, могут быть стан­дартными или стандартными с некоторой долей переменной информации в них. Сообщения содержат как правило переменную информацию и иденти­фикацию формата. Средства редактирования могут помогать в выборе нужного формата для документа и в заполнении в нем переменных полей. Циркулировать при этом должны только переменные данные. Точно также на экран можно выдавать формат, в который пользователь вставит пере­менную информацию. В дальнейшем только такая информация будет пере­дана на обработку. С кадрами-форматами связываются определенные ко­манды или редактирующий формат, которые определяют способ размеще­ния переменной информации в кадре-формате. СУБД должны иметь необ­ходимый набор функций выбора формата, редактирования и преобразова­ния данных, а также размещения данных в нужных местах экранных форм.