Имеется последовательность чисел, которая плавно возрастает, убывает и тд. Хочется её сжать. Числа с точностью 4 цифры после запятой.
Базовая оценка: текстовый JSON вида {"items": [0.1234, 0.1234, 0.1235, 0.1235, ...]} занимает 358 KB, сжимается гзипом до 73 KB.
Первый подход — извлекаем числа, масштабируем до целых (умножаем на 10000) и сохраняем как 4-байтовые int-ы в бинарном файле. Потом гзипуем файл. Получаем 69 KB.
Второй подход — сохраняем не сами числа, а разницу между ними, т.к. они довольно медленно возрастают/опускаются. Опять сохраняем как 4-байтовые int-ы. Получаем 44 KB.
Третий подход — нормализуем эти разницы, отнимая минимальное число, т.е. от 0 до max-min. Идея в том, что числа довольно маленькие, а отрицательные числа будут представлять из себя кучу единиц, может быть они сожмутся хуже нулей. Толку нет, получилось даже немного хуже.
Четвёртый подход — замечаем, что разницы умещаются в два байта максимум, а порой и в 1 байт, делаем немного умней алгоритм и сохраняем их группами то по 2 байта, то по 1 байту. Гзипаем результат, получилось 38K.
Пятый подход — реализуем всё сжатие вручную на кодах Хаффмана. В общем получилось лучше gzip, но не намного, цифр сейчас нет, в целом решил не двигаться в этом направлении, т.к. кода много, а толка мало. Общий подход был таков: берём разницы, часто эти разницы равны друг другу, т.е. идёт, например, куча нулей подряд, поэтому записываем парами (разница, количество разниц), потом считаем коды Хаффмана для значений разниц и для значений количеств разниц, потом записываем максимально экономя каждый бит это всё в конечный файл.
Вопрос — есть ли способ скармливать gzip-у данные так, чтобы он их как можно лучше распознавал и сжимал? Gzip нравится, т.е. его проверенные реализации есть везде.
Альтернативно можно попробовать сделать свой алгоритм, тогда тоже буду рад советам, но только если этот алгоритм будет намного лучше gzip-а, хотя бы раза в 3, т.к. его как минимум на двух языках придётся реализовывать и поддерживать, овчинка должна стоить выделки.
Здравствуйте, xma, Вы писали:
vsb>>Хочется её сжать.
xma>зачем ?
Чтобы по сети быстрей передавалось и в базе данных меньше места занимало.
vsb>>занимает 358 KB, сжимается гзипом до 73 KB. vsb>>Гзипаем результат, получилось 38K.
xma>недостаточно сжалось ? а сколько надо ?
Ну пока хочется все варианты посмотреть. Если получится сжать до 4КБ, например, будет идеально. Пока что планирую просто сжимать JSON, т.к. дальнейшие выигрыши не такие большие, а переписывать придётся много, но если выигрыш будет очень большой, то перепишу.
Здравствуйте, vsb, Вы писали:
vsb>Пятый подход — реализуем всё сжатие вручную на кодах Хаффмана.
Хаффман устаревший способ сжатия, арифметическое эффективнее: https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5
vsb>Вопрос — есть ли способ скармливать gzip-у данные так, чтобы он их как можно лучше распознавал и сжимал? Gzip нравится, т.е. его проверенные реализации есть везде.
vsb>Альтернативно можно попробовать сделать свой алгоритм, тогда тоже буду рад советам, но только если этот алгоритм будет намного лучше gzip-а, хотя бы раза в 3, т.к. его как минимум на двух языках придётся реализовывать и поддерживать, овчинка должна стоить выделки.
Я для таких целей делаю своё сжатие, а поверх гзипом (т.к. браузеры его нативно декодируют).
В твоём варианте я бы сохранял разницу пока она помещается в байт (+-127) и 255 + два байта, если не влазит. А гзип там уже разберётся.
Хаффмана я за 20 минут на жаве реализовал, а арифметическое мне показалось очень сложным. Как я понимаю, оно хоть и лучше в теории, но в целом выигрыш не какой-то огромный.
Здравствуйте, vsb, Вы писали:
vsb>Альтернативно можно попробовать сделать свой алгоритм, тогда тоже буду рад советам, но только если этот алгоритм будет намного лучше gzip-а, хотя бы раза в 3, т.к. его как минимум на двух языках придётся реализовывать и поддерживать, овчинка должна стоить выделки.
А как насчет bzip/7z?
P.S. Если сжималка работает медленнее сети, а это бывает, особого ускорения передачи от сжатия не получишь
Здравствуйте, vsb, Вы писали:
vsb>Пятый подход — реализуем всё сжатие вручную на кодах Хаффмана. В общем получилось лучше gzip, но не намного, цифр сейчас нет, в целом решил не двигаться в этом направлении, т.к. кода много, а толка мало. Общий подход был таков: берём разницы, часто эти разницы равны друг другу, т.е. идёт, например, куча нулей подряд, поэтому записываем парами (разница, количество разниц), потом считаем коды Хаффмана для значений разниц и для значений количеств разниц, потом записываем максимально экономя каждый бит это всё в конечный файл.
gzip — это и есть LZ77 + Хаффман. Поэтому, разницы особой не будет.
vsb>Вопрос — есть ли способ скармливать gzip-у данные так, чтобы он их как можно лучше распознавал и сжимал? Gzip нравится, т.е. его проверенные реализации есть везде.
Можно попробовать LEB128 и BWT.
vsb>Альтернативно можно попробовать сделать свой алгоритм, тогда тоже буду рад советам, но только если этот алгоритм будет намного лучше gzip-а, хотя бы раза в 3, т.к. его как минимум на двух языках придётся реализовывать и поддерживать, овчинка должна стоить выделки.
Я бы для начала записал бы разницы между значениями в файл в виде LEB128, после чего скормил бы это 7-Zipу на максимальном уровне сжатия (LZMA и PPMd отдельно). Это даст некую приблизительную оценку верхнего предела сжимаемости. Которую надо пересчитать в конкретные метрики. Если все сводится к тому, что у среднего юзера страница будет грузиться на 0.1 секунду быстрее, то нафиг такую оптимизацию.
Здравствуйте, vsb, Вы писали:
vsb>Хаффмана я за 20 минут на жаве реализовал, а арифметическое мне показалось очень сложным. Как я понимаю, оно хоть и лучше в теории, но в целом выигрыш не какой-то огромный.
Ещё есть дурацкий вариант: если скорость сжатия некритична — можно использовать zopfli или может уже аналоги есть. Они обеспечивают лучшую компрессию для gzip.
Здравствуйте, vsb, Вы писали:
vsb>Первый подход — извлекаем числа, масштабируем до целых (умножаем на 10000) и сохраняем как 4-байтовые int-ы в бинарном файле. Потом гзипуем файл. Получаем 69 KB.
А двух байт разве не достаточно?
Может поделитесь файлом, а люди поиграют (кто лучше сожмет)?
Здравствуйте, vsb, Вы писали:
vsb>Альтернативно можно попробовать сделать свой алгоритм, тогда тоже буду рад советам, но только если этот алгоритм будет намного лучше gzip-а, хотя бы раза в 3, т.к. его как минимум на двух языках придётся реализовывать и поддерживать, овчинка должна стоить выделки.
Здравствуйте, vsb, Вы писали:
vsb>Имеется последовательность чисел, которая плавно возрастает, убывает и тд. Хочется её сжать. Числа с точностью 4 цифры после запятой.
vsb>Базовая оценка: текстовый JSON вида {"items": [0.1234, 0.1234, 0.1235, 0.1235, ...]} занимает 358 KB, сжимается гзипом до 73 KB.
Здравствуйте, NGPraxis, Вы писали: NGP>Хаффман устаревший способ сжатия, арифметическое эффективнее
Арифметическое кодирование — устаревший способ сжатия. ANS эффективнее.
Скрытый текст
Арифметическое кодирование хотя и подбирается по эффективности сжатия к теоретическому пределу (а также обладает простым описанием и реализацией), уже не используется в новых разработках алгоритмов сжатия. Asymmetric numeral systems в области энтропийных кодеров его безоговорочно победил.
Здравствуйте, vsb, Вы писали:
vsb>Хаффмана я за 20 минут на жаве реализовал, а арифметическое мне показалось очень сложным. Как я понимаю, оно хоть и лучше в теории, но в целом выигрыш не какой-то огромный.
Интересно, что не нужно сжимать данные алгоритмом Хаффмана чтобы узнать сколько они будут занимать: достаточно умножить длину кодового слова на количество символов и просуммировать (плюс добавить сколько-то бит на хранение самого дерева).
В некотором смысле, аналогичное получается и для арифметического кодирования: его эффективность настолько близка к теоретическому пределу, что можно просто подставить частоты в формулу энтропии Шеннона, округлить результат вверх и почти не ошибиться
Там есть разные эффекты вроде снижения эффективности из-за ограниченного длинны используемых чисел, всяких патологических последовательностей и кодирования хвоста, но всем этим можно пренебречь на таких объёмах.
То есть совсем не обязательно реализовывать кодер для оценки эффективности его сжатия.
vsb> Общий подход был таков: берём разницы, часто эти разницы равны друг другу, т.е. идёт, например, куча нулей подряд, поэтому записываем парами (разница, количество разниц), потом считаем коды Хаффмана для значений разниц и для значений количеств разниц, потом записываем максимально экономя каждый бит это всё в конечный файл.
Вот, это самое важное.
Можешь считать, что у тебя уже есть алгоритм Хаффмана, или идеальный арифметический или ANS кодер. Но они — методы энтропийного сжатия. Их эффективность зависит от исходного алфавита и частот. Если применять их напрямую к сырым данным — результат будет разочаровывающим.
Для эффективного сжатия используется несколько этапов препроцессинга, которые как-то учитывают характер данных.
Кодируются абсолютные числа? Приведём их в относительные добавлением константы. Они слабо меняются? Вставим в начало дельта-кодирование. Очень слабо меняются? Сделаем его дважды. Получившиеся разности имеют удачное распределение? Применим коды Голомба...
И лишь где-то в конце пропустим это через Zstd в качестве универсального средства сжатия.
То есть в задаче сжимания векторов чисел в первую очередь важен выбор препроцессинга, учитывающего характер этих чисел, а не то, чем потом он будет дожиматься. Где-то RLE всех может порвать, а где-то преобразование из little-endian в big-endian развяжет руки методам контекстного моделирования (внезапно, как при сжатии x86 кода )
Здравствуйте, Quebecois, Вы писали:
Q>Я бы для начала записал бы разницы между значениями в файл в виде LEB128, после чего скормил бы это 7-Zipу на максимальном уровне сжатия (LZMA и PPMd отдельно). Это даст некую приблизительную оценку верхнего предела сжимаемости. Которую надо пересчитать в конкретные метрики. Если все сводится к тому, что у среднего юзера страница будет грузиться на 0.1 секунду быстрее, то нафиг такую оптимизацию.
В общем так получается:
Вариант один это просто писать значения в виде двухбайтовых чисел. Получилось 114552 байта.
Вариант два это писать в этом leb128. Получилось 89396 байта.
Вариант один через gzip: 37012. Вариант два через gzip: 32999. Т.е. для gzip это работает.
Теперь вариант один через winrar: 27478. Вариант два через winrar: 32510. То бишь винрар хорошо сжал данные без каких-то особых преобразований и плохо сжал данные с LEB128. 7-zip расположился между этими двумя вариантами, первый вариант сжал хуже винрара, второй лучше, но всё равно первый вариант лучше второго.
Здравствуйте, watchmaker, Вы писали:
W>И лишь где-то в конце пропустим это через Zstd в качестве универсального средства сжатия.
Вот на вход этому zstd к примеру в каком виде надо подать эти числа, чтобы он хорошо распознал то, что я ему хочу сказать. Т.е. все алгоритмы по сути принимают поток байтов. В какой вид надо преобразовать поток чисел, скажем в общем случае int4, чтобы zstd их хорошо сжал. Я пока пробовал варианты примитивные (прям так и пишем по 4 байта) и хитрые (вроде этого leb128). Результаты получаются сильно разные с разными алгоритмами, пока однозначный ответ не понятен.
Здравствуйте, vsb, Вы писали:
vsb>Имеется последовательность чисел, которая плавно возрастает, убывает и тд. Хочется её сжать. Числа с точностью 4 цифры после запятой.
vsb>Базовая оценка: текстовый JSON вида {"items": [0.1234, 0.1234, 0.1235, 0.1235, ...]} занимает 358 KB, сжимается гзипом до 73 KB.
Если допустимо сжимать с какой-то потерей точности, то можно поискать что наизобретали в промышленной автоматизации. Например SwingingDoor: https://habr.com/ru/post/105652/ (в комментариях есть еще названия других алгоритмов)
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, Quebecois, Вы писали:
Q>>Я бы для начала записал бы разницы между значениями в файл в виде LEB128, после чего скормил бы это 7-Zipу на максимальном уровне сжатия (LZMA и PPMd отдельно). Это даст некую приблизительную оценку верхнего предела сжимаемости. Которую надо пересчитать в конкретные метрики. Если все сводится к тому, что у среднего юзера страница будет грузиться на 0.1 секунду быстрее, то нафиг такую оптимизацию.
vsb>В общем так получается:
vsb>Вариант два это писать в этом leb128. vsb>Вариант два через gzip: 32999. Т.е. для gzip это работает. vsb>Теперь вариант один через winrar: 27478.
Т.е. даже теоретический выигрыш против LEB128+gzip — около 12%, или 5кб, или 13 мсек при скромной в наше время скорости 3G. Я бы остановился на текущем варианте и не заморачивался бы.
Если очень припрет, можно разделить данные на 2 пакета, и показывать первый, пока грузится второй. С точки зрения юзера скорость работы от этого увеличится гораздо быстрее.
Здравствуйте, vsb, Вы писали:
vsb>Имеется последовательность чисел, которая плавно возрастает, убывает и тд. Хочется её сжать. Числа с точностью 4 цифры после запятой.
А попробуй проделать всё то же, но поразрядно — единицы с единицами, десятки с десятками и т.д.
Когда-то мы применяли такое сжатие чуть ли не с rle, результат получался неплохой.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, vsb, Вы писали:
vsb>Имеется последовательность чисел, которая плавно возрастает, убывает и тд. Хочется её сжать. Числа с точностью 4 цифры после запятой.
vsb>Базовая оценка: текстовый JSON вида {"items": [0.1234, 0.1234, 0.1235, 0.1235, ...]} занимает 358 KB, сжимается гзипом до 73 KB.
vsb>Второй подход — сохраняем не сами числа, а разницу между ними, т.к. они довольно медленно возрастают/опускаются. Опять сохраняем как 4-байтовые int-ы. Получаем 44 KB.
vsb>Пятый подход — реализуем всё сжатие вручную на кодах Хаффмана. В общем получилось лучше gzip, но не намного
Единственных два нормальных подхода. Остальное -- шаманство. gzip и т.п. алгоритмы тоже, возможно,
имеют смысл, если в последовательностях чисел будут повторения.
Хаффман на фоне арифметического кодирования проигрывает. Вместо арифметического
кодирования в лоб есть алгоритмы вроде "русский народный range coder Дмитрия Субботина".
Рекомендую: http://caxapa.ru/?id=854732
а сколько надо ?
