RDM/2 : Сожмите ваши данные.

	The Russian Electronic Developer Magazine
	Русский электронный журнал разработчика

Сожмите ваши данные.

Во многих случаях программистской практики приходится сталкиваться с проблемой хранения данных. Данные стремятся заполонить все свободное место на диске, их нужно периодически передвигать с одного диска на другой, пытаясь освободить место для следующей порции данных, засовывать в архивы, архивы где-то хранить, мучительно вспоминать, кто, когда и куда засунул то, что вам потребовалось именно сейчас. Заканчивается все это сообщением "Read error" при попытке восстановить данные с вашей дискеты.

Как решить проблему громоздких данных, как переложить с бестолкового пользователя на вашу программу задачу сжатия данных, как обеспечить сохранность ваших данных от умышленного или неумышленного изменения, как сжать ваши данные намного лучше стандартных компрессоров, как, наконец, ускорить работу вашей программы с этими медленными жесткими дисками? Нет ничего проще! Но обо всем по порядку.

Неявные методы сжатия данных.

Простейшим способом борьбы с объемом данных, совершенно не требующем от программиста никаких усилий, является использование утилит прозрачного сжатия данных "на лету" типа STACKER, DriveSpace или ZipStream.

Излишки обнуляйте.

Многие базы данных используют DBF формат, в котором каждая запись состоит из полей, каждое из которых является текстовой строкой фиксированной длины. Иногда некоторые поля не используются, но оставлены в силу исторических причин или для совместимости. Часто в таких неиспользованных полях оказывается записан различный мусор, поскольку не инициализированы поля структуры, которая программой отображается в DBF запись. Аналогично, если в DBF поля записываются строки Си (оканчивающиеся нулем), то в оставшемся месте поля записи может оказаться мусор.

С точки зрения последующего сжатия каким-либо файловым компрессором лучше все неиспользованные поля и части полей записи заполнять нулями или пробелами.

Записывайте только значащие данные.

Более радикальным способом борьбы c DBF форматом может оказаться ...отказ от него. В самом деле, DBF часто используют как самый простой, известный и легкий способ хранения данных, и если не нужна совместимость в реальном времени с машинами баз данных, измените формат на более компактный и естественный. А для совместимости всегда можно сделать пункт меню "Save as..." или отдельностоящую утилиту. Итак, переходим к записям переменной длины, да еще от чисто текстовых - к двоичным. Текстовые поля меняем на байтовые длиной в sizeof(поле вашей структуры данных), для текстовых данных убираем постоянную длину строки.

Что же мы получим в итоге? Длина файла данных существенно сократилась, но в вашей программе никаких изменений не произошло, за исключением процедур записи и чтения файлов данных. В самом деле, модель данных (как массива структур вида struct MyRecord myrec[MAXRECNUM]) не изменилась.

Используем Zlib.

Некоторое время назад я прочитал в русскоязычной конференции fido7.su.os2.prog о библиотеке Zlib, general purpose data compression library. (Спасибо Dmitry V. Irtegov aka Fat Brother" и другим участникам)

Знакомство с Zlib превзошло все ожидания. Исходный код на pure C, вдобавок написанный в хорошем стиле. Полностью бесплатная библиотека, том числе и для коммерческого использования. Лицензионно чистая. Компилируется везде и чем угодно, есть интерфейсы для всякого безобразия наподобие C++Builder 3, Delphi 3, Java, Perl, Python, Visual Basic.

Функции библиотеки позволяют использовать запись в файл/чтение из файла с прозрачным сжатием/распаковкой в стиле:

  void *buf;
  int len;
  gzFile zfp;
  ....
  zfp = gzopen("myfile","wb");
  ....
  gzwrite(zfp,buf,len);
/* gzprintf, gzputs, gzputc, gzflush, gzrewind, gztell и т.д. */
  ....
  gzclose(zfp);
  ....
  zfp = gzopen("myfile","wb");
  ....
  gzread(zfp,buf,len);
  ....
  gzclose(zfp);

Есть функции для сжатия данных в памяти из буфера в буфер:

  Byte *Compr, *UnCompr;
  int ComprLen,UncomprLen;
  ....
  Compr    = (Byte*)malloc(ComprLen);
  UnCompr  = (Byte*)malloc(UncomprLen);
/* заполняем uncompr */
  ....
  rc =   compress(Compr, &ComprLen, UnCompr, UncomprLen);
  ....
  rc = uncompress(UnCompr, &UncomprLen, Compr, ComprLen);

С такими возможностями ваша пpогpамма может использовать больше памяти, чем вам дает опеpационная система, и либо pаботать без свопиpования, либо иметь в pаспоpяжении больше 480Мб для OS/2 ver3-4 или 2Гб для остального.
Есть большое количество полезных функций, включая подсчет контрольной суммы.

Действительно, эта библиотека заслуживает только превосходных оценок, как и ее авторы - Jean-loup Gailly и Mark Adler.

Однако лучше один раз увидеть, чем сто раз услышать. Официальный ftp - ftp://ftp.cdrom.com/pub/infozip/zlib/. Этот сайт может оказаться перегруженным; мне, например, значительно больше повезло на ftp://uu.net/pub/.

Итак, тратим один день на освоение Zlib, после чего делаем zlib.lib или zlib.dll, переключаемся на следующую передачу и нажимаем на педаль газа. Данные, которые занимали 50Mb теперь требуют 10, а программа начала быстрее работать! В самом деле, самым медленным устройством для PII и далее сегодня становится жесткий диск. Дополнительные затраты процессорного времени на сжатие/распаковку данных с лихвой окупаются для быстрых процессоров сокращением времени записи на диск и чтения с диска.

Использование Zlib позволяет автоматически решить проблему защиты ваших данных. При необходимости всегда можно добавить более или менее сложный механизм шифрации данных, чтобы сильно продвинутый пользователь не смог вскрыть их при помощи gzip.

Достигая невозможного.

Можно ли еще больше повысить плотность упаковки наших данных? Оказывается, можно! На первый взгляд это кажется невероятным, тем не менее это так.

Посмотрим, как этого достичь. Откажемся на время от использования zlib и поэкспериментируем с нашими данными и различными "general purpose" файловыми компрессорами. Для всех современных упаковщиков (arj, zip, rar) результаты будут, как правило, примерно одинаковыми. Давайте однако используем голову программиста по своему прямому предназначению и вспомним, что внешний по отношению к ваше программе упаковщик понятия на имеет о структуре ваших данных и относится к ним как к битовому потоку повторяющихся данных со случайной составляющей. Другими словами, упаковщики настроены на однородные повторяющиеся входные данные, а мы постараемся без потери информации преобразовать наши данные к виду, наиболее похожему на однородные и повторяющиеся.

Транспонирование.

Например, в случае использования вышеописанной DBF-подобной структуры данных

  struct MyRecord
  { type A a;
    type B b;
    type C c;
    type D d;
  }

записи в файл данных будут помещены в порядке

  ABCD
  ABCD
  ....
  ABCD

Если мы сделаем транспонирование, т.е. запишем данные в порядке:

  AAAA....A
  BBBB....B
  СССС....C
  DDDD....D

то однородность наших данных резко повысится, соответственно возрастет и сжатие при использовании любых упаковщиков.

Разностная форма.

Посмотрим на наши данные повнимательнее и мы заметим, что соседние записи, как правило, несильно отличаются друг от друга.

Рассмотрим пример. Пусть у нас есть байтовый массив длиной 256 элементов, в котором находятся числа:

  char m[256]={ 0,1,2,3,4,5,.....256};

запишем его в файл и посмотрим, как его сжимают упаковщики. Теперь запишем первый элемент и последовательные разности: m[0], m[1]-m[0],m[2]-m[1],....m[255]-m[254]. В файле у нас получится: 0,1,1,1,1,1,1,.....1.

Давайте почувствуем разницу:

Упаковщик Исходный массив, байт Разностная форма, байт
Rar 344 104
Zip 384 142

Не стоит забывать, что упаковщики добавляют к данным заголовок файла, и кpоме того, на коpотких данных не успевают набpать статистику.

Двумерные байтовые данные типа полутонового изображения.

Если изображение не слишком зашумлено и не слишком резкое (высокая корреляция соседних пикселов), можно использовать так называемое кодирование с предсказанием, которое в простейшем случае представляет собой комбинацию разностей по строкам и по элементам строки. Конечно, это будет не JPEG, но тем не менее... Тем более, что данными могут быть совсем не фотографии, а например, последовательности измерений с АЦП.

  int nx,ny,x,y,v;
  char mas[256][256], mas1[256][256];
  nx = 256;
  ny = 256;

  /* кодирование */
  mas1[0][0] = mas[0][0];
  for(x=1;x<nx;x++) mas1[0][x] = (mas[0][x]-mas[0][x-1]) & 0xff;
  for(y=1;y<ny;y++)
  { mas1[y][0] = (mas[y][0]-mas[y-1][0]) & 0xff;
    for(x=1;x<nx;x++)
    { v = mas[y][x-1]+mas[y-1][x];
      mas1[y][x] = (mas[y][x] - v) & 0xff;
    }
  }
  ....
  fwrite(mas1,ny,nx,fp);
  ...
  /* декодирование */
  fread(mas1,ny,nx,fp);
  mas[0][0] = mas1[0][0];
  for(x=1;x<nx;x++) mas[0][x] = (mas1[0][x]+mas1[0][x-1]) & 0xff;
  for(y=1;y<ny;y++)
  { mas[y][0] = (mas1[y][0]+mas[y-1][0]) & 0xff;
    for(x=1;x<nx;x++)
    { v = mas[y][x-1]+mas[y-1][x];
      mas1[y][x] = (mas1[y][x] + v) & 0xff;
    }
  }

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

Пусть русские ракеты летают не только в космосе и хоккее!

(с) Евгений Коцюба, 1999

Интересные ссылки:

Комментариев к странице: 0 | Добавить комментарий

Редактор: Дмитрий Бан
Оформление: Евгений Кулешов

Упаковщик	Исходный массив, байт	Разностная форма, байт
Rar	344	104
Zip	384	142