Я пытаюсь сжать набор данных временных рядов с коэффициентом сжатия 25%. Для меня это превратилось в месть.
Данные представляют собой исторические котировки акций с 1-минутным интервалом за период в 1 месяц (см. примечания к набору данных) с 0 отсутствующими данными. Это равно примерно 9000 точек данных типа uint32_t (я не делаю десятичные дроби)
Моей первой попыткой было использовать сжатие FastPFor для всех данных. Это привело к степени сжатия ~ 80%. Не достаточно хорош. Так -
Сначала я избавляюсь от всех временных меток (очевидно)
Затем я отсортировал исторические данные и удалил все дубликаты. Это уменьшило количество уникальных значений с ~ 5000 до 1000. Оттуда я использовал дифференциальный алгоритм сжатия SIMD для дальнейшего сжатия. Они также упаковывают биты. Это привело к окончательной степени сжатия ~ 5%. Большой! Вот в чем проблема.
Чтобы восстановить набор данных, вы должны иметь возможность привести его в порядок. Моя идея состояла в том, чтобы иметь инвертированные индексы для каждого из обработанных значений выше, где каждый индекс будет ссылаться на свою исходную позицию. Это, конечно, просто добавило 9000 номеров. Это приблизило размер к исходному размеру.
Пример:
Values Indexes
10 ===> 40, 20, 55, 100, 56, 21
25 ===> 1, 5
...
В результате я пытаюсь сжать инвертированные индексы.
- Сортировать их
- Избавьтесь от любых значений, которые на +1 от предыдущего значения ( RLE )
- Сожмите каждый из списков индексов с помощью github SIMDCompression от Lemire (я также попробовал его алгоритм FastPFor)
К сожалению, эта попытка сжать индексы не увенчалась успехом. В конце концов, это привело только к степени сжатия ~ 75% при фактическом сжатии с использованием 20-64 бит на целое число. Обратите внимание, что ранее я упоминал, что использую 32-битные числа. Сжатие сделало списки индексов только с 1 числом, в 2 раза превышающим их исходный размер (я ожидал, что он останется прежним).
Попытки использовать инвертированные индексы бесполезны - недостаточно хороши, чтобы оправдать дополнительную обработку, когда она сопоставима с исходными размерами.
Некоторые другие идеи, которые у меня были:
Определите наиболее распространенные последовательности чисел, используйте кодировку типа «Хаффмана», где вы назначите определенное значение для его представления.
Алгоритмы сжатия работают лучше с большим количеством данных - возможно, объединить все индексы в 1 массив, а затем сжать его один раз?
Каков наилучший способ сжатия инвертированных индексов?
Существует ли теоретическая минимальная компрессия?
Знаете ли вы какие-либо методы, которые я могу использовать вместо этого?
Любой вклад приветствуется.
Пример данных
- Отформатированные цены акций с индексами цитата -- › [indexes] - (индексы не обрабатываются)
Примечания
- Использование индексов будет использоваться только для восстановления набора данных и не будет использоваться для каких-либо других запросов.
