Алгоритмы сжатия, использующие исключение повторов

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

В основу алгоритмов RLE положен принцип выявления групп подряд идущих одинаковых символов и замены их структурой, в которой указывается код символа и число повторов, т.е. группа идущих подряд одинаковых символов заменяется на пару кодов вида <код символа; число повторов>. Максимальное число одинаковых символов, которое можно закодировать одной такой парой, определяется длиной кода числа повторов.

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

В качестве примера рассмотрим реализацию RLE а графическом формате PCX. Группа повторяющихся байтов заменяется на байт-счетчик и байт данных. В байте-счетчике старшие два бита содержат единицы, в младших шести битах хранится число повторов. Неповторяющиеся значения, меньшие 0C0_h = 0C0₁₆ = 11000000₂, записываются в сжатые данные без изменений. Для неповторяющихся значений, больших 0C0₁₆ = 11000000₂, (т.е. с двумя единицами в старших разрядах) такой подход недопустим, так как при распаковке такой байт будет восприниматься как байт-счетчик повторов. Поэтому такие байты при записи в сжатый поток предваряются байтом-счетчиком с числом повторов, равным единице (11000001 = С1₁₆). Рассмотрим пример.

Исходные данные: 00;00;00; 00;01;00;FE;FF;FF;FF.

Сжатые данные: С4;00;01;00;С1;FE;C3;FF.

В приведенном примере из строки длиной 10 байтов получена упакованная строка длиной 8 байтов. Видно, что один байт FE кодируется двумя байтами С1;FE, поэтому некоторые данные при таком сжатии могут вырасти в объеме до двух раз. Например:

Исходные данные: CF;FF;CF;FF;CF;FF.

Сжатые данные: C1;CF;C1;FF; C1;CF;C1;FF;C1;CF;C1;FF.

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

Сжатые данные: C5;10;C4;FF;00;01;C1;CF;C1;EF.

Распакованные данные: 10;10;10;10;10;FF;FF;FF;FF;00;01;FF;EF.

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