Страница Ивана Рощина > Статьи >

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

ZXNet: 500:95/462.53
E-mail: bestview@mtu-net.ru
WWW: http://www.ivr.da.ru

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

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

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

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

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

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

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

Табл. 1
Блок Результат архивации
0000 1 00  
0001 0 0001
0010 0 0010
0011 1 01  
0100 0 0100
0101 0 0101
0110 0 0110
0111 0 0111
1000 0 1000
1001 0 1001
1010 0 1010
1011 0 1011
1100 1 10  
1101 0 1101
1110 0 1110
1111 1 11  

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

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

Табл. 2
Блок Результат архивации
0000 1 00  
0001 0 000 
0010 0 001 
0011 1 01  
0100 0 0100
0101 0 0101
0110 0 0110
0111 0 0111
1000 0 1000
1001 0 1001
1010 0 1010
1011 0 1011
1100 1 10  
1101 0 110 
1110 0 111 
1111 1 11  

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

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

Другие мои статьи о сжатии:

1. 

«Повышение степени сжатия музыкальных модулей». «Радиомир. Ваш компьютер» 7/2002.

2. 

«Улучшение сжатия программ на ассемблере Z80». «Радиомир. Ваш компьютер» 4/2003.

3. 

«Сжатие данных: от битов к байтам». «Радиомир. Ваш компьютер» 11/2003.

Страница Ивана Рощина > Статьи >