Вопрос о сжимаемости некоторых групп чисел - PullRequest
1 голос
/ 07 апреля 2011

Допустим, у нас есть набор чисел, которые увеличиваются в маленькие значения с большим смещением

например, смещение = 123456789

наши числа: 123456790 123456791 123456793 123456796 123456799 123456804

если вычесть смещение из этих чисел, мы получим 1 2 4 7 10 15

Числа будут сохранены с 8 байтами других данных, что в сумме составит 12 других байтов, тогда группа из 10000 этихбудет сжат в один блок

, поэтому, если мы будем хранить эти числа как 32-битные целые числа и сжимать их, если мы будем использовать второй набор чисел, будут ли они сжиматься лучше?или потому что они содержат одинаковое количество энтропии, они будут сжиматься точно так же?

Поскольку мой непосредственный ответ моих коллег по работе был на то, что второй набор будет сжиматься лучше, поскольку в 32-битном числе будет много нулейво втором наборе, однако, энтропия такая же (я думаю), поэтому типичный алгоритм сжатия не поймет этого в любом случае и не приведет к аналогичной степени сжатия?

В конечном счете, я думаю, что мне нужно испытать это, чтобы увидетькаковы результаты, но мне любопытно попытаться выяснить это заранее.

1 Ответ

3 голосов
/ 07 апреля 2011

Это известно как дельта-кодирование . В зависимости от специфики ваших данных, это может дать вам лучшее сжатие. Также возможно получить более прямую экономию: например, если вы точно знаете, что разница между соседними элементами никогда не будет лежать вне диапазона 0–255, вы можете хранить дельты как отдельные байты, а не как 32-битные числа .

...