Какие есть простые варианты сжания битовых данных - отдельных чисел, небольших структур?

переизобретаем архиватор? может сначала теорию пойдешь почитаешь, потом будешь тащит свои «мегановыеидеи» на лор?

Ты про префиксное кодирование (код Хаффмана)?

А почему бы zlib не использовать?

0 - нет числа, 10 - 4 бита, 010 - 8 битов, 110 - 16 битов

Что то не то. Maybe:

0 - нет числа, 10 - 4 бита, 110 - 8 битов, 1110 - 16 битов

>Были еще какие то варианты, но не могу вспомнить как эта тема называется

Ещё вариант - просто модернизировать компьютер.

Есть ещё вариант. Я тут скормил жопеги вебп с ~90% качеством (меньше продуцирует артефакты, в зависимости от вводных можно до 60 понижать), получил 60% экономии. А на пнг так вообще до 95% меньше места надо. Так что за новыми алгоритмами будущее. Часть сканов я бы отправил в 10-12 битный bpg, жаль он ничем не поддерживается. Придётся писать патчи видимо.

0 - нет числа

Если данные однотипные со множеством «пробелов», может вообще использовать индексную модель:

data[i]=value;
index[t]=i;

или даже так:

data[i]=value;
*index[t]=*data[i];

Если кто-то сомневается, вот пример https://bellard.org/bpg/lena.html

Ну, обычно специализированное сжатие лучше универсального (с учетом требований к результирующему размеру и скоростям упаковки/распаковки). Так что нужно знать контекст.

Если что-то универсальное, можешь посмотреть на то, как устроен протобаф.

https://developers.google.com/protocol-buffers/docs/encoding

Там в небольшой статье описано и про вариативное кодирование чисел и про кодирование зигзаг для отрицательных чисел и в принципе можешь на сам протобаф посмотреть — это сейчас популярный формат сериализации.

0 - нет числа, 10 - 4 бита, 010 - 8 битов

Уже не сработает, потому что 0 и 010 нельзя различить. Тебе нужен https://ru.wikipedia.org/wiki/Экспоненциальный_код_Голомба.

Или если просто числа нужно сохранять, то https://en.wikipedia.org/wiki/LEB128.

Да, с примером я немного промахнулся.

Код Голомбо - да, один из вариантов. Но если задуматься, более общая схема, примерно как в LEB128 - битовый маркер есть ли следующее число плюс очередной пакет значения. Только значение не обязательно дробить на 7 бит, а в зависимости от контекста можно и на 3 или 4 бита. И упаковывать это все в битовый поток.

Счетчик, те что подсчитывают что либо, думаю по 3 бита, а идентификаторы 7 или 8 бит. Замерить на практике, какое дробление будет лучше.

Ещё вариант - просто модернизировать компьютер.

Если объем данных и расчетов возрастает экспоненциально, то на модернизации компьютера далеко не уйдешь. Только поиск алгоритмов снижающих эту экспоненциальность.

Что-то вроде такого:

Функция УпаковатьЗначение(поток_упаковки, значение, n битов дробления)
   НачалоЦикла
      если значение = 0 тогда
         добавить битовое знаение 0
         прервать
      иначе
         добавить в поток_упаковки битовое значение 1
         добавить в поток n битов из (значение & маска n битов)
         значение = значение >> n
      конец
   КонецЦикла
КонецФункции

Стесняюсь спросить: а с какой целью ты решил изобрести колесо?

Как можно упаковывать числа и структуры, что бы меньше занимало место в памяти и на диске?

https://www.youtube.com/watch?v=wDgD4gokEis

получил 60% экономии

Скорми эти жопеги гугловому guetzli и получи ещё большую экономию без видимого ухудшения качества и преобразования в webp.
Правда если использовать обычную (не opencl/cuda) версию, то оно ОЧЕНЬ долго это делает.

Попробовал. Очень смазывает детали, 300 dpi скан процессит нереально долго, файл меньше на 15-25% (от дефолт до q90). Там терабайты сканов, чаcть в 600 dpi. Webp практически устраивает, хотелось бы конвертировать в него только когда bpg не вышел. Цветные png лучше бы в bpg всё же.

Стесняюсь спросить: а с какой целью ты решил изобрести колесо?

По вашему поиск знаний это изобретение колеса? Я спросил какие есть методы, мне ответили, я выбрал подходящий под ситуацию и чуть усовершенствовал. Если знаете лучше вариант или хоть какой-нибудь вариант, то скажите, а то зачем встревать?

Всё тот же вопрос: а зачем?

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

а зачем?

упаковывать числа и структуры, в теме написано и приведен пример, что примерно мне нужно.

zip, gzip, bzip2, xz, {список продолжить}

Недостаточно?

Недостаточно?

dedup забыл.

Я читаю это как deflate+параша, deflate, параша, lzma. На практике наибольшая польза от lz4 и zstd.

для битмапов н.р. https://roaringbitmap.org/

zip, gzip, bzip2, xz, {список продолжить} Недостаточно?

А который из них умеет 4 байта упаковывать в один бит? Мне казалось они все для работают на уровне байтов, и расчитаны для данных неопределенной структуры.

https://msgpack.org

P. S. Прочитал всю тему — это именно оно. Числа, структуры, налетай, забирай, готовое, на всем чем можно реализованное… То, что доктор прописал.

https://msgpack.org P. S. Прочитал всю тему — это именно оно.

Примерно, но мне очень важно, что бы упаковывать в биты, а не в байты, потому что в оставшиеся биты я хочу добавлять еще разную инфу.

Для примера, структура может быть существенно больше 4 байт, и ее нужно расположить в отдельном месте, и подгружать ее по затребованию и сослаться на нее по идентификатору. Но в то же время, в некоторых случаях в упакованном виде она занимает не больше 31 бит, и в этих случаях я хочу вместо идентификатора сами данные структуры расположить вместо идентификатора, и приписать один старший бит, что это данные, а не идентификатор.

Для тех, кто поднимает шум, типа не фиг мелочиться, просто обнови комп, скажу, что мне моих 32Гб оператики не хватает для нужных мне целей.

В указанном упаковщике, структура:

typedef struct msgpack_sbuffer {
    size_t size;
    char* data;
    size_t alloc;
} msgpack_sbuffer;

010

Это «8 бит» или «два числа - одного нет, другое 4 бита»?

Примерно, но мне очень важно, что бы упаковывать в биты, а не в байты, потому что в оставшиеся биты я хочу добавлять еще разную инфу.

Ну так отдай ее тоже messsagepack’у, он поддерживает иерархические структуры данных. Существенно более плотную упаковку ты все равно не получишь, пол-октета все равно не передашь.

Для примера, структура может быть существенно больше 4 байт, и ее нужно расположить в отдельном месте, и подгружать ее по затребованию и сослаться на нее по идентификатору. Но в то же время, в некоторых случаях в упакованном виде она занимает не больше 31 бит, и в этих случаях я хочу вместо идентификатора сами данные структуры расположить вместо идентификатора, и приписать один старший бит, что это данные, а не идентификатор.

Messagepack это уже решил, причем без вынесения в отдельное место, смотреть пункты «array format family» и «map format family».

Короче, перед изобретанием велосипедов, засунь свой message в messagepack в лобешник, со массивами и мапами, ни в чем себе не отказывая, посмотри, как он это расположит и прикинь, сможешь ли ты разработать что-то лучше, почему нельзя проблемные куски встроить в messagepack как opaque data, а для экономии на интах использовать его средства и стоят ли эти последние 15% экономии того геморроя, который ты огребешь пытаясь переизобрести этот сложный, готовый и зрелый стандарт. А потом еще и реализации писать. Вангую, что не стоят.

В С это называется битовые поля или bit fields.

struct waka
{
   unsigned int suit : 2;
   unsigned int face_value : 4;
};

Ну так отдай ее тоже messsagepack’у, он поддерживает иерархические структуры данных. Существенно более плотную упаковку ты все равно не получишь, пол-октета все равно не передашь.

Рассмотрим приведенный пример https://github.com/msgpack/msgpack-c/wiki/v2_0_cpp_tutorial#aggregate-value В этом примере показывает как пакуются 5 чисел типа int, и показывается что получилось в результате. Кажное число помещает в одтельный байт, хотя приведенный пример вполне можно было бы размещать не по байтам, а по 4 бита на число.

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

Данная библиотека вероятно хороша целей передачи данных скажем через интернет - упаковать структуру, а потом еще и зипом сжать, но для моих целей оно не оптимально.

Мне нужно паковать отдельные однотипные структуры, потом их вытаскивать обратно по иднексу. В некоторых полях этих структур, данные в большинстве случаев отсутствуют, и тогда в упакованном виде они заменются одним битом - есть ли нет. Сам этот бит является записью кода Голомбо или вариацией LEB128.

Кстати, если говорите что использование LEB128 это изобретение велосипеда, то получается что использование msgpack это то же изобретение велосипеда. И в результате я должен все задвинуть, и всегда искать готовый конечный продукт.

Нет, мы тебе говорим, что разработка аналогов XYZ — изобретение велосипеда. А задвинуть и юзать готовое ты реально должен.

Часть сканов я бы отправил в 10-12 битный bpg, жаль он ничем не поддерживается. Придётся писать патчи видимо.

Делюсь рецептом как правильно готовить сканы (в том числе черно-белые лекции, написанные от руки) (не фотки, а именно сканы документов которые надо читать и на которых не нужен цвет). Будет исходить из того что начальный формат jpeg или tiff.

#!/bin/sh
for i in *.jpg; do convert $i ${i%jpg}pnm; done
for i in *.pnm; do convert -contrast -gamma 1.9 -normalize $i ${i%.pnm}_.pnm; done
for i in *_.pnm; do convert $i ${i%_.pnm}.pbm; done
for i in *.pbm; do cjb2 -dpi 300 -clean $i ${i%pbm}djvu; done
djvm -c book.djvu *.djvu

Нет, мы тебе говорим, что разработка аналогов XYZ — изобретение велосипеда. А задвинуть и юзать готовое ты реально должен.

Сравнил я упаковку типовым qCompress(bytes,9) с моей упаковкой. Вот такие результаты:

raw 32 zip_raw 34 my_conv_to_bits 18 zip_my_conv_to_bits 31
raw 32 zip_raw 32 my_conv_to_bits 18 zip_my_conv_to_bits 31
raw 32 zip_raw 34 my_conv_to_bits 16 zip_my_conv_to_bits 29
raw 48 zip_raw 40 my_conv_to_bits 22 zip_my_conv_to_bits 35
raw 32 zip_raw 35 my_conv_to_bits 16 zip_my_conv_to_bits 29
raw 32 zip_raw 31 my_conv_to_bits 18 zip_my_conv_to_bits 31
raw 16 zip_raw 24 my_conv_to_bits 10 zip_my_conv_to_bits 22
raw 12 zip_raw 24 my_conv_to_bits 10 zip_my_conv_to_bits 22
raw 12 zip_raw 24 my_conv_to_bits 10 zip_my_conv_to_bits 22
raw 32 zip_raw 33 my_conv_to_bits 14 zip_my_conv_to_bits 27
raw 12 zip_raw 24 my_conv_to_bits 10 zip_my_conv_to_bits 22
raw 80 zip_raw 69 my_conv_to_bits 32 zip_my_conv_to_bits 47
raw 64 zip_raw 52 my_conv_to_bits 27 zip_my_conv_to_bits 40

В моей упаковке использовалось только обрезание лишних не значащих нулей за счет указания, сколько значащих цифр содержится в значении и склеивание этого на уровне битов. Методы сделаны на вскидку, без подгонки под оптимальность.

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

https://github.com/victorprogrammist/test_pack_qCompress_and_bits Здесь исходники этих упаковок - работа с битами на пару страниц кода.

Здесь исходники этих упаковок - работа с битами на пару страниц кода.

А где сами тесты то?

А где сами тесты то?

это вырезка из большого проекта, сообщения генерятся в файле pack_types.h там легко увидеть. Делать специальный выделенный тест так же как и подробное описание не вижу смысла - те кому нужно понять поймут, там все очень кратко. А упертые упирают на ихнюю правильность, а не на то что нужно для мной обозначенной задачи.

Вопрос совершенно бессмысленный без уточнения характера выборки.

Приведи пример реальных данных, которые тебе надо упаковать. Можно на pastebin