Сжатие данных

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

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

Пусть имеется три записи, содержащие следующие значения:

Эколог………….

Экология……….

Экологический…

Тогда после сжатия приведенных записей по этой технологии будет записано:

0 – Эколог

6 – ия

7 – ческий

Другой тип технологии сжатия основан на иерархическом сжатии данных.

Пусть в файле ПРОДУКТЫ записи упорядочены по возрастанию значений номера накладной (поля НН), как показано в таблице.

Записи файла ПРОДУКТЫ

Номер накладной (НН)	Код покупателя (КП)	Наименование продукта (НП)	Количество, кг (КОЛ)	Цена, руб (ЦЕНА)
		сыр
		масло
		шоколад
		сахар
		крахмал

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

1) постоянная – номер накладной и код покупателя (повторяются в записях);

2) переменная – данные о продуктах: наименование, количество, цена.

Результат иерархического сжатия показан в таблице.

Результат иерархического сжатия записей файла ПРОДУКТЫ

НН	КП	НП	КОЛ	ЦЕНА
		сыр
масло
шоколад
		сахар
крахмал

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

Пусть некоторые значения записаны с помощью символов A, Б, В, Г и подсчитана частота, с которой они встречаются. Принцип кодирования Хаффмана показан в таблице.

Кодирование Хаффмана

Символ	Частота, %	Код
A
В
Г
Б

Символ А встречается чаще других и его код поэтому самый короткий. Все остальные коды длиннее. Использовать в качестве первого кода 0 нельзя, так как он будет совпадать с начальной частью последующих более длинных кодов.

Физическая организация современных баз данных во многом определяет производительность СУБД и представляет коммерческую тайну.

Дата добавления: 2015-05-26