Как мне сжать большое количество одинаковых двойников?

Question

Я хочу хранить миллиарды (10 ^ 9) чисел с плавающей запятой двойной точности в памяти и экономить место. Эти значения сгруппированы в тысячи упорядоченных наборов (они являются временными рядами), и в пределах набора я знаю, что разница между значениями обычно невелика (по сравнению с их абсолютным значением). Кроме того, чем ближе друг к другу, тем выше вероятность того, что разница будет относительно небольшой.

Идеальным соответствием будет дельта-кодирование, в котором хранится только разность каждого значения по сравнению с его предшественником. Однако мне нужен произвольный доступ к подмножествам данных, поэтому я не могу зависеть от последовательного прохождения полного набора. Поэтому я использую дельты для базового уровня по всему набору, который дает дельты, которые, как я ожидаю, будут в пределах 10-50 процентов от абсолютного значения (большую часть времени).

Я рассмотрел следующие подходы:

• делит меньшее значение на большее, получая значение от 0 до 1, которое может быть сохранено как целое число с некоторой фиксированной точностью плюс один бит для запоминания, какое число было разделено на какое. Это довольно просто и дает удовлетворительное сжатие, но это не метод без потерь и, следовательно, только вторичный выбор.
• XOR в двоичном64 IEEE 754 кодирует представления обоих значений и сохраняет длину длинных отрезков нулей в начале показателя степени и мантиссы плюс остальные биты, которые были разными. Здесь я совершенно не знаю, как судить о сжатии, хотя думаю, что в большинстве случаев оно должно быть хорошим.

Существуют ли стандартные способы сделать это? Какие могут быть проблемы с моими подходами выше? Какие еще решения вы видели или использовали сами?

Answer 1

Редко все значащие биты числа двойной точности.

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

Часто вы обнаружите, что вам нужен только 16 бит фактического динамического диапазона. Вы, вероятно, можете сжать все это в массивы "short", которые сохранят все исходные данные.

Используйте простую «технику Z-счета», где каждое значение действительно является знаком стандартной дроби со знаком.

Таким образом, последовательность выборок со средним значением m и стандартным отклонением s преобразуется в группу значений Z. Обычные преобразования Z-счета используют двойное число, но вы должны использовать версию этого двойного с фиксированной запятой. s / 1000 или s / 16384 или что-то, что сохраняет только фактическую точность ваших данных, а не шумовые биты на конце.

for u in samples:
    z = int( 16384*(u-m)/s )

for z in scaled_samples:
    u = s*(z/16384.0)+m

Ваши Z-показатели сохраняют приятную простоту в работе со статистической взаимосвязью с исходными образцами.

---

Допустим, вы используете подписанный 16-битный Z-счет. У вас есть +/- 32,768. Масштабируйте это до 16384, и ваши Z-показатели имеют эффективное разрешение 0,000061 десятичного.

Если вы используете подписанный 24-но Z-счет, у вас +/- 8 миллионов. Масштабируйте это до 4,194,304, и у вас будет разрешение 0,00000024.

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

Answer 2

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

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

Answer 3

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