Во многих случаях программистской практики приходится сталкиваться с проблемой хранения данных. Данные стремятся заполонить все свободное место на диске, их нужно периодически передвигать с одного диска на другой, пытаясь освободить место для следующей порции данных, засовывать в архивы, архивы где-то хранить, мучительно вспоминать, кто, когда и куда засунул то, что вам потребовалось именно сейчас. Заканчивается все это сообщением "Read error" при попытке восстановить данные с вашей дискеты трехлетней давности.
Как решить проблему громоздких данных, как переложить с бестолкового пользователя на вашу программу задачу сжатия данных, как обеспечить сохранность ваших данных от умышленного или неумышленного изменения, как сжать ваши данные намного лучше стандартных компрессоров, как ускорить работу вашей программы с этими медленными жесткими дисками, как, наконец, сократить время загрузки ваших данных через эти медленные каналы передачи данных ? Нет ничего проще! Но обо всем по порядку.
С точки зрения последующего сжатия каким-либо файловым компрессором лучше все неиспользованные поля и части полей записи заполнять нулями или пробелами.
Что же мы получим в итоге? Длина файла данных существенно сократилась, но в вашей программе никаких изменений не произошло, за исключением процедур записи и чтения файлов данных. В самом деле, модель данных (как массива структур вида struct MyRecord myrec[MAXRECNUM]) не изменилась.
Знакомство с Zlib превзошло все ожидания. Исходный код на pure C, вдобавок написанный в хорошем стиле. Полностью бесплатная библиотека, том числе и для коммерческого использования. Лицензионно чистая. Компилируется везде и чем угодно, есть интерфейсы для всякого безобразия наподобие C++Builder 3, Delphi 3, Java, Perl, Python, Visual Basic. В настоящее время библиотека используется во многих проектах Open Source проектах (я знаю Mesa 3D , wxWindows, MGL by SciTechsoft ).
Функции библиотеки позволяют использовать запись в файл/чтение из файла с прозрачным сжатием/распаковкой в стиле:
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.
Хотя следует заметить, что визуально сжатие данных происходит
несколько медленнее, чем при использовании zip'а.
Однако лучше один раз увидеть, чем сто раз услышать. Официальный 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) результаты будут, как правило, примерно одинаковыми. Давайте однако используем голову программиста по своему прямому предназначению и вспомним, что внешний по отношению к ваше программе упаковщик понятия на имеет о структуре ваших данных и относится к ним как к битовому потоку повторяющихся данных со случайной составляющей. Другими словами, упаковщики настроены на однородные повторяющиеся входные данные, а мы постараемся без потери информации преобразовать наши данные к виду, наиболее похожему на однородные и повторяющиеся.
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ать статистику.
Приведем пример для большого файла. Исходный файл представляет собой
словарь слов, отсортированных по алфавиту. Разделителем между словами служит,
как обычно в языке Си, 0x00. Используем несколько видоизмененную
разностную форму: в каждом слове словаря начало слова, совпадающее с предыдущим,
заменяем символом 0x00. Кроме того, попробуем использовать кодировку
числа повторяющихся символов одним байтом со значениями от 0 до 31,
предварительно желательно удостоверится в том, что в исходном файле
не встречаеются символы 1-31
| Исходная форма | "разностная" форма | форма c кодировкой повторений |
| адлер
адлера адлерах адлерам адлерами адлерберг |
адлер
00000а 000000х 000000м 0000000и 00000берг |
адлер
0x05а 0x06х 0x06м 0x07и 0x05берг |
| Файл | исходный размер | bzip2 | rar | zip | ha |
| исходный словарь | 15139031 | 4017450
26.6% |
3506369
23.2% |
3406981
22.5% |
3336947
22.0% |
| разностная форма | 15139031 | 693849
4.6% |
1045018
6.9% |
1386780
9.1% |
1295865
8.6% |
| форма c кодировкой повторений | 3454333 | 611229
4.04% |
777152
5.13% |
903968
5.97% |
720009
4.76 |
Итого - разница в 2.5-5 раз !!! Обратите внимание на результаты для bzip2.
-------
int *st;
int n;
[...]
n = 142651; //1373024
[...]
fp = fopen("s.bin","wb");
for(i=0;i<n;i++)
fwrite(&st[i],sizeof(int),1,fp);
fclose(fp);
fp = fopen("s.bin3","wb");
for(i=0;i<n;i++)
fwrite(&st[i],3,1,fp);
fclose(fp);
fp = fopen("s.hex","w");
for(i=0;i<n;i++)
fprintf(fp,"%x ",st[i]);
fclose(fp);
fp = fopen("s.dec","w");
for(i=0;i<n;i++)
fprintf(fp,"%i ",st[i]);
fclose(fp);
| Файл | исходный размер | bzip2 | rar | zip | ha |
| s.bin | 570604
5492096 |
300590
3563942 |
337057
3561196 |
344004
2950497 |
333543
2837484 |
| s.bin3 | 427953
4119072 |
303160
3609035 |
318496
3382974 |
354092
3642416 |
339152
3371983 |
| s.hex | 786002
8492688 |
345581
3862500 |
400043
3751773 |
388746
3632994 |
370852
3583934 |
| s.dec | 887447
9873082 |
349287
3944731 |
398698
3760490 |
389366
3617739 |
373713
3590173 |
Таким образом, использование более компактного исходного представления данных не всегда может приводить к меньшим размерам архивов, но с другой стороны, при этом уменьшается выигрыш от использования файловых компрессоров.
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 - 2001[an error occurred while processing this directive]