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

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

Предположим, что некоторые данные написаны с помощь символов А, Б, В, Г, Д, тогда с учетом относительной частоты с которой эти символы встречаются, у них различные коды (табл. 1).

Таблица 1

Коды символов

 

Символ	Частота, %	Код
А	35	1
В	30	01
Г	20	001
Д	10	0001
Б	5	0000

 

Символ А встречается чаще остальных, и потому имеет самый короткий код, состоящий из одного бита. Все остальные коды должны быть длиннее, однако нельзя использовать код на основе одного нуля, так как он будет совпадать с начальной частью дру­гих, более длинных кодов. Оценочно можно сказать, что в сред­нем общая длина закодированного текста на 40% меньше, чем при отсутствии кодирования.

Глоссарий

 

Диспетчер дисков	Программное обеспечение, контролирующее перемещение данных между оперативной памятью и диском
Диспетчер файлов	Программное обеспечение, управляющее размещением данных на диске и структурами данных
Индекс	Средство ускорения операции поиска записей в таблице, а также выполнения других операций, использующих поиск: извлечение, модификация, сортировка и т.д.
Индексный файл	Файл, в котором хранится информация индекса
Кодирование Хаффмана	Технология кодирования символов, которая может быть эффективной для сжатия различных символов, встречающихся с разной частотой
Сжатие на основе различий	Технология сжатия данных в БД, которая предусматривает замену некоторого значения сведениями о его отличиях от предыдущего значения
Словарь данных	Часть СУБД, определяющая структуру пользовательских данных и возможности их использования
Стратегический селектор	Программное обеспечение, преобразующее требование пользователя в эффективную для исполнения форму
Транзакция	Последовательность операций над БД, рассматриваемых СУБД как единое целое
Хеширование	Технология быстрого прямого доступа к хранимой записи на основе заданного значения некоторого поля, при этом, поле не обязательно должно быть ключевым

14