Алгоритм сжатия данных IEEE-754

Question

У кого-нибудь есть рекомендации по хорошему алгоритму сжатия, который хорошо работает со значениями с плавающей запятой двойной точности? Мы обнаружили, что двоичное представление значений с плавающей запятой приводит к очень низким степеням сжатия в обычных программах сжатия (например, Zip, RAR, 7-Zip и т. Д.).

Данные, которые нам нужно сжать, представляют собой одномерный массив 8-байтовых значений, отсортированных в монотонно возрастающем порядке. Значения представляют собой температуры в градусах Кельвина с интервалом, как правило, ниже 100 градусов. Количество значений варьируется от нескольких сотен до максимум 64K.

Разъяснения

• Все значения в массиве различны, хотя повторение существует на уровне байтов благодаря способу представления значений с плавающей запятой.

• Желателен алгоритм без потерь, поскольку это научные данные. Преобразование в представление с фиксированной точкой с достаточной точностью (~ 5 десятичных знаков) может быть приемлемым при условии значительного улучшения эффективности хранения.

Обновление

Нашел интересную статью на эту тему. Не уверен, насколько применим подход к моим требованиям.

http://users.ices.utexas.edu/~burtscher/papers/dcc06.pdf

Answer 1

Первое, на что нужно обратить внимание: попробуйте сжать данные до , чтобы преобразовать их с двойной точностью. Напомним ваш комментарий Дэвиду Торнли, если ваши АЦП с ИК-изображениями не имеют 24 значащих разряда, 32-разрядные числа с плавающей запятой должны иметь более чем достаточную точность; только ваше требование точно сохранить шум, создаваемый последующей обработкой, является проблемой. В противном случае, возможно, было бы целесообразно реинжинировать вашу обработку, определив таблицу значений, которую она генерирует, и вместо этого сохранив индекс для этой таблицы.

Второе: если ваш алгоритм сжатия знает, что ваши данные находятся в 8-байтовых блоках, это будет намного эффективнее; это потому, что он не добавит ваши старшие байты с младшими байтами. В качестве грубого метода предварительной обработки вы можете попробовать поставить перед каждым двойником префикс уникальным байтом (возможно, запятой ASCII?), Прежде чем передавать его через компрессор на основе байтов, такой как gzip; это должно привести к лучшему общему сжатию, даже если промежуточный поток будет на 12% больше. Менее грубым, но более трудоемким было бы написать собственное сжатие, адаптированное к этой задаче - возможно, с использованием 8-уровневого дерева для представления ожидаемых значений каждого байта в вашем двойном числе.

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

Answer 2

Все перечисленные вами кодеры ориентированы на байты и отбрасываются несколькими свойствами типа double. С одной стороны, существует схема, в которой 12-разрядный показатель / знак не очень хорошо сочетается с границами байтов, а с другой - шумность вашего ввода. С первой частью легко разбираться множеством способов, вторая ограничит эффективность любого сжатия без потерь, которое вы к нему добавляете. Я думаю, что даже лучший результат будет менее чем удивительным, я не знаю ваших данных, но я подозреваю, что вы можете рассчитывать лишь на 25% экономии, более или менее.

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

1. Обрабатывать поток как 64-битные целые и дельта-кодировать смежные значения. Если у вас есть серии значений с одним и тем же показателем, он фактически обнулит их, а также, возможно, некоторые старшие биты мантиссы. Будут переполнения, но данные по-прежнему нуждаются только в 64 битах, и операция может быть восстановлена.

2. На этом этапе вы можете при желании попробовать грубое целочисленное предсказание и сохранить различия.

3. Если вы следовали предложению ранее, у вас будет почти половина значений, начиная с 000 ... и почти половина с FFF ... Чтобы устранить это, поверните значение влево (ROL) на 1 бит и XOR со всеми Fs, если текущий LSB равен 1. Реверс XOR с Fs, если LSB равен 0, тогда ROR.

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

4. Вы можете попробовать переупорядочить байты, чтобы сгруппировать байты с одинаковым значением. Мол, сначала все самые значимые байты и так далее. По крайней мере, вы должны сначала получить что-то вроде массива нулей с максимум несколькими битами шума.

5. Запускать через обычный компрессор или даже сначала RLE на серии нулей, затем энтропийный энкодер, как Хаффман, или лучше, энкодер диапазона от 7zip / LZMA.

Есть одна хорошая вещь в ваших данных, она однообразна. В ваших данных есть что-то плохое: набор слишком мал. Сколько вы хотите сэкономить, простые килобайты? зачем? Эффективность сжатия сильно пострадает, если между смежными значениями часто существует экспоненциальная разница.

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

Answer 3

Если вам требуется архивное хранилище с высокой степенью сжатия, вам может пригодиться «Высокопроизводительное сжатие данных с плавающей точкой двойной точности» от Burtscher & Patanaworabhan или «Быстрое и эффективное сжатие данных с плавающей точкой» от Lindstrom & Isenberg ,

Если вы хотите более быстрый динамический доступ за счет более низкой степени сжатия, тогда может подойти 1D подъемный вейвлет. Вы можете квантовать данные в меньшие целые числа, указав количество цифр для хранения. Затем используйте дельта-кодирование с прогнозирующей моделью с последующим преобразованием по Хаару или более дорогим вейвлет-преобразованием и арифметическим кодированием коэффициентов, превышающих указанное значение.

надеюсь, это поможет

Вы можете получить алгоритм ZFP Линдстрема здесь: https://github.com/LLNL/zfp

Answer 4

Алгоритмы сжатия основаны на повторениях и закономерностях, и числа с плавающей запятой в этом не преуспевают.

Первый вопрос: можете ли вы использовать значения с плавающей запятой одинарной точности, которые сразу же дадут вам 50% сжатия. Немногие термометры имеют точность до семи цифр, и показатель степени будет отображать температуры значительно ниже всего, что мне сказали, что вы можете получить.

Если нет, можете ли вы отфильтровать свои температуры, округлив их до эквивалента N цифр (более вероятно, N / 0,301 бит)? Это может ввести достаточно закономерностей, чтобы быть полезным.

Если вам действительно нужно хранить 64 бита информации для каждого показания температуры, и все биты значимы и не предсказуемы по сравнению с другими битами, то вы фактически не сможете сжать ее.

Answer 5

Можете ли вы сделать дельту между соседними значениями?
Есть ли предел тому, насколько значение может меняться между измерениями? Допустимо ли ограничивать это изменение каким-либо максимальным значением ставки (за счет введения некоторого сглаживания?)

Очевидно, что предел реальной точности значений термодатчика ограничен. Вам нужно хранить 64 бита точности или лучше хранить целое число, скажем, 0,01 Кельвина?

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

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

например. Если у вас есть максимальная разница в 1 градус между показаниями, вы можете сохранить изменения в 1/256 от этого в байте. Если вам нужно хранить больший диапазон или большую точность, используйте короткий, деленный на некоторый коэффициент.
Поэтому следующее чтение будет = last_reading + (float) increment / 256.0

Answer 6

Можно подумать о перекодировании ваших данных с помощью энтропийного кодера (Хаффман, Шеннон-Фано, Арифметическое кодирование). Но это даст хорошие результаты, только если у вас много повторений точек данных и если вы знаете, какие символы будут появляться с какой вероятностью.