Недавно я реализовал небольшую программу для визуализации внутренней работы схемы, сжимающей временные последовательности чисел с плавающей запятой при помощи выполнения XOR последующих значений. Визуализации получились красивыми и помогли мне понять этот красивый алгоритм гораздо проще, чем все объяснения, которые я встречал ранее.
Алгоритм
Алгоритм* прост. Сначала мы записываем первое число с плавающей запятой полностью; для всех последующих чисел выполняется XOR с предыдущим числом, а затем результат кодируется одним из трёх способов.
[*Конкретно эта версия сжатия чисел с плавающей запятой при помощи XOR была впервые описана в «Gorilla: A Fast, Scalable, In-Memory Time Series Database» и часто называется «Gorilla-сжатием».]
- Мы записываем один бит 02. Он показывает, что число идентично предыдущему.
- Мы записываем последовательность из двух битов 112. Далее мы записываем 5-битное целое число, обозначающее количество начальных нулей в значении, полученном при помощи XOR. Затем мы записываем 6-битное целое число, обозначающее количество битов в подпоследовательности, начинающейся с первого бита 1, которая включает последний бит 1 и заканчивается им. Затем мы записываем эту подпоследовательность, опуская все нули в начале и в конце.
- Мы записываем последовательность из двух битов 102. Затем мы сразу же записываем подпоследовательность полученного при помощи XOR значения, имеющую тот же начальный индекс и длину, что и последняя записанная нами подпоследовательность.
Как выбрать между вариантами (2) и (3)? Преимущество (3) в том, что мы опускаем 5+6=11 битов, которые в противном случае потребовались бы для хранения количества начальных нулей и длины последовательности, но (3) мы можем использовать, только если наша ненулевая подпоследовательность умещается в окно, определённое предыдущими значениями смещения и длины. В статье Gorilla предлагается простая эвристика: если ранее использованная подпоследовательность битов включает все ненулевые биты, то мы выбираем (3) и опускаем запись битов смещения и длины. В противном случае мы выбираем (2) и записываем новое смещение и длину. Стоит отметить, что эта эвристика минимизирует количество случаев, когда нам нужно записывать 11 битов значений смещения/длины, но необязательно обеспечивает оптимальное сжатие, потому что может оказаться, что мы записываем для последующих значений гораздо более длинные подпоследовательности, чем необходимо (подробнее об этом ниже).
Хотя алгоритм прост, из его описания не совсем очевидно, почему он должен обеспечивать хорошее сжатие. Со случаем (1) всё просто — повторяющиеся значения сжимаются в один бит. Но почему сработает усечение нулей в начале и в конце при XOR последующих значений с плавающей запятой? Давайте применим алгоритм к реальным данным и посмотрим, как это выглядит!
DECIMAL BITS IN XOR BITS OUT
0.007859230041503906 0011111110000000000110001000000000000000000000000000000000000000 0011111110000000000110001000000000000000000000000000000000000000
0.0076792240142822266 0011111101111111011101000100000000000000000000000000000000000000 0000000011111111011011001100000000000000000000000000000000000000 1101000010001111111110110110011
0.008411884307861328 0011111110000001001110100100000000000000000000000000000000000000 0000000011111110010011100000000000000000000000000000000000000000 10111111100100111000
0.00831747055053711 0011111110000001000010001100000000000000000000000000000000000000 0000000000000000001100101000000000000000000000000000000000000000 10000000000011001010
0.008234977722167969 0011111110000000110111011000000000000000000000000000000000000000 0000000000000001110101010100000000000000000000000000000000000000 10000000011101010101
0.008572578430175781 0011111110000001100011101000000000000000000000000000000000000000 0000000000000001010100110000000000000000000000000000000000000000 10000000010101001100
0.009616851806640625 0011111110000011101100100000000000000000000000000000000000000000 0000000000000010001111001000000000000000000000000000000000000000 10000000100011110010
0.009622573852539063 0011111110000011101101010000000000000000000000000000000000000000 0000000000000000000001110000000000000000000000000000000000000000 10000000000000011100
0.00926518440246582 0011111110000010111110011010000000000000000000000000000000000000 0000000000000001010011001010000000000000000000000000000000000000 1101111001011101001100101
0.009131669998168945 0011111110000010101100111010000000000000000000000000000000000000 0000000000000000010010100000000000000000000000000000000000000000 10001001010000
0.008625507354736328 0011111110000001101010100100000000000000000000000000000000000000 0000000000000011000110011110000000000000000000000000000000000000 11011100011001100011001111
0.008272171020507813 0011111110000000111100010000000000000000000000000000000000000000 0000000000000001010110110100000000000000000000000000000000000000 100101011011010
0.008666276931762695 0011111110000001101111111010000000000000000000000000000000000000 0000000000000001010011101010000000000000000000000000000000000000 100101001110101
0.009252548217773438 0011111110000010111100110000000000000000000000000000000000000000 0000000000000011010011001010000000000000000000000000000000000000 101101001100101
0.009163856506347656 0011111110000010110001001000000000000000000000000000000000000000 0000000000000000001101111000000000000000000000000000000000000000 100000110111100
0.008917093276977539 0011111110000010010000110010000000000000000000000000000000000000 0000000000000000100001111010000000000000000000000000000000000000 100010000111101
0.009442806243896484 0011111110000011010101101100000000000000000000000000000000000000 0000000000000001000101011110000000000000000000000000000000000000 100100010101111
0.009443044662475586 0011111110000011010101101110000000000000000000000000000000000000 0000000000000000000000000010000000000000000000000000000000000000 100000000000001
0.009201765060424805 0011111110000010110110000110000000000000000000000000000000000000 0000000000000001100011101000000000000000000000000000000000000000 100110001110100
0.009229660034179688 0011111110000010111001110000000000000000000000000000000000000000 0000000000000000001111110110000000000000000000000000000000000000 100000111111011
0.008151531219482422 0011111110000000101100011100000000000000000000000000000000000000 0000000000000010010101101100000000000000000000000000000000000000 101001010110110
0.008004188537597656 0011111110000000011001001000000000000000000000000000000000000000 0000000000000000110101010100000000000000000000000000000000000000 100011010101010
0.007958173751831055 0011111110000000010011000110000000000000000000000000000000000000 0000000000000000001010001110000000000000000000000000000000000000 100000101000111
0.0069658756256103516 0011111101111100100010000100000000000000000000000000000000000000 0000000011111100110001000010000000000000000000000000000000000000 11010000100101111110011000100001
0.0044634342193603516 0011111101110010010010000100000000000000000000000000000000000000 0000000000001110110000000000000000000000000000000000000000000000 100000111011000000000
0.004178524017333984 0011111101110001000111011000000000000000000000000000000000000000 0000000000000011010101011100000000000000000000000000000000000000 100000001101010101110
0.00484156608581543 0011111101110011110101001100000000000000000000000000000000000000 0000000000000010110010010100000000000000000000000000000000000000 100000001011001001010
0.003814220428466797 0011111101101111001111110000000000000000000000000000000000000000 0000000000011100111010111100000000000000000000000000000000000000 100001110011101011110
В первом столбце чисел показаны значения сжимаемых временных последовательностей в десятичном виде. Конкретно эта временная последовательность измеряет время, проведённое в одной области кода enn-trainer на каждой итерации прогона обучения.
Второй столбец — это описание в виде 64-битного числа с плавающей точкой тех же чисел. Красным показан бит знака, зелёным — экспонента, а синим — мантисса. Стоит отметить, что биты экспоненты идентичны почти во всех числах последовательности, что ожидаемо, когда значения отличаются менее, чем в два раза. Также стоит отметить, что у чисел есть много начальных нулей, что не совсем очевидно в десятичном представлении. Похоже, что эти тайминги записываются с разрешением в миллисекунды, то есть значения меньше 0,02 умещаются всего в 15 битов.
В третьем столбце показаны XOR каждого значения с предыдущим значением, где область ненулевых битов выделена жёлтым. Полученные при помощи XOR значения содержат множество нулей в начале (потому что бит знака и биты экспоненты у последующих значений не меняются) и множество нулей в конце (потому что в исходных значениях уже имелось множество нулей в конце). Именно благодаря этим регулярным длинным последовательностям нулей в начале и конце и работает сжатие!
В четвёртом столбце показаны биты, ставшие результатом работы алгоритма. В первой строке записано полное представление первого числа без сжатия. Во второй строке мы впервые записываем 11 контрольных битов, количество нулей в начале (810 = 010002), длину ненулевой области — 1 (1710 = 0100012)** и ненулевые биты 111111110110110011.
[** Мы вычитаем из длины 1, потому что в противном случае может произойти переполнение 6 битов, выделенных под длину в случае, когда все биты отличаются, и длина равна 64. Это абсолютно допустимо, потому что длина всегда не меньше 1.]
В третьей строке область ненулевых битов попадает в то же окно, поэтому вместо этого мы записываем 10 контрольных битов и ненулевую подпоследовательность 111111100100111000. Стоит отметить, что эта подпоследовательность содержит три нуля в конце, но эти три бита всё равно занимают меньше места, чем 11 битов, которые могли бы нам понадобиться для записи нового смещения и новой длины. Мы продолжаем пропускать смещение и длину до девятой строки, где мы переходим к новому смещению и длине, потому что область ненулевых битов в XOR не попадает в ранее использовавшееся окно.
Вся эта последовательность (в том числе и не показанные выше значения) сжимается с коэффициентом 3,03. Даже если мы сравним с использованием 32-битных значений одинарной точности с плавающей запятой, то коэффициент сжатия всё равно составит 1,51.
См. здесь простую реализацию алгоритма кодирования и декодирования менее чем в сотне строк Rust (не включая структуры
BitReader
/BitWriter
). Код адаптирован из программы https://github.com/jeromefroe/tsz-rs, имеющей более сложный код, но гораздо более подробные комментарии. В моей реализации содержатся две дополнительные опции: сжатие с потерями, маскирующее часть самых младших битов в мантиссе, и описанное в следующем разделе простое улучшение, способное существенно повысить сжатие для некоторых временных последовательностей.Модифицируем алгоритм
Как мы отметили в предыдущем разделе, в алгоритме сжатия Gorilla используется эвристика для изменения размера окна. Он жадно минимизирует количество изменений окна, что на практике чаще всего хорошо работает, но не обеспечивает гарантированно максимального сжатия. В частности, у такой эвристики есть один патологический режим отказа: если последовательность содержит значение выброса, требующее для своего кодирования очень большого окна, а все последующие значения имеют ненулевые значения только в гораздо меньшем подокне, то мы зафиксируемся на неэффективно большом окне, потому что никогда не столкнёмся с условием, приводящим к изменению размера окна. Вот пример такого события:
DECIMAL BITS IN XOR BITS OUT
0 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000
26.33333396911621 0100000000111010010101010101010101100000000000000000000000000000 0100000000111010010101010101010101100000000000000000000000000000 11000011000011000000001110100101010101010101011
42.69767379760742 0100000001000101010110010100110101100000000000000000000000000000 0000000001111111000011000001100000000000000000000000000000000000 100000000011111110000110000011000000
56.29090881347656 0100000001001100001001010011110010000000000000000000000000000000 0000000000001001011111000111000111100000000000000000000000000000 100000000000010010111110001110001111
70.9795913696289 0100000001010001101111101011000110100000000000000000000000000000 0000000000011101100110111000110100100000000000000000000000000000 100000000000111011001101110001101001
77.60713958740234 0100000001010011011001101101101101100000000000000000000000000000 0000000000000010110110000110101011000000000000000000000000000000 100000000000000101101100001101010110
73.88888549804688 0100000001010010011110001110001110000000000000000000000000000000 0000000000000001000111100011100011100000000000000000000000000000 100000000000000010001111000111000111
82.1276626586914 0100000001010100100010000010101110100000000000000000000000000000 0000000000000110111100001100100000100000000000000000000000000000 100000000000001101111000011001000001
82.46154022216797 0100000001010100100111011000100111100000000000000000000000000000 0000000000000000000101011010001001000000000000000000000000000000 100000000000000000001010110100010010
78.86000061035156 0100000001010011101101110000101001000000000000000000000000000000 0000000000000111001010101000001110100000000000000000000000000000 100000000000001110010101010000011101
85.75609588623047 0100000001010101011100000110001111100000000000000000000000000000 0000000000000110110001110110100110100000000000000000000000000000 100000000000001101100011101101001101
80.33999633789063 0100000001010100000101011100001010000000000000000000000000000000 0000000000000001011001011010000101100000000000000000000000000000 100000000000000010110010110100001011
77.66666412353516 0100000001010011011010101010101010100000000000000000000000000000 0000000000000111011111110110100000100000000000000000000000000000 100000000000001110111111101101000001
87.82353210449219 0100000001010101111101001011010011000000000000000000000000000000 0000000000000110100111100001111001100000000000000000000000000000 100000000000001101001111000011110011
70.93478393554688 0100000001010001101110111101001110000000000000000000000000000000 0000000000000100010011110110011101000000000000000000000000000000 100000000000001000100111101100111010
87.77083587646484 0100000001010101111100010101010101100000000000000000000000000000 0000000000000100010010101000011011100000000000000000000000000000 100000000000001000100101010000110111
80.75 0100000001010100001100000000000000000000000000000000000000000000 0000000000000001110000010101010101100000000000000000000000000000 100000000000000011100000101010101011
76.04255676269531 0100000001010011000000101011100101000000000000000000000000000000 0000000000000111001100101011100101000000000000000000000000000000 100000000000001110011001010111001010
80.05000305175781 0100000001010100000000110011001101000000000000000000000000000000 0000000000000111000000011000101000000000000000000000000000000000 100000000000001110000000110001010000
90.20454406738281 0100000001010110100011010001011101000000000000000000000000000000 0000000000000010100011100010010000000000000000000000000000000000 100000000000000101000111000100100000
82.25 0100000001010100100100000000000000000000000000000000000000000000 0000000000000010000111010001011101000000000000000000000000000000 100000000000000100001110100010111010
72.01786041259766 0100000001010010000000010010010010100000000000000000000000000000 0000000000000110100100010010010010100000000000000000000000000000 100000000000001101001000100100100101
76 0100000001010011000000000000000000000000000000000000000000000000 0000000000000001000000010010010010100000000000000000000000000000 100000000000000010000000100100100101
80.44000244140625 0100000001010100000111000010100100000000000000000000000000000000 0000000000000111000111000010100100000000000000000000000000000000 100000000000001110001110000101001000
85.78845977783203 0100000001010101011100100111011000100000000000000000000000000000 0000000000000001011011100101111100100000000000000000000000000000 100000000000000010110111001011111001
90.89473724365234 0100000001010110101110010100001101100000000000000000000000000000 0000000000000011110010110011010101000000000000000000000000000000 100000000000000111100101100110101010
91.60465240478516 0100000001010110111001101011001010100000000000000000000000000000 0000000000000000010111111111000111000000000000000000000000000000 100000000000000000101111111110001110
99.51851654052734 0100000001011000111000010010111101100000000000000000000000000000 0000000000001110000001111001110111000000000000000000000000000000 100000000000011100000011110011101110
В качестве простого исправления я добавил счётчик «сожаления», отслеживающий количество нулей в начале и конце, которые мы встретили в выдаваемых алгоритмом подпоследовательностях. Если эта сумма превзойдёт определённое пороговое значение, мы принудительно выполняем сброс окна. На практике достаточно хорошо срабатывает пороговое значение «максимального сожаления» (max regret), равное 100; оно существенно улучшает сжатие в некоторых последовательностях и лишь немного ухудшает сжатие в остальных. Вот, как выглядит сжатие той же временной последовательности с max regret = 100.
DECIMAL BITS IN XOR BITS OUT
0 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000
26.33333396911621 0100000000111010010101010101010101100000000000000000000000000000 0100000000111010010101010101010101100000000000000000000000000000 11000011000011000000001110100101010101010101011
42.69767379760742 0100000001000101010110010100110101100000000000000000000000000000 0000000001111111000011000001100000000000000000000000000000000000 100000000011111110000110000011000000
56.29090881347656 0100000001001100001001010011110010000000000000000000000000000000 0000000000001001011111000111000111100000000000000000000000000000 100000000000010010111110001110001111
70.9795913696289 0100000001010001101111101011000110100000000000000000000000000000 0000000000011101100110111000110100100000000000000000000000000000 100000000000111011001101110001101001
77.60713958740234 0100000001010011011001101101101101100000000000000000000000000000 0000000000000010110110000110101011000000000000000000000000000000 100000000000000101101100001101010110
73.88888549804688 0100000001010010011110001110001110000000000000000000000000000000 0000000000000001000111100011100011100000000000000000000000000000 100000000000000010001111000111000111
82.1276626586914 0100000001010100100010000010101110100000000000000000000000000000 0000000000000110111100001100100000100000000000000000000000000000 100000000000001101111000011001000001
82.46154022216797 0100000001010100100111011000100111100000000000000000000000000000 0000000000000000000101011010001001000000000000000000000000000000 100000000000000000001010110100010010
78.86000061035156 0100000001010011101101110000101001000000000000000000000000000000 0000000000000111001010101000001110100000000000000000000000000000 100000000000001110010101010000011101
85.75609588623047 0100000001010101011100000110001111100000000000000000000000000000 0000000000000110110001110110100110100000000000000000000000000000 11011010101011101100011101101001101
80.33999633789063 0100000001010100000101011100001010000000000000000000000000000000 0000000000000001011001011010000101100000000000000000000000000000 100010110010110100001011
77.66666412353516 0100000001010011011010101010101010100000000000000000000000000000 0000000000000111011111110110100000100000000000000000000000000000 101110111111101101000001
87.82353210449219 0100000001010101111101001011010011000000000000000000000000000000 0000000000000110100111100001111001100000000000000000000000000000 101101001111000011110011
70.93478393554688 0100000001010001101110111101001110000000000000000000000000000000 0000000000000100010011110110011101000000000000000000000000000000 101000100111101100111010
87.77083587646484 0100000001010101111100010101010101100000000000000000000000000000 0000000000000100010010101000011011100000000000000000000000000000 101000100101010000110111
80.75 0100000001010100001100000000000000000000000000000000000000000000 0000000000000001110000010101010101100000000000000000000000000000 100011100000101010101011
76.04255676269531 0100000001010011000000101011100101000000000000000000000000000000 0000000000000111001100101011100101000000000000000000000000000000 101110011001010111001010
80.05000305175781 0100000001010100000000110011001101000000000000000000000000000000 0000000000000111000000011000101000000000000000000000000000000000 101110000000110001010000
90.20454406738281 0100000001010110100011010001011101000000000000000000000000000000 0000000000000010100011100010010000000000000000000000000000000000 100101000111000100100000
82.25 0100000001010100100100000000000000000000000000000000000000000000 0000000000000010000111010001011101000000000000000000000000000000 100100001110100010111010
72.01786041259766 0100000001010010000000010010010010100000000000000000000000000000 0000000000000110100100010010010010100000000000000000000000000000 101101001000100100100101
76 0100000001010011000000000000000000000000000000000000000000000000 0000000000000001000000010010010010100000000000000000000000000000 100010000000100100100101
80.44000244140625 0100000001010100000111000010100100000000000000000000000000000000 0000000000000111000111000010100100000000000000000000000000000000 101110001110000101001000
85.78845977783203 0100000001010101011100100111011000100000000000000000000000000000 0000000000000001011011100101111100100000000000000000000000000000 100010110111001011111001
90.89473724365234 0100000001010110101110010100001101100000000000000000000000000000 0000000000000011110010110011010101000000000000000000000000000000 100111100101100110101010
91.60465240478516 0100000001010110111001101011001010100000000000000000000000000000 0000000000000000010111111111000111000000000000000000000000000000 100000101111111110001110
99.51851654052734 0100000001011000111000010010111101100000000000000000000000000000 0000000000001110000001111001110111000000000000000000000000000000 11011000101011110000001111001110111
86.34782409667969 0100000001010101100101100100001011000000000000000000000000000000 0000000000001101011101110110110110100000000000000000000000000000 110110001011011010111011101101101101
81.20833587646484 0100000001010100010011010101010101100000000000000000000000000000 0000000000000001110110110001011110100000000000000000000000000000 1000011101101100010111101
88.29729461669922 0100000001010110000100110000011011100000000000000000000000000000 0000000000000010010111100101001110000000000000000000000000000000 1000100101111001010011100
92.60416412353516 0100000001010111001001101010101010100000000000000000000000000000 0000000000000001001101011010110001000000000000000000000000000000 1000010011010110101100010
Я особо не размышлял об этом, так что высока вероятность, что есть более качественные и логически обоснованные эвристики (примечание: комментатор EdSchouten на Hacker News придумал хороший подход). Интересно было бы и найти наиболее эффективный алгоритм для поиска оптимальных моментов сброса окна и его нового интервала при анализе всей временной последовательности. Это было бы полезно в случаях, когда вам гораздо важнее минимизация размера в сжатом виде, а не скорость сжатия (в распаковке может использоваться тот же алгоритм с почти той же скоростью, что и при сжатии с помощью эвристики).
Производительность
Моя наивная реализация достигает на i7-10875H производительности более чем 100 МиБ/с при кодировании и 200 МиБ/с при декодировании случайных чисел с плавающей запятой (при использовании более сжимаемых данных кодирование достигает скорости более 200 МиБ/с, декодирование — более 350 МиБ/с). Ничего потрясающего, но вполне прилично для столь малого объёма кода, и всё равно гораздо быстрее, чем большинство сетевых подключений (в основном я использую алгоритм для снижения объёма передаваемых по сети данных). Существует SIMD-реализация на Rust, достигающая скорости в несколько ГБ/с, однако она, похоже, использует нестабильные фичи, требующие обновления для совместимости с более новыми версиями Rust.
При профилировании наивной реализации выяснилось, что больше всего времени она тратит на методы
BitWriter
/BitReader
.Заменив их на bitbuffer и добавив ещё несколько небольших оптимизаций, мы получаем скорость кодирования 370 МиБ/с, декодирования — 1 ГиБ/с. Я попробовал и bitter; ранний (поломанный) прототип, некорректно обрабатывающий операции чтения с более чем 56 битами, достиг более чем 2 ГиБ/с при декодировании даже в автоматическом режиме; а другая версия (вероятно, корректная) всё равно оказалась примерно на 30% быстрее, чем моя изначальная реализация bitbuffer (больше 1 ГиБ/с).
Дополнительные примеры
Ниже вашему вниманию представлены примеры различных временных последовательностей. При сжатии всех последовательностей применялось стандартное пороговое значение max regret = 100. Можно воссоздать результаты, выполнив
cargo run --example gorilla_time -- --verbose
в 4cfbda210. Все временные последовательности суммарно содержат 246 значений, в примерах показано только несколько первых значений.Числа с плавающей запятой, имеющие мало значащих битов
Значения в этой временной последовательности являются средними значениями, вычисленными делением небольшого целого числа на степень двойки, что даёт очень малое количество значащих битов (коэффициент сжатия 5,68).
DECIMAL BITS IN XOR BITS OUT
0.061279296875 0011111110101111011000000000000000000000000000000000000000000000 0011111110101111011000000000000000000000000000000000000000000000
0.060546875 0011111110101111000000000000000000000000000000000000000000000000 0000000000000000011000000000000000000000000000000000000000000000 111000100000111
0.072265625 0011111110110010100000000000000000000000000000000000000000000000 0000000000011101100000000000000000000000000000000000000000000000 1101011000101111011
0.060791015625 0011111110101111001000000000000000000000000000000000000000000000 0000000000011101101000000000000000000000000000000000000000000000 110101100011111101101
0.06103515625 0011111110101111010000000000000000000000000000000000000000000000 0000000000000000011000000000000000000000000000000000000000000000 1000000011
0.066650390625 0011111110110001000100000000000000000000000000000000000000000000 0000000000011110010100000000000000000000000000000000000000000000 1101011001000111100101
0.056884765625 0011111110101101001000000000000000000000000000000000000000000000 0000000000011100001100000000000000000000000000000000000000000000 10111000011
0.053955078125 0011111110101011101000000000000000000000000000000000000000000000 0000000000000110100000000000000000000000000000000000000000000000 10001101000
0.051513671875 0011111110101010011000000000000000000000000000000000000000000000 0000000000000001110000000000000000000000000000000000000000000000 10000011100
0.062744140625 0011111110110000000100000000000000000000000000000000000000000000 0000000000011010011100000000000000000000000000000000000000000000 10110100111
0.0556640625 0011111110101100100000000000000000000000000000000000000000000000 0000000000011100100100000000000000000000000000000000000000000000 10111001001
0.063232421875 0011111110110000001100000000000000000000000000000000000000000000 0000000000011100101100000000000000000000000000000000000000000000 10111001011
0.07373046875 0011111110110010111000000000000000000000000000000000000000000000 0000000000000010110100000000000000000000000000000000000000000000 10000101101
0.060791015625 0011111110101111001000000000000000000000000000000000000000000000 0000000000011101110000000000000000000000000000000000000000000000 10111011100
0.062744140625 0011111110110000000100000000000000000000000000000000000000000000 0000000000011111001100000000000000000000000000000000000000000000 10111110011
0.06298828125 0011111110110000001000000000000000000000000000000000000000000000 0000000000000000001100000000000000000000000000000000000000000000 10000000011
0.082275390625 0011111110110101000100000000000000000000000000000000000000000000 0000000000000101001100000000000000000000000000000000000000000000 10001010011
0.069580078125 0011111110110001110100000000000000000000000000000000000000000000 0000000000000100110000000000000000000000000000000000000000000000 10001001100
0.070556640625 0011111110110010000100000000000000000000000000000000000000000000 0000000000000011110000000000000000000000000000000000000000000000 10000111100
0.064208984375 0011111110110000011100000000000000000000000000000000000000000000 0000000000000010011000000000000000000000000000000000000000000000 10000100110
0.059814453125 0011111110101110101000000000000000000000000000000000000000000000 0000000000011110110100000000000000000000000000000000000000000000 10111101101
0.052490234375 0011111110101010111000000000000000000000000000000000000000000000 0000000000000100010000000000000000000000000000000000000000000000 10001000100
0.04345703125 0011111110100110010000000000000000000000000000000000000000000000 0000000000001100101000000000000000000000000000000000000000000000 10011001010
0.052978515625 0011111110101011001000000000000000000000000000000000000000000000 0000000000001101011000000000000000000000000000000000000000000000 10011010110
0.0546875 0011111110101100000000000000000000000000000000000000000000000000 0000000000000111001000000000000000000000000000000000000000000000 10001110010
Целые числа с высокой степенью избыточности
Значения в этой последовательности показывают среднюю производительность, потому что программа начинает с округлённых до целых чисел. Из-за этого временная последовательность в основном сходится с течением времени к единственному значению (коэффициент сжатия 13,5).
DECIMAL BITS IN XOR BITS OUT
1682 0100000010011010010010000000000000000000000000000000000000000000 0100000010011010010010000000000000000000000000000000000000000000
1617 0100000010011001010001000000000000000000000000000000000000000000 0000000000000011000011000000000000000000000000000000000000000000 110111000011111000011
1580 0100000010011000101100000000000000000000000000000000000000000000 0000000000000001111101000000000000000000000000000000000000000000 1001111101
1546 0100000010011000001010000000000000000000000000000000000000000000 0000000000000000100110000000000000000000000000000000000000000000 1000100110
1518 0100000010010111101110000000000000000000000000000000000000000000 0000000000001111100100000000000000000000000000000000000000000000 110110000011111111001
1494 0100000010010111010110000000000000000000000000000000000000000000 0000000000000000111000000000000000000000000000000000000000000000 1000001110
1487 0100000010010111001111000000000000000000000000000000000000000000 0000000000000000011001000000000000000000000000000000000000000000 111000100010011001
1488 0100000010010111010000000000000000000000000000000000000000000000 0000000000000000011111000000000000000000000000000000000000000000 1011111
1478 0100000010010111000110000000000000000000000000000000000000000000 0000000000000000010110000000000000000000000000000000000000000000 1010110
1470 0100000010010110111110000000000000000000000000000000000000000000 0000000000000001111000000000000000000000000000000000000000000000 11011110000111111
1471 0100000010010110111111000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 11101010000001
1469 0100000010010110111101000000000000000000000000000000000000000000 0000000000000000000010000000000000000000000000000000000000000000 11101000000001
1464 0100000010010110111000000000000000000000000000000000000000000000 0000000000000000000101000000000000000000000000000000000000000000 1110011000010101
1461 0100000010010110110101000000000000000000000000000000000000000000 0000000000000000001101000000000000000000000000000000000000000000 11100100000111101
1456 0100000010010110110000000000000000000000000000000000000000000000 0000000000000000000101000000000000000000000000000000000000000000 100101
1447 0100000010010110100111000000000000000000000000000000000000000000 0000000000000000010111000000000000000000000000000000000000000000 111000100010010111
1447 0100000010010110100111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1442 0100000010010110100010000000000000000000000000000000000000000000 0000000000000000000101000000000000000000000000000000000000000000 1000101
1440 0100000010010110100000000000000000000000000000000000000000000000 0000000000000000000010000000000000000000000000000000000000000000 1000010
1437 0100000010010110011101000000000000000000000000000000000000000000 0000000000000000111101000000000000000000000000000000000000000000 1110000000101111101
1380 0100000010010101100100000000000000000000000000000000000000000000 0000000000000011111001000000000000000000000000000000000000000000 110111000011111111001
1382 0100000010010101100110000000000000000000000000000000000000000000 0000000000000000000010000000000000000000000000000000000000000000 1000000010
1384 0100000010010101101000000000000000000000000000000000000000000000 0000000000000000001110000000000000000000000000000000000000000000 1000001110
1385 0100000010010101101001000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000000001
1385 0100000010010101101001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1384 0100000010010101101000000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000000001
1387 0100000010010101101011000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 1000000011
1390 0100000010010101101110000000000000000000000000000000000000000000 0000000000000000000101000000000000000000000000000000000000000000 1000000101
1395 0100000010010101110011000000000000000000000000000000000000000000 0000000000000000011101000000000000000000000000000000000000000000 1000011101
1398 0100000010010101110110000000000000000000000000000000000000000000 0000000000000000000101000000000000000000000000000000000000000000 1000000101
1401 0100000010010101111001000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 1000001111
1402 0100000010010101111010000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 1000000011
1405 0100000010010101111101000000000000000000000000000000000000000000 0000000000000000000111000000000000000000000000000000000000000000 1000000111
1408 0100000010010110000000000000000000000000000000000000000000000000 0000000000000011111101000000000000000000000000000000000000000000 1011111101
1411 0100000010010110000011000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 1000000011
1412 0100000010010110000100000000000000000000000000000000000000000000 0000000000000000000111000000000000000000000000000000000000000000 1000000111
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000010000000000000000000000000000000000000000000 1000000010
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000000001
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000001110000000000000000000000000000000000000000000 1000001110
1420 0100000010010110001100000000000000000000000000000000000000000000 0000000000000000000101000000000000000000000000000000000000000000 1000000101
1421 0100000010010110001101000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000000001
1421 0100000010010110001101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1421 0100000010010110001101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1423 0100000010010110001111000000000000000000000000000000000000000000 0000000000000000000010000000000000000000000000000000000000000000 11101000000001
1425 0100000010010110010001000000000000000000000000000000000000000000 0000000000000000011110000000000000000000000000000000000000000000 11100010000111111
1425 0100000010010110010001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1427 0100000010010110010011000000000000000000000000000000000000000000 0000000000000000000010000000000000000000000000000000000000000000 100001
1427 0100000010010110010011000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000111000000000000000000000000000000000000000000 1110011000010111
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 10001
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 10011
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 10011
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 10011
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 10011
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 10001
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 10001
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 10011
1431 0100000010010110010111000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 10001
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 10001
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1431 0100000010010110010111000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 10001
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 11100100000111111
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1431 0100000010010110010111000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 101111
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 101111
1431 0100000010010110010111000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 101111
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 101111
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1431 0100000010010110010111000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 101111
1431 0100000010010110010111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 101111
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 100001
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 100001
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 100001
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1433 0100000010010110011001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 100001
1432 0100000010010110011000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1431 0100000010010110010111000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 101111
1431 0100000010010110010111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1431 0100000010010110010111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 100001
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1430 0100000010010110010110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000010000000000000000000000000000000000000000000 100010
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 100001
1429 0100000010010110010101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 100001
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1428 0100000010010110010100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1427 0100000010010110010011000000000000000000000000000000000000000000 0000000000000000000111000000000000000000000000000000000000000000 100111
1427 0100000010010110010011000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1427 0100000010010110010011000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1426 0100000010010110010010000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 100001
1426 0100000010010110010010000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1425 0100000010010110010001000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 100011
1424 0100000010010110010000000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 100001
1423 0100000010010110001111000000000000000000000000000000000000000000 0000000000000000011111000000000000000000000000000000000000000000 111000100010011111
1423 0100000010010110001111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1423 0100000010010110001111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1421 0100000010010110001101000000000000000000000000000000000000000000 0000000000000000000010000000000000000000000000000000000000000000 1000010
1421 0100000010010110001101000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1420 0100000010010110001100000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000001
1420 0100000010010110001100000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1419 0100000010010110001011000000000000000000000000000000000000000000 0000000000000000000111000000000000000000000000000000000000000000 1000111
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000001
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 1000011
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000001
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 1001111
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 1001111
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 1001111
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000001
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000001
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000001
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1414 0100000010010110000110000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000001
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 1001111
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000001
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 1000011
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 1000011
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 1000011
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 1000011
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 1000011
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1418 0100000010010110001010000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000011000000000000000000000000000000000000000000 1000011
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1417 0100000010010110001001000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000001000000000000000000000000000000000000000000 1000001
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 1001111
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 1001111
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1416 0100000010010110001000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000001111000000000000000000000000000000000000000000 1001111
1415 0100000010010110000111000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
Инкрементно увеличивающиеся целые числа
Целые числа, с каждым шагом времени увеличивающиеся на 1. Было бы гораздо эффективнее рассматривать их как integer, а не float, и применять сжатие дельты дельт, но алгоритму XOR всё равно удаётся уменьшить данные всего до чуть более одного байта на элемент данных (коэффициент сжатия 6,98).
DECIMAL BITS IN XOR BITS OUT
1 0011111111110000000000000000000000000000000000000000000000000000 0011111111110000000000000000000000000000000000000000000000000000
2 0100000000000000000000000000000000000000000000000000000000000000 0111111111110000000000000000000000000000000000000000000000000000 110000100101011111111111
3 0100000000001000000000000000000000000000000000000000000000000000 0000000000001000000000000000000000000000000000000000000000000000 11011000000001
4 0100000000010000000000000000000000000000000000000000000000000000 0000000000011000000000000000000000000000000000000000000000000000 110101100000111
5 0100000000010100000000000000000000000000000000000000000000000000 0000000000000100000000000000000000000000000000000000000000000000 11011010000001
6 0100000000011000000000000000000000000000000000000000000000000000 0000000000001100000000000000000000000000000000000000000000000000 110110000000111
7 0100000000011100000000000000000000000000000000000000000000000000 0000000000000100000000000000000000000000000000000000000000000000 1001
8 0100000000100000000000000000000000000000000000000000000000000000 0000000000111100000000000000000000000000000000000000000000000000 11010100000111111
9 0100000000100010000000000000000000000000000000000000000000000000 0000000000000010000000000000000000000000000000000000000000000000 11011100000001
10 0100000000100100000000000000000000000000000000000000000000000000 0000000000000110000000000000000000000000000000000000000000000000 110110100000111
11 0100000000100110000000000000000000000000000000000000000000000000 0000000000000010000000000000000000000000000000000000000000000000 1001
12 0100000000101000000000000000000000000000000000000000000000000000 0000000000001110000000000000000000000000000000000000000000000000 1101100000010111
13 0100000000101010000000000000000000000000000000000000000000000000 0000000000000010000000000000000000000000000000000000000000000000 10001
14 0100000000101100000000000000000000000000000000000000000000000000 0000000000000110000000000000000000000000000000000000000000000000 10011
15 0100000000101110000000000000000000000000000000000000000000000000 0000000000000010000000000000000000000000000000000000000000000000 10001
16 0100000000110000000000000000000000000000000000000000000000000000 0000000000011110000000000000000000000000000000000000000000000000 11010110000111111
17 0100000000110001000000000000000000000000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 11011110000001
18 0100000000110010000000000000000000000000000000000000000000000000 0000000000000011000000000000000000000000000000000000000000000000 110111000000111
19 0100000000110011000000000000000000000000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 1001
20 0100000000110100000000000000000000000000000000000000000000000000 0000000000000111000000000000000000000000000000000000000000000000 1101101000010111
21 0100000000110101000000000000000000000000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 10001
22 0100000000110110000000000000000000000000000000000000000000000000 0000000000000011000000000000000000000000000000000000000000000000 10011
23 0100000000110111000000000000000000000000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 10001
24 0100000000111000000000000000000000000000000000000000000000000000 0000000000001111000000000000000000000000000000000000000000000000 11011000000111111
25 0100000000111001000000000000000000000000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 100001
26 0100000000111010000000000000000000000000000000000000000000000000 0000000000000011000000000000000000000000000000000000000000000000 100011
27 0100000000111011000000000000000000000000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 100001
28 0100000000111100000000000000000000000000000000000000000000000000 0000000000000111000000000000000000000000000000000000000000000000 100111
29 0100000000111101000000000000000000000000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 100001
30 0100000000111110000000000000000000000000000000000000000000000000 0000000000000011000000000000000000000000000000000000000000000000 100011
31 0100000000111111000000000000000000000000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 100001
32 0100000001000000000000000000000000000000000000000000000000000000 0000000001111111000000000000000000000000000000000000000000000000 11010010001101111111
Метки времени Unix
Это последовательность меток времени Unix с точностью примерно в миллисекунду. Наше решение использовать всего 5 битов для хранения нулей в начале подводит нас, потому что ограничивает нас максимум 2^5 – 1 = 31 нулями в начале. Кроме того, эту последовательность лучше хранить как integer со сжатием дельты дельт (коэффициент сжатия 1,80).
DECIMAL BITS IN XOR BITS OUT
1652566453.6112177 0100000111011000101000000000101001101101011001110001111000110001 0100000111011000101000000000101001101101011001110001111000110001
1652566455.1489727 0100000111011000101000000000101001101101110010011000100011000101 0000000000000000000000000000000000000000101011101001011011110100 11111110111100000000001010111010010110111101
1652566456.750367 0100000111011000101000000000101001101110001100000000011000000011 0000000000000000000000000000000000000011111110011000111011000110 111111101111100000001111111001100011101100011
1652566458.3119035 0100000111011000101000000000101001101110100100111111011000111010 0000000000000000000000000000000000000000101000111111000000111001 1111111100000000000000101000111111000000111001
1652566459.9219267 0100000111011000101000000000101001101110111110110000000011011001 0000000000000000000000000000000000000000011010001111011011100011 10000000000011010001111011011100011
1652566461.561778 0100000111011000101000000000101001101111011000111111010000101100 0000000000000000000000000000000000000001100110001111010011110101 10000000001100110001111010011110101
1652566463.257791 0100000111011000101000000000101001101111110100000111111110100110 0000000000000000000000000000000000000000101100111000101110001010 10000000000101100111000101110001010
1652566464.8399875 0100000111011000101000000000101001110000001101011100001001011011 0000000000000000000000000000000000011111111001011011110111111101 10000011111111001011011110111111101
1652566466.3860452 0100000111011000101000000000101001110000100110001011010011110111 0000000000000000000000000000000000000000101011010111011010101100 10000000000101011010111011010101100
1652566467.9558356 0100000111011000101000000000101001110000111111010010110001101001 0000000000000000000000000000000000000000011001011001100010011110 10000000000011001011001100010011110
1652566469.5445094 0100000111011000101000000000101001110001011000101101100100111110 0000000000000000000000000000000000000001100111111111010101010111 10000000001100111111111010101010111
1652566471.164418 0100000111011000101000000000101001110001110010101000010111010011 0000000000000000000000000000000000000000101010000101110011101101 10000000000101010000101110011101101
1652566472.7336688 0100000111011000101000000000101001110010001011101111010001101110 0000000000000000000000000000000000000011111001000111000110111101 10000000011111001000111000110111101
1652566474.2879102 0100000111011000101000000000101001110010100100100110110100011111 0000000000000000000000000000000000000000101111001001100101110001 10000000000101111001001100101110001
1652566475.8257375 0100000111011000101000000000101001110010111101001101100011100010 0000000000000000000000000000000000000000011001101011010111111101 10000000000011001101011010111111101
1652566477.406342 0100000111011000101000000000101001110011010110100000000110000010 0000000000000000000000000000000000000001101011101101100101100000 10000000001101011101101100101100000
1652566478.9654105 0100000111011000101000000000101001110011101111011100100101001001 0000000000000000000000000000000000000000111001111100100011001011 10000000000111001111100100011001011
1652566480.4778848 0100000111011000101000000000101001110100000111101001010110101010 0000000000000000000000000000000000000111101000110101110011100011 10000000111101000110101110011100011
1652566482.0515509 0100000111011000101000000000101001110100100000110100110010011100 0000000000000000000000000000000000000000100111011101100100110110 10000000000100111011101100100110110
1652566483.541527 0100000111011000101000000000101001110100111000101010100001100001 0000000000000000000000000000000000000000011000011110010011111101 10000000000011000011110010011111101
1652566485.121764 0100000111011000101000000000101001110101010001111100101011111011 0000000000000000000000000000000000000001101001010110001010011010 10000000001101001010110001010011010
1652566486.6397657 0100000111011000101000000000101001110101101010001111000111101100 0000000000000000000000000000000000000000111011110011101100010111 10000000000111011110011101100010111
1652566488.2642183 0100000111011000101000000000101001110110000100001110100011110100 0000000000000000000000000000000000000011101110000001100100011000 10000000011101110000001100100011000
1652566489.7945278 0100000111011000101000000000101001110110011100101101100110001011 0000000000000000000000000000000000000000011000100011000101111111 10000000000011000100011000101111111
1652566491.4354746 0100000111011000101000000000101001110110110110111101111011010001 0000000000000000000000000000000000000000101010010000011101011010 10000000000101010010000011101011010
1652566493.0550997 0100000111011000101000000000101001110111010000111000011011000001 0000000000000000000000000000000000000001100110000101100000010000 10000000001100110000101100000010000
1652566494.6093755 0100000111011000101000000000101001110111101001110000000000000010 0000000000000000000000000000000000000000111001001000011011000011 10000000000111001001000011011000011
Шумные числа одинарной точности с плавающей запятой
Это довольно типичная временная последовательность с плавающей запятой, фиксирующая градиентную норму на каждой итерации прогона машинного обучения. Основная часть значащих битов является несжимаемым шумом. Но мы всё равно получаем какое-то сжатие, потому что биты экспоненты не меняются, а число использует одинарную точность и не задействует самые младшие 29 битов мантиссы (коэффициент сжатия 2,37).
DECIMAL BITS IN XOR BITS OUT
0.012796709313988686 0011111110001010001101010010100101000000000000000000000000000000 0011111110001010001101010010100101000000000000000000000000000000
0.3509874641895294 0011111111010110011101101001010000100000000000000000000000000000 0000000001011100010000111011110101100000000000000000000000000000 110100101100110111000100001110111101011
0.37030330300331116 0011111111010111101100110000110010100000000000000000000000000000 0000000000000001110001011001100010000000000000000000000000000000 1000000011100010110011000100
0.3147137761116028 0011111111010100001001000100010101000000000000000000000000000000 0000000000000011100101110100100111100000000000000000000000000000 1000000111001011101001001111
0.3929761052131653 0011111111011001001001101000010101000000000000000000000000000000 0000000000001101000000101100000000000000000000000000000000000000 1000011010000001011000000000
0.40006211400032043 0011111111011001100110101001111000100000000000000000000000000000 0000000000000000101111000001101101100000000000000000000000000000 1000000001011110000011011011
0.5028038024902344 0011111111100000000101101111100000000000000000000000000000000000 0000000000111001100011000110011000100000000000000000000000000000 1001110011000110001100110001
0.4919178783893585 0011111111011111011110111001010100100000000000000000000000000000 0000000000111111011011010110110100100000000000000000000000000000 1001111110110110101101101001
0.4074249267578125 0011111111011010000100110100000000000000000000000000000000000000 0000000000000101011010001101010100100000000000000000000000000000 1000001010110100011010101001
0.45758020877838135 0011111111011101010010001111111010000000000000000000000000000000 0000000000000111010110111011111010000000000000000000000000000000 1000001110101101110111110100
0.40965843200683594 0011111111011010001101111101100000000000000000000000000000000000 0000000000000111011111110010011010000000000000000000000000000000 1000001110111111100100110100
0.4113210439682007 0011111111011010010100110001010110000000000000000000000000000000 0000000000000000011001001100110110000000000000000000000000000000 1000000000110010011001101100
0.3712143003940582 0011111111010111110000011111100110100000000000000000000000000000 0000000000001101100100101110110000100000000000000000000000000000 1000011011001001011101100001
0.4784809947013855 0011111111011110100111110110111011000000000000000000000000000000 0000000000001001010111101001011101100000000000000000000000000000 1000010010101111010010111011
0.49545547366142273 0011111111011111101101011000101011100000000000000000000000000000 0000000000000001001010101110010000100000000000000000000000000000 1000000010010101011100100001
0.4399729073047638 0011111111011100001010001000010000100000000000000000000000000000 0000000000000011100111010000111011000000000000000000000000000000 1000000111001110100001110110
0.45343348383903503 0011111111011101000001010000110111100000000000000000000000000000 0000000000000001001011011000100111000000000000000000000000000000 1000000010010110110001001110
0.5084419846534729 0011111111100000010001010010100000100000000000000000000000000000 0000000000111101010000000010010111000000000000000000000000000000 1001111010100000000100101110
0.6009485125541687 0011111111100011001110101111100001100000000000000000000000000000 0000000000000011011111111101000001000000000000000000000000000000 1000000110111111111010000010
0.48541179299354553 0011111111011111000100001111110010100000000000000000000000000000 0000000000111100001010100000010011000000000000000000000000000000 1001111000010101000000100110
0.4059547781944275 0011111111011001111110110010100111000000000000000000000000000000 0000000000000110111010111101010101100000000000000000000000000000 1000001101110101111010101011
0.4256344139575958 0011111111011011001111011001100000100000000000000000000000000000 0000000000000010110001101011000111100000000000000000000000000000 1000000101100011010110001111
0.4449596107006073 0011111111011100011110100011011111100000000000000000000000000000 0000000000000111010001111010111111000000000000000000000000000000 1101101010100111010001111010111111
0.5190045833587646 0011111111100000100110111010111110000000000000000000000000000000 0000000000111100111000011001100001100000000000000000000000000000 11010100110001111001110000110011000011
0.6285673379898071 0011111111100100000111010011100101000000000000000000000000000000 0000000000000100100001101001011011000000000000000000000000000000 100001001000011010010110110
0.5742775797843933 0011111111100010011000000111101101100000000000000000000000000000 0000000000000110011111010100001000100000000000000000000000000000 100001100111110101000010001
0.5105176568031311 0011111111100000010101100010100100100000000000000000000000000000 0000000000000010001101100101001001000000000000000000000000000000 100000100011011001010010010
0.6416354179382324 0011111111100100100010000100011100000000000000000000000000000000 0000000000000100110111100110111000100000000000000000000000000000 100001001101111001101110001
Мы можем сэкономить ещё немного места, если изначально будем считать значения числами одинарной точности с плавающей запятой, потому что в этом случае для хранения длины ненулевой подпоследовательности нам понадобится на один бит меньше. В данном случае это почти ничего не меняет, потому что поле длины сохраняется редко (коэффициент сжатия 2,41).
DECIMAL BITS IN XOR BITS OUT
0.012796709 00111100010100011010100101001010 00111100010100011010100101001010
0.35098746 00111110101100111011010010100001 00000010111000100001110111101011 11001101100110111000100001110111101011
0.3703033 00111110101111011001100001100101 00000000000011100010110011000100 1000000011100010110011000100
0.31471378 00111110101000010010001000101010 00000000000111001011101001001111 1000000111001011101001001111
0.3929761 00111110110010010011010000101010 00000000011010000001011000000000 1000011010000001011000000000
0.4000621 00111110110011001101010011110001 00000000000001011110000011011011 1000000001011110000011011011
0.5028038 00111111000000001011011111000000 00000001110011000110001100110001 1001110011000110001100110001
0.49191788 00111110111110111101110010101001 00000001111110110110101101101001 1001111110110110101101101001
0.40742493 00111110110100001001101000000000 00000000001010110100011010101001 1000001010110100011010101001
0.4575802 00111110111010100100011111110100 00000000001110101101110111110100 1000001110101101110111110100
0.40965843 00111110110100011011111011000000 00000000001110111111100100110100 1000001110111111100100110100
0.41132104 00111110110100101001100010101100 00000000000000110010011001101100 1000000000110010011001101100
0.3712143 00111110101111100000111111001101 00000000011011001001011101100001 1000011011001001011101100001
0.478481 00111110111101001111101101110110 00000000010010101111010010111011 1000010010101111010010111011
0.49545547 00111110111111011010110001010111 00000000000010010101011100100001 1000000010010101011100100001
0.4399729 00111110111000010100010000100001 00000000000111001110100001110110 1000000111001110100001110110
0.45343348 00111110111010000010100001101111 00000000000010010110110001001110 1000000010010110110001001110
0.508442 00111111000000100010100101000001 00000001111010100000000100101110 1001111010100000000100101110
0.6009485 00111111000110011101011111000011 00000000000110111111111010000010 1000000110111111111010000010
0.4854118 00111110111110001000011111100101 00000001111000010101000000100110 1001111000010101000000100110
0.40595478 00111110110011111101100101001110 00000000001101110101111010101011 1000001101110101111010101011
0.4256344 00111110110110011110110011000001 00000000000101100011010110001111 1000000101100011010110001111
0.4449596 00111110111000111101000110111111 00000000001110100011110101111110 110101010100111010001111010111111
0.5190046 00111111000001001101110101111100 00000001111001110000110011000011 1100111110001111001110000110011000011
0.62856734 00111111001000001110100111001010 00000000001001000011010010110110 100001001000011010010110110
0.5742776 00111111000100110000001111011011 00000000001100111110101000010001 100001100111110101000010001
0.51051766 00111111000000101011000101001001 00000000000100011011001010010010 100000100011011001010010010
0.6416354 00111111001001000100001000111000 00000000001001101111001101110001 100001001101111001101110001
0.51030874 00111111000000101010001110011000 00000000001001101110000110100000 100001001101110000110100000
0.64693856 00111111001001011001110111000100 00000000001001110011111001011100 100001001110011111001011100
0.51288015 00111111000000110100110000011101 00000000001001101101000111011001 100001001101101000111011001
0.6287092 00111111001000001111001100010110 00000000001000111011111100001011 100001000111011111100001011
0.65078825 00111111001001101001101000001111 00000000000001100110100100011001 100000001100110100100011001
0.5141415 00111111000000111001111011000111 00000000001001010000010011001000 100001001010000010011001000
Если мы готовы выполнять сжатие с потерями, то можем добиться существенного улучшения сжатия благодаря снижению размера мантиссы до 4 битов (коэффициент сжатия 8,48).
MASK: 1111111111111111000000000000000000000000000000000000000000000000
DECIMAL BITS IN XOR BITS OUT
0.012796709313988686 0011111110001010001101010010100101000000000000000000000000000000 0011111110001010001101010010100101000000000000000000000000000000
0.3509874641895294 0011111111010110011101101001010000100000000000000000000000000000 0000000001011100000000000000000000000000000000000000000000000000 110100100010010111
0.37030330300331116 0011111111010111101100110000110010100000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 11011110000001
0.3147137761116028 0011111111010100001001000100010101000000000000000000000000000000 0000000000000011000000000000000000000000000000000000000000000000 110111000000111
0.3929761052131653 0011111111011001001001101000010101000000000000000000000000000000 0000000000001101000000000000000000000000000000000000000000000000 11011000000111101
0.40006211400032043 0011111111011001100110101001111000100000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
0.5028038024902344 0011111111100000000101101111100000000000000000000000000000000000 0000000000111001000000000000000000000000000000000000000000000000 1101010000101111001
0.4919178783893585 0011111111011111011110111001010100100000000000000000000000000000 0000000000111111000000000000000000000000000000000000000000000000 10111111
0.4074249267578125 0011111111011010000100110100000000000000000000000000000000000000 0000000000000101000000000000000000000000000000000000000000000000 10000101
0.45758020877838135 0011111111011101010010001111111010000000000000000000000000000000 0000000000000111000000000000000000000000000000000000000000000000 10000111
0.40965843200683594 0011111111011010001101111101100000000000000000000000000000000000 0000000000000111000000000000000000000000000000000000000000000000 10000111
0.4113210439682007 0011111111011010010100110001010110000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
0.3712143003940582 0011111111010111110000011111100110100000000000000000000000000000 0000000000001101000000000000000000000000000000000000000000000000 10001101
0.4784809947013855 0011111111011110100111110110111011000000000000000000000000000000 0000000000001001000000000000000000000000000000000000000000000000 10001001
0.49545547366142273 0011111111011111101101011000101011100000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 10000001
0.4399729073047638 0011111111011100001010001000010000100000000000000000000000000000 0000000000000011000000000000000000000000000000000000000000000000 10000011
0.45343348383903503 0011111111011101000001010000110111100000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 10000001
0.5084419846534729 0011111111100000010001010010100000100000000000000000000000000000 0000000000111101000000000000000000000000000000000000000000000000 10111101
0.6009485125541687 0011111111100011001110101111100001100000000000000000000000000000 0000000000000011000000000000000000000000000000000000000000000000 10000011
0.48541179299354553 0011111111011111000100001111110010100000000000000000000000000000 0000000000111100000000000000000000000000000000000000000000000000 10111100
0.4059547781944275 0011111111011001111110110010100111000000000000000000000000000000 0000000000000110000000000000000000000000000000000000000000000000 10000110
0.4256344139575958 0011111111011011001111011001100000100000000000000000000000000000 0000000000000010000000000000000000000000000000000000000000000000 10000010
0.4449596107006073 0011111111011100011110100011011111100000000000000000000000000000 0000000000000111000000000000000000000000000000000000000000000000 10000111
0.5190045833587646 0011111111100000100110111010111110000000000000000000000000000000 0000000000111100000000000000000000000000000000000000000000000000 10111100
0.6285673379898071 0011111111100100000111010011100101000000000000000000000000000000 0000000000000100000000000000000000000000000000000000000000000000 10000100
0.5742775797843933 0011111111100010011000000111101101100000000000000000000000000000 0000000000000110000000000000000000000000000000000000000000000000 10000110
0.5105176568031311 0011111111100000010101100010100100100000000000000000000000000000 0000000000000010000000000000000000000000000000000000000000000000 10000010
0.6416354179382324 0011111111100100100010000100011100000000000000000000000000000000 0000000000000100000000000000000000000000000000000000000000000000 10000100
0.5103087425231934 0011111111100000010101000111001100000000000000000000000000000000 0000000000000100000000000000000000000000000000000000000000000000 10000100
0.6469385623931885 0011111111100100101100111011100010000000000000000000000000000000 0000000000000100000000000000000000000000000000000000000000000000 10000100
0.5128801465034485 0011111111100000011010011000001110100000000000000000000000000000 0000000000000100000000000000000000000000000000000000000000000000 10000100
0.6287091970443726 0011111111100100000111100110001011000000000000000000000000000000 0000000000000100000000000000000000000000000000000000000000000000 10000100
0.6507882475852966 0011111111100100110100110100000111100000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
0.5141414999961853 0011111111100000011100111101100011100000000000000000000000000000 0000000000000100000000000000000000000000000000000000000000000000 10000100
0.5344889163970947 0011111111100001000110101000100010000000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 10000001
0.5667627453804016 0011111111100010001000101110101110100000000000000000000000000000 0000000000000011000000000000000000000000000000000000000000000000 10000011
0.6604780554771423 0011111111100101001000101010001011100000000000000000000000000000 0000000000000111000000000000000000000000000000000000000000000000 1101101000010111
0.6362493634223938 0011111111100100010111000010011110100000000000000000000000000000 0000000000000001000000000000000000000000000000000000000000000000 10001
0.47262275218963623 0011111111011110001111110111001110000000000000000000000000000000 0000000000111010000000000000000000000000000000000000000000000000 110101000010011101
0.5955216288566589 0011111111100011000011101000001101100000000000000000000000000000 0000000000111101000000000000000000000000000000000000000000000000 1101010000101111101
0.6833667159080505 0011111111100101110111100010001111100000000000000000000000000000 0000000000000110000000000000000000000000000000000000000000000000 10000110
0.4804770052433014 0011111111011110110000000010001010100000000000000000000000000000 0000000000111011000000000000000000000000000000000000000000000000 10111011
0.476748526096344 0011111111011110100000110000110001000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0
График с обычной мантиссой
График с 4-битной мантиссой
Комментарии (16)
krote
08.08.2024 18:29+2в упор не вижу тут эффективности сжатия чисел с плавающей запятой, ведь в примере приведены урезанные числа, большая часть битов которых не значащая и сожмется вообще большинством других алгоритмов.
dyadyaSerezha
08.08.2024 18:29+4Не сожмется, потому что обычные алогоритмы не спускаются на уровень бит, а оперируют потоком байт или их блоков. Тут же используется знание о внутренней структуре елементов потока и о их потенциальной однородности.
funny_falcon
08.08.2024 18:29Повторю: https://habr.com/ru/companies/sportmaster_lab/articles/834840/#comment_27144872
Mingun
08.08.2024 18:29Непонятно только, зачем для префикса полного числа взяли
0
, они же реже всех встречаются. Можно экономить еще по 1 биту почти на каждом числеfunny_falcon
08.08.2024 18:29Видимо, когда в Google разрабатывали алгоритм, их данные имели много повторений. Возможно, они снимали показания быстрее, чем они менялись.
vibornoff
08.08.2024 18:29+1А что если "результат XOR" переупорядочить в "битовые колонки"?
Берём 16/32/64 последовательно идущих "результата XOR" и все первые биты пакуем в первое число, все вторые биты - во второе, и т.д.
Будет на выходе поток 16/32/64-битных int-ов преимущественно состояший из `0x00…00` и `0xff…ff`.funny_falcon
08.08.2024 18:29Да, действительно такая схема есть, только ещё проще: не в битовые колонки, а в байтовые. И даже без предварительного XOR, емнип.
Если цель только сжать по сильнее, то это вполне рабочий вариант. Gorilla хороша тем, что для анализа значений не требуется предварительная распаковка всего массива. А классические алгоритмы сжатия требуют сохранять выходной буфер до окончания декомпрессии.
Хотя, конечно, можно сочетать этот подход с RLE + Хафман. Причём объединить байты и повторы в один алфавит для Хафмана. Тогда можно действительно доставать по байту из 8ми последовательностей и соединять в число. Это будет медленнее, чам Gorilla, но компрессия, наверное, будет лучше.
vadimr
В статье приведены вещественные числа с одинарной точностью, расширенные нулями до формата двойной точности. Естественно, что эти нули и пожались. Это просто жульничество.
Хотя алгоритм, по заявлению автора, и сжимает в 3 раза, а не в 2, но после такого начала веры дальнейшему уж нет.
dyadyaSerezha
Как я понимаю, вся идея такого сжатия основана на том, что последовательность чисел не случайная, а реальная - например, данные с датчиков. Тогда действительно должно быть сжатие, потому что: 1) у чисел много общих старших битов (они более-менее в одном диапазоне), и 2) может быть много нулевых младших битов, елсли датчик не обеспечивает такую точность и младшие биты просто добиваются нулями до полного формата (float, double, etc - Не важно).
vadimr
Реально такая последовательность чисел очень искусственна и маловероятна. Обычно биты в вещественных числах (кроме показателя степени) распределены достаточно случайно.
Конкретно в данном случае просто ошибочно выбран формат представления чисел, и этот факт эксплуатируется. Хотя гораздо проще было бы числа закодировать в их родной одинарной точности и не плодить несовместимый сжатый формат файла.
Хотя замечу, что с датчиков обычно идут числа с фиксированной точкой, и скорее всего вещественный формат здесь изначально вообще притянут за уши.
dyadyaSerezha
Да. Обычно вообще просто целые числа идут, а уж как их интерпретировать, дело принимающего.
funny_falcon
“Несовместимый сжатый формат” придумал Google. С тех пор его много где повторили. Повторили потому, что померили и увидели выгоду.
Произвольные вещественные числа действительно имеют много рандомных бит. Особенно, если десятичные дроби используются. Если же намеренно округлять до двоичных дробей (а когда ты сам делаешь датчики, то вполне можешь загрубить значения слегка), то нулей в хвосте получается много.
Сомневаюсь, что generic алгоритм сжатия нормально сожмёт. Во-первых, сжатие работает побайтово, а тут границы повторов на байты не выровнены. Во-вторых, повторы достаточно маленькие, и кодирование повторов плохо сжимается обычно.
Кроме степени компрессии играет роль, во-первых, скорость сжатия/разжатия, а во-вторых, возможность использования разжатых чисел немедленно, один-за-другим, без ожидания разжатия всего входного буфера, и без выходного буфера в принципе.
vadimr
Если вы читаете с датчиков, да ещё имеете возможность округлять, то вам вообще не требуются числа с плавающей точкой. Насколько мне известно, нет такого датчика чего угодно, диапазон измеряемых значений которого (т.е. динамический диапазон измеряемой величины) не укладывается в int32.
В Google примерно столько же криворуких программистов, как и везде.
funny_falcon
Датчик - это в широком смысле. Много разных показателей может быть в программах. Думать над каждым, как его представлять - пустая трата времени. Проще сказать: мы складываем в float/double с максимумом 20 бит мантиссы (что соответствует 6 знакам точности). А дальше уже умные алгоритмы сожмут это до приемлемых размеров.
А сжатие Гориллой тем и хорошо, что оно автоматически адаптируется к диапазону: ты можешь в него и миллисекунды выраженные в секундах складывать, и террабайты выраженные в байтах. Мосле xor экспоненты и те значения, и другие сожмутся примерно одинаково.
vadimr
Не разделяю такой подход.
funny_falcon
А вас ни кто и не заставляет его разделять. Не нравится, не используйте/не следуйте этому подходу.
А другие экономят своё время и довольны этим.