© Иван Рощин, Москва

Улучшение сжатия данных: ещё одна идея

(«Радиомир. Ваш компьютер» 8/2003)

Хочу рассказать об одной появившейся у меня идее, которую можно использовать для улучшения сжатия данных. Не знаю, может быть, эта идея уже известна (так как она довольно проста), и я зря об этом пишу, но мне о ней не приходилось слышать.

Идея красива своей парадоксальностью: иногда можно сжать данные… именно потому, что сжать их нельзя!

В архиваторах обычно используется такой приём: если блок данных удалось сжать (т.е. удалось уменьшить его размер), то в архив записывается признак «блок сжат» (например, бит 1) и далее — сжатый блок. Если блок не удалось сжать, в архив записывается признак «блок сохранён без сжатия» (например, бит 0) и далее — исходный блок.

Теперь попробую объяснить смысл идеи на простом примере. Пусть архиватор действует по следующему алгоритму: если блок данных состоит только из следующих друг за другом пар 00 и 11, то он может быть сжат, и в архив записывается бит 1 и далее — 0 вместо каждой пары 00 и 1 вместо каждой пары 11. В противном случае блок сохраняется без сжатия: в архив записывается бит 0 и далее — исходный блок. Например, блок 001100 будет закодирован как 1 010 (для наглядности первый бит, указывающий, сжат блок или нет, отделён пробелом), а блок 101 не может быть сжат и будет закодирован как 0 101.

В табл. 1 приведены результаты архивации всех возможных блоков длиной 4 бита (как нетрудно догадаться, их 16).

Рассмотрим исходный блок 0001. Результатом его архивации будет 0 0001. При восстановлении этого блока, после того, как прочитан первый бит (0), становится ясно, что далее следует исходный блок, сохранённый без сжатия, так как сжат он быть не может. Тогда, прочтя первые три следующих бита (000), мы можем с уверенностью сказать, что четвёртый бит будет равен 1. Он не может равняться 0, так как тогда исходный блок будет 0000, а такой блок может быть сжат — а мы знаем, что исходный блок не может быть сжат! То есть хранить последний бит блока в этом случае не нужно — вот и экономия!

Если применить аналогичные рассуждения к другим блокам, получим, что сэкономить один бит удаётся ещё в трёх случаях — для блоков 0010, 1101 и 1110 — именно за счёт того, что они оказались несжимаемыми! В итоге получим следующее:

Вообще говоря (каким бы ни был алгоритм сжатия), если блок данных не удалось сжать, и он сохранён без сжатия, то его в некоторых случаях можно записать хотя бы на один бит короче (то есть сжать!) именно за счёт того, что известно, что сжат он быть не может.

Может быть, кого-нибудь заинтересует изложенная здесь идея, и он разовьёт её дальше, так, что она сможет быть применена на практике.