Сжатие способом кодирования серий: алгоритм RLE

Базовая классификация обратимых алгоритмов сжатия

Существует много разных практических методов сжатия без потери информации, которые, как правило, имеют разную эффективность для разных типов данных и разных объемов. Однако, в основе этих методов лежат три главные классические схемы сжатия:

- кодирование серий последовательностей (RLE);

- статистические методы сжатия;

- словарные (эвристические) методы сжатия.

Сжатие способом кодирования серий: алгоритм RLE

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Проблема всех аналогичных методов заключается в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других - некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток в начале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.

В основе алгоритма RLE лежит идея выявления повторяющихся последовательностей данных и замены их более простой структурой, в которой указывается код данных и коэффициент повторения. Например, пусть задана такая последовательность данных, что подлежит сжатию: 1 1 1 1 2 2 3 4 4 4. В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).

Эвристические (словарные) алгоритмы сжатия (LZ, LZW) ищут в файле строки, которые повторяются и строят словарь фраз, которые уже встречались. Обычно такие алгоритмы имеют целый ряд специфических параметров (размер буфера, максимальная длина фразы и т.п.), подбор которых зависит от опыта автора работы, и эти параметры добираются таким образом, чтобы достичь оптимального соотношения времени работы алгоритма, коэффициента сжатия и перечня файлов, которые хорошо сжимаются.

Статистические алгоритмы (Хаффмана, Шеннона-Фано, арифметические) Статистические алгоритмы используют статистическую модель данных, и качество сжатия информации напрямую зависит от того, насколько хороша эта модель. Учет статистических свойств данных в простейшем случае означает использование для кодирования неравномерных кодов – часто встречающиеся символы кодируются короткими кодами, а редко – длинными. Т.е., такие алгоритмы нуждаются в знании вероятностей появления символов в изображении, оценкой чего может являться в простом случае частота появления символов во входных данных. Как правило, эти вероятности неизвестны. Целью кодирования является преобразование входного потока в поток бит минимальной длины, что достигается уменьшением энтропии (хаотичности) входного потока путем учета частот символов.

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

Первый заключается в просмотре входного потока и построении кодирования на основании собранной статистики (при этом требуется два прохода по файлу - один для просмотра и сбора статистической информации, второй - для кодирования, что несколько ограничивает сферу применения таких алгоритмов, т.к., таким образом, исключается возможность однопроходного кодирования "на лету", применяемого в телекоммуникационных системах, где и объем данных, подчас, не известен, а их повторная передача или разбор может занять неоправданно много времени). В таком случае, в выходной поток записывается статистическая схема использованного кодирования. Данный метод известен как статическое кодирование Хаффмена. Вместе со сжатым файлом передается таблица символов. Такие алгоритмы достаточно неплохо сжимают большинство файлов, но необходимая дополнительная передача таблицы частот символов, а также необходимость двух проходов исходного файла для набора статистики и сжатия.

Второй метод - метод адаптивного кодирования. Его принцип состоит в том, чтобы менять схему кодирования в зависимости от характера изменений входного потока. Адаптивные - начинают работать с фиксированной начальной таблицей частот символов (обычно все символы сначала равновероятны) и в процессе работы эта таблица изменяется в зависимости от символов, которые встречаются в файле. Преимущества: однопроходность алгоритма, не нуждается в передаче таблицы частот символов, достаточно эффективно сжимает широкий класс файлов. Такой подход имеет однопроходный алгоритм и не требует сохранения информации об использованном кодировании в явном виде. Адаптивное кодирование может дать большую степень сжатия, по сравнению со статическим, поскольку более полно учитываются изменения частот входного потока. Данный метод известен как динамическое кодирование Хаффмена.

С учетом этого статистические алгоритмы можно разделить на три класса:

1. Не адаптивные - используют фиксированные, заблаговременно заданные вероятности символов. Таблица вероятностей символов не передается вместе с файлом, поскольку она известна заблаговременно. Недостаток: узкая область использования для определенной таблицы частот, для которых достигается приемлемый коэффициент сжатия.

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

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

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

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

В статическом кодировании Хаффмена входным символам (цепочкам битов различной длины) ставятся в соответствие цепочки битов, также, переменной длины - их коды. Длина кода каждого символа берется пропорциональной двоичному логарифму его частоты, взятому с обратным знаком. А общий набор всех встретившихся различных символов составляет алфавит потока. Это кодирование является префиксным, что позволяет легко его декодировать в результативный поток, т.к., при префиксном кодировании, код любого символа не является префиксом кода никакого другого символа - алфавит уникален.