сжатие данных с плавающей запятой

<p>существуют ли какие-либо методы сжатия без потерь, которые можно применить к данным временных рядов с плавающей запятой, и которые значительно превзойдут, скажем, запись данных в двоичном виде в файл и запуск их через gzip?</p><p>снижение точности может быть приемлемым, но это должно происходить контролируемым образом (т. е. я должен быть в состоянии установить предел, сколько цифр должно быть сохранено)</p><p>я работаю с некоторыми большими файлами данных, которые представляют собой серии коррелированных <code>double</code>s, описывающих функцию времени (то есть значения коррелируются). обычно мне не нужна полная точность <code>double</code>, но мне может понадобиться больше, чем <code>float</code>.</p><p>поскольку существуют специализированные методы без потерь для изображений/аудио, мне было интересно, существует ли что-нибудь специализированное для этой ситуации.</p><p><strong> разъяснение: </strong>я ищу существующие практические инструменты, а не документ, описывающий, как реализовать что-то вроде этого. что-то сравнимое с gzip по скорости было бы отлично. </p>

<p>возможно, вы захотите взглянуть на эти ресурсы:</p><ul> <li> <a href="http://www.cs.unc.edu/~isenburg/lcpfpv/">сжатие без потерь прогнозируемых значений с плавающей точкой</a> </li> <li>документы <a href="http://cs.txstate.edu/~mb92/">martin burtscher</a> : <a href="http://users.ices.utexas.edu/~burtscher/papers/tr08.pdf">сжатие с плавающей точкой fpc двойной точности алгоритм и его реализация</a> , <a href="http://cs.txstate.edu/~mb92/papers/dcc06.pdf">быстрое сжатие без потерь научных данных с плавающей точкой</a> и <a href="http://users.ices.utexas.edu/~burtscher/papers/dcc07a.pdf">сжатие высокой пропускной способности double-precision данные с плавающей точкой</a> </li> </ul><p>вы также можете попробовать <a href="http://en.wikipedia.org/wiki/logluv\_tiff">сжатый logluv tiff</a> для этого, подумал, что я сам не использовал их.</p>

<p>вот несколько идей, если вы хотите создать свой собственный простой алгоритм:</p><ul> <li>используйте xor текущего значения с предыдущим значением, чтобы получить набор битов, описывающих разницу.</li> <li>разделите это различие на две части: одна часть - «биты мантиссы», а другая - «биты экспоненты».</li> <li>используйте кодирование переменной длины (различное количество бит/байт на значение) или любой метод сжатия, который вы выберете, чтобы сохранить эти различия. вы можете использовать отдельные потоки для мантисс и экспонент, поскольку мантиссы могут сжать больше битов.</li> <li>это может не сработать, если вы чередуете два разных источника временных значений. поэтому вам, возможно, придется сжать каждый источник в отдельный поток или блок.</li> <li>чтобы потерять точность, вы можете отбросить наименее значимые биты или байты из мантиссы, оставив показатель степени без изменений.</li> </ul>

<p>поскольку вы заявляете, что вам нужна точность где-то между «float» и «double»: вы можете обнулить любое количество младших разрядов в числах с одинарной и двойной точностью. числа с плавающей точкой ieee-754 представлены в двоичном виде примерно как <code>seeefffffffff</code>, который представляет значение</p><p>знак * 1.fffffff * 2 ^ (eee).</p><p>вы можете обнулить младшую значащую дробь (f). для плавающих с одинарной точностью (32-разрядных) имеется 23 дробных бита, из которых можно обнулить до 22. для двойной точности (64-разрядных) это 52 и до 51. (если вы обнуляете все биты , тогда специальные значения nan и +/- inf будут потеряны).</p><p>особенно, если данные представляют десятичные значения, такие как 1.2345, это поможет в сжатии данных. это связано с тем, что 1.2345 нельзя представить точно как двоичное значение с плавающей запятой, а как <code>0x3ff3c083126e978d</code>, что не подходит для сжатия данных. отрезание младших значащих 24 битов приведет к <code>0x3ff3c08312000000</code>, который по-прежнему с точностью до 9 десятичных цифр (в этом примере разница составляет 1.6e-9). </p><p>если вы сделаете это с необработанными данными, а затем сохраните различия между последовательными числами, будет еще более удобно сжатие (через gzip), если необработанные данные изменяются медленно.</p><p>вот пример в c:</p><pre><code>#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; } </code></pre><p>и один в python/numpy:</p><pre class="lang-py prettyprint-override"><code>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 </code></pre>

<p>поскольку вы запрашиваете существующие инструменты, возможно, <a href="https://computation.llnl.gov/projects/floating-point-compression">zfp</a> подойдет.</p>

<p>возможные методы, которые можно использовать для сжатия с плавающей точкой:</p><ul> <li><p>транспонировать 4xn для поплавка и 8xn для двойного + lz77<br> реализация: <a href="https://github.com/powturbo/turbotranspose">сжатие с плавающей точкой в turbotranspose</a> <br> см. также сжатие с потерями </p></li> <li><p>предиктор (например, метод конечного контекста) + кодирование (например, "целочисленное сжатие").<br> реализация: <a href="https://github.com/powturbo/turbopfor">сжатие с плавающей точкой в turbopfor</a> </p></li> <li><p>по возможности, конвертировать все числа с плавающей запятой в целые числа (например, 1.63 -> 163),<br> затем использовать целочисленное сжатие<br> реализация: <a href="https://github.com/powturbo/turbopfor">целочисленное сжатие</a> </p></li> </ul><p>вы можете протестировать все эти методы с вашими данными, используя инструмент <a href="https://sites.google.com/site/powturbo/downloads">icapp</a> для linux и windows.</p>

<p>один из методов, который используют люди hdf5, - это «перемешивание», когда вы группируете каждый байт для n значений с плавающей запятой вместе. это, скорее всего, даст вам повторяющиеся последовательности байтов, которые будут лучше сжиматься с помощью gzip, <a href="http://www.hdfgroup.org/hdf5/doc\_resource/h5shuffle\_perf.pdf">например</a> .</p><p>второй метод, который я обнаружил и который значительно уменьшает размер сжатых сжатых данных, заключается в том, чтобы сначала преобразовать данные в формат <a href="https://en.wikipedia.org/wiki/half-precision\_floating-point\_format">float16 (половинная точность)</a> и обратно обратно в float32. это приводит к большому количеству нулей в выходном потоке, что может уменьшить размеры файлов примерно на 40-60 процентов после сжатия. одна тонкость заключается в том, что максимальное значение float16 довольно низкое, поэтому вам может потребоваться сначала масштабировать данные, например, в питоне</p><pre class="lang-py prettyprint-override"><code>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 </code></pre><p>некоторые тесты показывают, что средняя абсолютная дробная разница между входом и выходом для некоторых данных составляет около 0,00019 с максимумом 0,00048. это соответствует точности 2 ** 11 мантиссы.</p>

<p>вы можете использовать алгоритм экспоненциального сглаживания холта (алгоритм сжатия, основанный на прогнозировании). первоначально присвойте некоторый вес данным и прогнозируйте следующее значение. если оба данных одинаковы, в msb создается много нулей, выполняя операцию xor</p>