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

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

(«Радиомир. Ваш компьютер» 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.bbb по сравнению с файлом 1.bmp наблюдалось для всех архиваторов, принимавших участие в тестировании. Это можно считать косвенным свидетельством того, что эти архиваторы, как и PKZIP, являются байт-ориентированными.

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

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