Комментарии 16
В статье приведены вещественные числа с одинарной точностью, расширенные нулями до формата двойной точности. Естественно, что эти нули и пожались. Это просто жульничество.
Хотя алгоритм, по заявлению автора, и сжимает в 3 раза, а не в 2, но после такого начала веры дальнейшему уж нет.
Как я понимаю, вся идея такого сжатия основана на том, что последовательность чисел не случайная, а реальная - например, данные с датчиков. Тогда действительно должно быть сжатие, потому что: 1) у чисел много общих старших битов (они более-менее в одном диапазоне), и 2) может быть много нулевых младших битов, елсли датчик не обеспечивает такую точность и младшие биты просто добиваются нулями до полного формата (float, double, etc - Не важно).
Реально такая последовательность чисел очень искусственна и маловероятна. Обычно биты в вещественных числах (кроме показателя степени) распределены достаточно случайно.
Конкретно в данном случае просто ошибочно выбран формат представления чисел, и этот факт эксплуатируется. Хотя гораздо проще было бы числа закодировать в их родной одинарной точности и не плодить несовместимый сжатый формат файла.
Хотя замечу, что с датчиков обычно идут числа с фиксированной точкой, и скорее всего вещественный формат здесь изначально вообще притянут за уши.
Да. Обычно вообще просто целые числа идут, а уж как их интерпретировать, дело принимающего.
“Несовместимый сжатый формат” придумал Google. С тех пор его много где повторили. Повторили потому, что померили и увидели выгоду.
Произвольные вещественные числа действительно имеют много рандомных бит. Особенно, если десятичные дроби используются. Если же намеренно округлять до двоичных дробей (а когда ты сам делаешь датчики, то вполне можешь загрубить значения слегка), то нулей в хвосте получается много.
Сомневаюсь, что generic алгоритм сжатия нормально сожмёт. Во-первых, сжатие работает побайтово, а тут границы повторов на байты не выровнены. Во-вторых, повторы достаточно маленькие, и кодирование повторов плохо сжимается обычно.
Кроме степени компрессии играет роль, во-первых, скорость сжатия/разжатия, а во-вторых, возможность использования разжатых чисел немедленно, один-за-другим, без ожидания разжатия всего входного буфера, и без выходного буфера в принципе.
Если вы читаете с датчиков, да ещё имеете возможность округлять, то вам вообще не требуются числа с плавающей точкой. Насколько мне известно, нет такого датчика чего угодно, диапазон измеряемых значений которого (т.е. динамический диапазон измеряемой величины) не укладывается в int32.
В Google примерно столько же криворуких программистов, как и везде.
Датчик - это в широком смысле. Много разных показателей может быть в программах. Думать над каждым, как его представлять - пустая трата времени. Проще сказать: мы складываем в float/double с максимумом 20 бит мантиссы (что соответствует 6 знакам точности). А дальше уже умные алгоритмы сожмут это до приемлемых размеров.
А сжатие Гориллой тем и хорошо, что оно автоматически адаптируется к диапазону: ты можешь в него и миллисекунды выраженные в секундах складывать, и террабайты выраженные в байтах. Мосле xor экспоненты и те значения, и другие сожмутся примерно одинаково.
в упор не вижу тут эффективности сжатия чисел с плавающей запятой, ведь в примере приведены урезанные числа, большая часть битов которых не значащая и сожмется вообще большинством других алгоритмов.
Не сожмется, потому что обычные алогоритмы не спускаются на уровень бит, а оперируют потоком байт или их блоков. Тут же используется знание о внутренней структуре елементов потока и о их потенциальной однородности.
Повторю: https://habr.com/ru/companies/sportmaster_lab/articles/834840/#comment_27144872
Непонятно только, зачем для префикса полного числа взяли 0, они же реже всех встречаются. Можно экономить еще по 1 биту почти на каждом числе
А что если "результат XOR" переупорядочить в "битовые колонки"?
Берём 16/32/64 последовательно идущих "результата XOR" и все первые биты пакуем в первое число, все вторые биты - во второе, и т.д.
Будет на выходе поток 16/32/64-битных int-ов преимущественно состояший из `0x00…00` и `0xff…ff`.
Да, действительно такая схема есть, только ещё проще: не в битовые колонки, а в байтовые. И даже без предварительного XOR, емнип.
Если цель только сжать по сильнее, то это вполне рабочий вариант. Gorilla хороша тем, что для анализа значений не требуется предварительная распаковка всего массива. А классические алгоритмы сжатия требуют сохранять выходной буфер до окончания декомпрессии.
Хотя, конечно, можно сочетать этот подход с RLE + Хафман. Причём объединить байты и повторы в один алфавит для Хафмана. Тогда можно действительно доставать по байту из 8ми последовательностей и соединять в число. Это будет медленнее, чам Gorilla, но компрессия, наверное, будет лучше.
Простая красота XOR-сжатия чисел с плавающей запятой