Сжатие данных с плавающей запятой - PullRequest
39 голосов
/ 25 декабря 2011

Существуют ли какие-либо методы сжатия без потерь, которые можно применить к данным временных рядов с плавающей запятой, и они значительно превзойдут, скажем, запись данных в двоичном виде в файл и запуск их через gzip?

СокращениеТочность может быть приемлемой, но это должно происходить контролируемым образом (то есть я должен иметь возможность установить ограничение на количество сохраняемых цифр)

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

Поскольку существуют специальные методы без потерь для изображений / аудио, мне было интересно, существует ли что-нибудь специализированное для этой ситуации.

Пояснение: Я ищу существующие практические инструменты, а не документ, описывающий, как реализовать нечто подобное.Что-то сравнимое с gzip по скорости было бы отлично.

Ответы [ 7 ]

17 голосов
/ 11 февраля 2014

Вот несколько идей, если вы хотите создать свой собственный простой алгоритм:

  • Используйте xor текущего значения с предыдущим значением, чтобы получить набор битов, описывающих разницу.
  • Разделите эту разницу на две части: одна часть - «биты мантиссы», а другая - «биты экспоненты».
  • Используйте кодирование переменной длины (различное количество бит / байт на значение) или любой метод сжатия, который вы выберете, чтобы сохранить эти различия. Вы можете использовать отдельные потоки для мантисс и экспонент, поскольку мантиссы могут сжать больше битов.
  • Это может не сработать, если вы чередуетесь между двумя разными источниками временных значений. Поэтому вам, возможно, придется сжать каждый источник в отдельный поток или блок.
  • Чтобы потерять точность, вы можете отбросить наименее значимые биты или байты из мантиссы, оставив показатель степени в целости.
4 голосов
/ 20 апреля 2016

Поскольку вы заявляете, что вам нужна точность где-то между 'float' и 'double': вы можете обнулить любое количество младших разрядов в числах с одинарной и двойной точностью.Числа с плавающей точкой IEEE-754 представлены в двоичном виде примерно как seeefffffffff, который представляет значение

sign * 1.fffffff * 2 ^ (eee).

Вы можете обнулить наименее значимоедробь (е) бит.Для плавающих с одинарной точностью (32-битных) имеется 23 дробных бита, из которых можно обнулить до 22. Для двойной точности (64-битных) это 52 и до 51. (Если вы обнуляете все биты, тогда специальные значения NaN и +/- inf будут потеряны).

Особенно, если данные представляют десятичные значения, такие как 1,2345, это поможет в сжатии данных.Это связано с тем, что 1.2345 нельзя представить точно как двоичное значение с плавающей запятой, а скорее как 0x3ff3c083126e978d, что не подходит для сжатия данных.Отрезание младших значащих 24 битов приведет к 0x3ff3c08312000000, что по-прежнему с точностью до 9 десятичных цифр (в этом примере разница составляет 1,6e-9).

Если вы сделаете это с необработанными данными, а затем сохраните различия между последовательными числами, будет еще более удобно сжатие (посредством gzip), если необработанные данные изменяются медленно.

Здесьпример в C:

#include <inttypes.h>

double double_trunc(double x, int zerobits)
{
  // mask is e.g. 0xffffffffffff0000 for zerobits==16
  uint64_t mask = -(1LL << zerobits);  
  uint64_t floatbits = (*((uint64_t*)(&x)));
  floatbits &= mask;
  x = * ((double*) (&floatbits));
  return x;
}

и один в python / numpy:

import numpy as np

def float_trunc(a, zerobits):
    """Set the least significant <zerobits> bits to zero in a numpy float32 or float64 array.
    Do this in-place. Also return the updated array.
    Maximum values of 'nzero': 51 for float64; 22 for float32.
    """

at = a.dtype
assert at == np.float64 or at == np.float32 or at == np.complex128 or at == np.complex64
if at == np.float64 or at == np.complex128:
    assert nzero <= 51
    mask = 0xffffffffffffffff - (1 << nzero) + 1
    bits = a.view(np.uint64)
    bits &= mask
elif at == np.float32 or at == np.complex64:
    assert nzero <= 22
    mask = 0xffffffff - (1 << nzero) + 1
    bits = a.view(np.uint32)
    bits &= mask

return a
3 голосов
/ 05 апреля 2018

Поскольку вы запрашиваете существующие инструменты, возможно, zfp подойдет.

3 голосов
/ 19 марта 2017

Возможные методы, которые можно использовать для сжатия с плавающей точкой:

Вы можете протестировать все эти методы с вашими данными, используя инструмент icapp для Linux и Windows.

3 голосов
/ 04 февраля 2016

Один из методов, который используют люди HDF5, - это «тасование», когда вы группируете каждый байт для N значений с плавающей запятой вместе. Это, скорее всего, даст вам повторяющиеся последовательности байтов, которые будут лучше сжиматься при помощи gzip, например .

Второй метод, который я обнаружил и который значительно уменьшает размер сжатых сжатых данных, заключается в том, чтобы сначала преобразовать данные в формат float16 (половинная точность) и обратно обратно в float32. Это приводит к большому количеству нулей в выходном потоке, что может уменьшить размеры файлов примерно на 40-60 процентов после сжатия. Одна тонкость заключается в том, что максимальное значение float16 довольно низкое, поэтому вам может понадобиться сначала масштабировать данные, например, в питоне

import numpy as np
import math

input = np.array(...)

# format can only hold 65504 maximum, so we scale input data
log2max = int(math.log(np.nanmax(input), 2))
scale = 2**(log2max - 14)
scaled = input * (1./scale)

# do the conversion to float16
temp_float16 = np.array(scaled, dtype=np.float16)
# convert back again and rescale
output = np.array(temp_float16, dtype=np.float32) * scale

Некоторые тесты показывают, что средняя абсолютная дробная разница между входом и выходом для некоторых данных составляет около 0,00019 с максимумом 0,00048. Это соответствует точности 2 * 11 мантиссы.

1 голос
/ 26 февраля 2016

Вы можете использовать алгоритм экспоненциального сглаживания Холта (алгоритм сжатия, основанный на прогнозировании).Первоначально присвойте некоторый вес данным и прогнозируйте следующее значение. Если оба данных одинаковы, в MSB выдает много нулей, выполняя операцию XOR

...