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

Question

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

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

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

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

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

Answer 1

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

Answer 2

Редко все биты номера с двойной точностью значимы.

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

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

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

Таким образом, последовательность образцов со средним значением м и стандартным отклонением с преобразуется в кучу Z балла. Нормальные преобразования Z-score используют double, но вы должны использовать версию с двойной точкой. 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.Масштабируйте это на 16 384, и ваши Z-баллы имеют эффективное разрешение 0,000061 десятичных знаков.

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

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

Answer 3

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

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