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

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

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

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

Эколог………….

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

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

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

0 – Эколог

6 – ия

7 – ческий

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

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

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

Номер накладной ( НН)	Код покупателя ( КП)	Наименование продукта ( НП)	Количество, кг ( КОЛ)	Цена, руб ( ЦЕНА)
15	47	сыр	23	9200
15	47	масло	17	6000
15	47	шоколад	5	12000
38	111	сахар	55	1400
38	111	крахмал	8	1030

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

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

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

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

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

НН	КП	НП	КОЛ	ЦЕНА
15	47	сыр	23	9200
		масло	17	6000
		шоколад	5	12000
38	111	сахар	55	1400
		крахмал	8	1030

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

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

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

Символ	Частота, %	Код
A	45	1
В	40	01
Г	35	001
Б	30	0001

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

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

91