6.3. Алгоритмы сжатия данных

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

Качество сжатия характеризуется коэффициентом сжатия, равным отно-

шению объема сжатых данных к объему исходных данных.

В зависимости от возможной точности восстановления исходных данных,

различаю сжатие без потерь (данные восстанавливаются точно в исходном ви-

де) и сжатие с потерями (восстановленные данные не идентичны исходным, но их различиями в том контексте, в котором эти данные используются, можно пренебречь). Сжатие с потерями применяется, например, для упаковки много- цветных фотографических изображений (алгоритм JPEG), звука (алгоритм MP3), видео (группа алгоритмов MPEG). При этом используются особенности человеческого восприятия: например, глаз человека не может различить два

близких оттенка цвета, закодированных 24 битами, поэтому можно без види-

мых искажений уменьшить разрядность представления цвета.

Для многих разновидностей данных – текстов, исполняемых файлов и т.д.

– допустимо применение только алгоритмов сжатия без потерь.

Сжатие без потерь, в основном, базируется на двух группах методов: сло-

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

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

то встречающиеся байты можно закодировать более короткой битовой после- довательностью, а редко встречающиеся – более длинной. Часто в одном алго- ритме используют и словарные, и статистические методы.

6.3.1. Алгоритм rle

Самый простой из словарных методов – RLE (Run Length Encoding, коди- рование переменной длины) умеет сжимать данные, в которых есть последова- тельности повторяющихся байтов. Упакованные RLE данные состоят из управ- ляющих байтов, за которыми следуют байты данных. Если старший бит управ- ляющего байта равен 0, то следующие байты (в количестве, записанном в семи младших битах управляющего байта) при упаковке не изменялись. Если стар- ший бит равен 1, то следующий байт нужно повторить столько раз, какое число записано в остальных разрядах управляющего байта.

Например, исходная последовательность

00000000 00000000 00000000 00000000 11001100 10111111 10111011

будет закодирована в следующем виде (выделены управляющие байты):

10000100 00000000 00000011 11001100 10111111 10111011.

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

дированы всего двумя байтами: 1010 1000 00000000.