Как сжать временной ряд, где единственными значениями являются 1, 0 и -1

Question

Я пытаюсь эффективно хранить огромное количество (> 1 миллиардов) временных рядов. Каждое значение может быть только 1, 0 или -1, и значение записывается один раз в минуту в течение 40000 минут.

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

Например, если бы я взял 16-минутный период: для записи этих значений потребовалось бы (16 x 2 бита) = 32 бита = 4 байта. Но, вероятно, я могу сократить это число пополам (или больше), если просто назначу число каждой из 16 возможных перестановок.

Мой вопрос: какова формула для определения количества перестановок для 16 значений? Я знаю, как рассчитать его, если значения могут быть любыми, но я озадачен тем, как это сделать, когда есть только 3 значения.

Answer 1

Если -1, 0 и 1 одинаково вероятны, тогда формула для количества битов, требуемых для n выборок, равна потолка (n log ₂ 3 ) . Как вы заметили, для одного семпла вы получите два бита, фактически потратив одно из состояний, тратя чуть более 0,4 бит на семпл.

Как выяснилось, пять семплов очень хорошо вписываются в восемь битов, где 3 ⁵ = 243, и только около 0,015 бит на символ тратится впустую.

Вы можете использовать дополнительные состояния в качестве символов конца потока. Например, вы можете использовать пять из оставшихся 13 состояний, чтобы сигнализировать об окончании потока, указывая, что осталось 0, 1, 2, 3 или 4 выборки. Тогда, если это 1, 2, 3 или 4, есть еще один байт с этими выборками. Немного лучше было бы использовать три состояния для 1 случая, обеспечивая выборку в этом байте. Затем используются семь из 13 состояний, требующих один байт для завершения потока для случаев 0 и 1 и два байта для завершения потока для оставшихся случаев 2, 3 или 4.

Если -1, 0 и 1 имеют заметно отличающиеся вероятности, то вы можете использовать кодирование Хаффмана для выборок, чтобы представить результат в меньшем количестве бит, чем в «плоском» случае выше. Однако существует только один код Хаффмана для одной выборки из трех символов, что в целом не дает хорошей производительности Таким образом, вы снова захотите объединить образцы для лучшей производительности кодирования Хаффмана. (Или используйте арифметическое кодирование, но это более сложное, чем, возможно, необходимо в этом случае.) Таким образом, вы можете снова сгруппировать пять выборок в одно целое число в диапазоне 0..242, и Хаффман закодировать их вместе с концом потока символ (назовите его 243), который встречается только один раз.

Answer 2

Например, вы можете сжать файл и получить отличный уровень сжатия всего с 3 символами.

Если вы хотите выполнить тяжелую работу, вы можете сделать то, что делают базовые алгоритмы zip:

У вас есть 3 значения -1, 0 и 1.

Затем вы можете определить дерево трансляций, например:

bit sequence - symbol  
0            - 0  
10           - 1  
110          - -1  
1110          - End of data 

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

Так что, если у вас есть серии 1,1,0, -1,0, это будет переводиться как:

101001100

Если это все данные, которые вы видите, у вас есть 9 битов, поэтому вам нужно будет что-то дополнить до 16.

Затем просто поставьте конец маркера данных и после этого anytihg.

10100110 01110000

Для этого вам нужно работать с битовыми операторами.

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