Я тестирую свой новый формат файла изображения, который, не вдаваясь в ненужные подробности, состоит из 24-битного формата PPM RGB на пиксель, передаваемого через поток сжатия zlib, и 8-байтового заголовка, добавляемого спереди.
Пока я писал тесты для оценки производительности соответствующего кода, который реализует это, у меня был один тестовый пример, который дал довольно ужасные результаты.
unsigned char *image = new unsigned char[3000*3000*3];
for(int i=0;i<3000*3000;++i) {
image[i*3] = i%255;
image[i*3+1] = (i/2)%255;
image[i*3+2] = (i*i*i)%255;
}
Теперь то, что я делаю, - это создание полностью упакованного 3-байтового изображения размером 3000x3000 пикселей, в котором красные и зеленые полосы неуклонно увеличиваются, но синий компонент будет немного различаться.
Когда я сжал это с использованием потока zlib для моего формата .ppmz, он смог уменьшить размер с 27 000 049 байт (причина в том, что в заголовках нет даже 27 миллионов - 49 байт) до 25 545 520 байт. Этот сжатый файл составляет 94,6% от исходного размера.
Поначалу меня это очень взволновало, потому что я подумал, что даже если синий компонент настолько хаотичен, что ему ничего не поделаешь, по крайней мере, красный и зеленый компоненты повторяются совсем немного. Достаточно умный компрессор должен быть в состоянии сжаться до 1/3 размера ...
Чтобы проверить это, я взял исходный несжатый файл размером 27 МБ и RAR-файл, и он получил 8 535 878 байт. Это довольно хорошо, на 31,6%, даже лучше, чем треть!
Тогда я понял, что допустил ошибку при определении моего тестового изображения. Я использовал мод 255, когда должен был зажимать 255, то есть мод 256:
unsigned char *image = new unsigned char[3000*3000*3];
for(int i=0;i<3000*3000;++i) {
image[i*3] = i%256;
image[i*3+1] = (i/2)%256;
image[i*3+2] = (i*i*i)%256;
}
Дело в том, что теперь у моих пикселей есть еще одно значение, которое я пропускал ранее. Но когда я снова запустил свой код, ppmz стал жалким 145797-байтовым файлом. WinRAR сжал его в 62K.
Почему это крошечное изменение объясняет эту огромную разницу? Даже мощный WinRAR не смог получить оригинальный файл размером менее 8 МБ. Что такое повторение значений каждые 256 шагов, при этом каждые 255 шагов полностью изменяются? Я понял, что с %255 он делает шаблоны первых двух цветовых компонентов немного не в фазе, но поведение вряд ли случайное. А потом просто сумасшедшая модульная арифметика, сбрасываемая в последний канал. Но я не понимаю, как это может объяснить такой огромный разрыв в производительности.
Интересно, это скорее математический вопрос, чем вопрос программирования, но я действительно не понимаю, как исходные данные могут содержать больше энтропии, чем мои недавно измененные данные. Я думаю, что степень зависимости 2 указывает на то, что связано с алгоритмами.
Обновление: я провел еще один тест: я переключил третью строку обратно на (i*i*i)%255, но оставил остальные на %256. Степень сжатия ppmz немного увеличилась до 94,65%, а RAR - 30,9%. Похоже, они прекрасно справляются с линейно растущими последовательностями, даже когда они не синхронизированы, но происходит нечто довольно странное, когда арифметический мод 2 ^ 8 чертовски более дружественен к нашим алгоритмам сжатия, чем другие значения.