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

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

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

Сжатие данных: от битов к байтам

Радиомир. Ваш компьютер» 11/2003)
Дополненная версия.

Хотите, покажу фокус? :–) Смотрите, имеется bmp-файл длиной 1406 байтов, содержащий вот такой чёрно-белый рисунок (рис. 1). На рисунке изображены восемь одинаковых объектов. Налицо явная избыточность, так что, по идее, файл должен хорошо сжиматься.

Рис. 1

Попробуем это проверить. Сожмём файл с помощью архиватора PKZIP 2.50:

pkzip 1.zip 1.bmp

В результате получаем архив 1.zip длиной 1073 байта, что всего на 24% меньше длины исходного файла.

А теперь обработаем исходный bmp-файл с помощью «волшебной» программы, текст которой на языке C приведён ниже.

/* bit2byte.c */
/* Compiler: Turbo C 2.0 */

#include <stdio.h>

void main (int argc, char *argv[])
{
 FILE *f_src, *f_dst;
 int i,a,b;

 if (argc<3)
 {printf ("Syntax: bit2byte.exe source-file destiny-file\n"); exit();}
 f_src=fopen(argv[1],"rb");
 if (f_src==NULL) {printf ("Can't open source file\n"); exit();}
 f_dst=fopen(argv[2],"wb");
 if (f_dst==NULL) {printf ("Can't open destiny file\n"); exit();}

 while ((a=fgetc(f_src))!=EOF)
 {
  for (i=0;i<8;i++)
  {
   if ((a&0x80)==0) b=0; else b=1;
   fputc (b,f_dst);
   if ferror(f_dst) {printf ("Can't write to destiny file!\n"); exit ();}
   a=a<<1;
  }
 }

 if ferror(f_src) {printf ("Can't read from source file!\n"); exit ();}
 if (fclose(f_src)!=0) {printf ("Can't close source file!\n"); exit ();}
 if (fclose(f_dst)!=0) printf ("Can't close destiny file!\n");
}

При запуске этой программы надо указать в командной строке имя исходного файла (находящегося в текущем каталоге) и имя формируемого выходного файла (он будет сформирован также в текущем каталоге). Запускаем программу с такими параметрами:

bit2byte.exe 1.bmp 1.bbb

Программа формирует файл 1.bbb, длина которого в восемь раз больше длины исходного файла и равна 11248 байтам. Зачем нужен этот файл? А вот смотрите, сейчас мы попробуем сжать его тем же PKZIP’ом:

pkzip 2.zip 1.bbb

Получили архив 2.zip, длина которого… всего 445 байтов! Это приблизительно в 2,4 раза меньше длины первоначального архива!

Естественно, в файле 1.bbb содержится вся информация, которая была в исходном файле 1.bmp. Эту информацию можно извлечь, обработав файл 1.bbb нижеприведённой программой.

/* byte2bit.c */
/* Compiler: Turbo C 2.0 */

#include <stdio.h>

void main (int argc, char *argv[])
{
 FILE *f_src, *f_dst;
 int i,a;

 if (argc<3)
 {printf ("Syntax: byte2bit.exe source-file destiny-file\n"); exit();}
 f_src=fopen(argv[1],"rb");
 if (f_src==NULL) {printf ("Can't open source file\n"); exit();}
 f_dst=fopen(argv[2],"wb");
 if (f_dst==NULL) {printf ("Can't open destiny file\n"); exit();}

 while ((a=fgetc(f_src))!=EOF)
 {
  for (i=0;i<7;i++)
  {
   a=a<<1;
   a=a+fgetc(f_src);
   if ferror(f_src) {printf ("Can't read from source file!\n"); exit ();}
  }
  fputc (a,f_dst);
  if ferror(f_dst) {printf ("Can't write to destiny file!\n"); exit ();}
 }

 if ferror(f_src) {printf ("Can't read from source file!\n"); exit ();}
 if (fclose(f_src)!=0) {printf ("Can't close source file!\n"); exit ();}
 if (fclose(f_dst)!=0) printf ("Can't close destiny file!\n");
}

При её запуске, как и для предыдущей программы, надо указать в командной строке имена исходного и формируемого файлов. Запускаем:

byte2bit.exe 1.bbb 2.bmp

Получили файл 2.bmp, полностью идентичный первоначальному файлу 1.bmp (в этом легко убедиться, сравнив файлы, например, с помощью утилиты fc.exe).

В чём же секрет фокуса? Как получилось, что «раздутый» в восемь раз файл сжался гораздо лучше исходного? Что делают программы bit2byte и byte2bit?

Чёрно-белое изображение в формате bmp хранится по строкам. Каждая строка представлена последовательностью байтов, а в каждом байте хранится информация о восьми пикселах. Каждому пикселу соответствует один бит: 0 — чёрный пиксел, 1 — белый.

Рассмотрим, как представлены в файле 1.bmp две строки изображения: строка, соответствующая верху первого объекта, и строка, соответствующая верху второго объекта (рис. 2).

Рис. 2

Что мы видим? Подчёркнутые последовательности пикселов в этих двух строках совпадают, а значит, совпадают и соответствующие последовательности битов в файле. А вот совпадений на байтовом уровне не наблюдается, так как второй объект сдвинут относительно первого на пиксел вправо.

Архиватор PKZIP является байт-ориентированным, т.е. ищет как раз совпадающие последовательности байтов. Совпадений на битовом уровне он просто «не видит». Поэтому он и смог сжать файл 1.bmp только на 24%.

А что делает программа bit2byte? Она читает байты из исходного файла и после чтения каждого байта записывает в формируемый файл восемь байтов, представляющих собой значения битов прочитанного байта. Например, если из исходного файла прочитан байт 00110101, в формируемый файл будут записаны байты 0, 0, 1, 1, 0, 1, 0, 1.

Таким образом, после обработки файла 1.bmp программой bit2byte последовательности битов в нём превратились в последовательности байтов в сформированном файле 1.bbb. Это позволило PKZIP’у при сжатии файла 1.bbb обнаружить в нём совпадающие последовательности, в результате чего и произошло значительное повышение степени сжатия.

Программа byte2bit, как вы уже, наверно, догадались, выполняет обратную задачу: прочитав из исходного файла (ранее полученного в результате работы программы bit2byte) очередные восемь байтов, она записывает в формируемый файл один байт, «собранный» из прочитанных значений.

Кроме PKZIP, я протестировал и несколько других архиваторов, сжимая с их помощью файлы 1.bmp и 1.bbb. Архиваторы запускались с параметрами по умолчанию. Результаты тестирования (включая и полученные ранее для PKZIP) вы можете увидеть в табл. 1.

Для каждого архиватора в таблице приведены три строки с информацией: первая строка соответствует исходному файлу 1.bmp (чтобы было с чем сравнивать), вторая — архиву, полученному при сжатии этого файла, и третья — архиву, полученному при сжатии файла 1.bbb. Информацию в каждой строке следует понимать так: первое число — длина файла в байтах, второе число — длина файла в процентах от длины исходного файла 1.bmp.

Табл. 1
PKZIP 2.50 *********************************** 1406 (100%)
*************************** 1073 (76%)
*********** 445 (32%)
ARJ 2.60 *********************************** 1406 (100%)
************************** 1058 (75%)
********** 412 (29%)
IMP 1.12 *********************************** 1406 (100%)
**************************** 1110 (79%)
********* 359 (26%)
HA 0.99c *********************************** 1406 (100%)
************************ 958 (68%)
****** 258 (18%)
RAR 2.90 beta 4 *********************************** 1406 (100%)
************************** 1056 (75%)
******** 312 (22%)

Как видно из таблицы, существенное улучшение сжатия файла 1.bbb по сравнению с файлом 1.bmp наблюдалось для всех архиваторов, принимавших участие в тестировании. Это можно считать косвенным свидетельством того, что эти архиваторы, как и PKZIP, являются байт-ориентированными.

Какой можно сделать вывод из всего вышесказанного? Если вы пользуетесь каким-либо из указанных выше архиваторов или другим байт-ориентированным архиватором, и сжимаемый файл представляет собой массив элементов, размер которых не кратен байту (элементы могут быть как одной какой-то длины, так и у разных элементов может быть разная длина), и в файле присутствуют совпадающие последовательности элементов (а значит, и совпадающие последовательности битов), то имеет смысл не сжимать такой файл непосредственно, а воспользоваться программой bit2byte и сжимать уже полученный «раздутый» файл (а при извлечении файла из архива — соответственно, воспользоваться программой byte2bit, чтобы восстановить исходный файл).

* * *

Исполняемые файлы (для DOS) программ bit2byte и byte2bit, а также листинги этих программ в текстовом виде вы можете скачать с сайта журнала или с моей web-страницы (см. ниже). Там же доступен и файл 1.bmp (на случай, если вы захотите проверить приведённые в статье результаты или протестировать ещё какие-нибудь архиваторы).

Скачать исполняемые файлы программ bit2byte и byte2bit (12 КБ ZIP)
Скачать листинги программ bit2byte и byte2bit в текстовом виде (1 КБ ZIP)
Скачать файл 1.bmp (1 КБ ZIP)

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

1. 

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

2. 

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

3. 

«Улучшение сжатия данных: ещё одна идея». «Радиомир. Ваш компьютер» 8/2003.

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