Обзор алгоритмов сжатия без потерь

RLE

Групповое кодирование – Run Length Encoding (RLE) – один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары "счетчик, значение". Лучший, средний и худший коэффициенты сжатия – 1/32, 1/2, 2/1.

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

При кодировании *.exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt..., которые часто встречаются в ресурсах (строки в кодировке Unicode).

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

Кодер RLE

ТекущийСимвол := ДайОчереднойСимвол()
ТекущееСостояние := НЕТ_ПОВТОРОВ
ТекущаяДлина := 0
Пока ТекущийСимвол <> EOF
  Буфер := ДайОчереднойСимвол()
  Если Буфер = ТекущийСимвол
    Если ТекущееСостояние = НЕТ_ПОВТОРОВ 
      Выдать ( НЕТ_ПОВТОРОВ )
      Выдать ( ТекущаяДлина )
      Выдать ( ТекущаяДлина предыдущих символов сообщения )
      ТекущаяДлина := 2 
      ТекущееСостояние := ПОВТОРЫ 
    Иначе
      ТекущаяДлина := ТекущаяДлина + 1 
    Конец если 
  Иначе
    Если ТекущееСостояние = НЕТ_ПОВТОРОВ
      ТекущаяДлина := ТекущаяДлина + 1 Иначе
      Выдать ( ПОВТОРЫ ) 
      Выдать ( ТекущаяДлина ) 
      Выдать ( ТекущийСимвол ) 
      ТекущаяДлина := 1 
      ТекущееСостояние := НЕТ_ПОВТОРОВ 
    Конец если 
  Конец если
  ТекущийСимвол := Буфер
Конец пока

Декодер RLE

ТекущийКод := ДайКодФрагмента()
Пока ТекущийКод <> EOF
  ТекущаяДлина := ДайДлинуФрагмента()
  Если ТекущийКод = НЕТ_ПОВТОРОВ
    Выдать ( ТекущаяДлина, следующих символов сообщения )
  Иначе
    Выдать ( ТекущаяДлина, ДайОчереднойСимвол() ) 
  Конец если
  ТекущийКод := ДайКодФрагмента() 
Конец пока

К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.