чем эффективней пожать 256 бит

случайные биты не жмутся

/thread

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

CRC32 сойдёт я думаю.

но в среднем у тебя будет чаще оверхед в виде заголовка и непожатые биты :)

смешная шутка

там заголовок то может будет 1 бит, так что может быть выгодно

Ну у меня жсон злибом неплохо так сжимался, если сжимать данные которые не понадобятся никогда, экономия очень неплохая. Если понадобятся, то скрость слишком проседает.

Арифметическое кодирование, наверное. Особенно, если тебя патенты не пугают.

Но на 256 битах вряд ли будет профит.

Но на 256 битах

Ринат, 256 бит - это ж всего 32 байта. Чего ТС сжимать то хочет?

Я бы даже напомнил, что это четыре int64_t.

uint64_t

Чего ТС сжимать то хочет?

256 бит

256 бит

32 байта. Сжимать нечего!

Есть специальные алгоритмы для сжатия коротких текстовых строк, например https://github.com/antirez/smaz

А для общего случая вряд ли есть что-то специальное, да и вообще непонятно, на кой черт сжимать такие объемы информации

Если у тебя есть много сообщений по 256 бит и в них не случайные данные, а есть возможны повторящиеся фрагменты, то можно использовать алгоритм общего назначения со словарем, который формируется из набора образцов. Например, zstd так умеет

Именно случайные-случайные, и без накопления статистики по предыдущим битам? Тогда только RLE.

есть чего

есть чего

Чего?

Нет нужно сжимать каждое сообщение в отдельности, не скопом

Биты. Было 32 байта, будет скажем 25 уже большой прогресс.

Нет нужно сжимать каждое сообщение в отдельности, не скопом

Вот именно для этого и предназначен режим со словарем. Если можно пожать скопом, то никакой словарь не нужен, склеиваешь вместе и жмешь с такой же эффективностью

https://facebook.github.io/zstd/#small-data

хорошо бы какой то вариант RLE для таких микро случаев, ориентированный не на байты (8 бит) а на что меньшее

будет скажем 25

Не будет. Только если это не нули с парой единиц.

Возьми файл размером 50 мегабайт случайных данных из /dev/urandom и попробуй сжимать разными архиваторами. Затем сравни размер архивов и оригинала и пойми тщетность этой затеи.

и int64_t тоже

при линейном распределении - да, но если там какое-то другое, например, гауссово, то вполне, вот только 256 бит - слишком мало, чтобы получить профит, ну кроме случая, когда можно составить словарь, как выше советуют

при линейном распределении - да,

ты хотел сказать равномерном, а это подразумеваемый дефолт для случайных данных

подразумеваемый дефолт для случайных данных - гауссово распределение, кстати оно ещё называется «нормальным» не просто так

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

но блин 32 байта это как говорила Раневская «Королевство маловато - разгуляться негде». проще не париться этим обрезком вечности.

32 байта «жмутся по-любому» #&169; (это не шутка и не троллинг)

меньше уже как повезёт :(

а 32 байта — да, жмутся. другое дело, что «выигрыш» там ~4..12 bit (это насколько я помню, лень рыться в записях).

как только, алгоритм станет public я тебя кастану и ты меня опровергнешь. ЛОР нас рассудит :)

---
блин, прощай отпуск // и кто меня за язык тянул

есть чего

Чего?

а чего надо?

а чего надо?

У ТС спроси, я так и не распарсил, чё ему надо.

Есть последовательность из 256 случайных бит, нужно попытаться их чем то эффективно пожать

Эффективнее всего никак не жать, т.к. случайные данные не жмутся.

случайные данные не жмутся

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

Я дико извиняюсь, а хранится это будет как? Имею ввиду: записывать на hdd (ssd)? А как же размер блока?

они у тебя случайные, или с неизвестной закономерностью?

если случайные, то они не жмутся. вариант жать/не жать не даст профита в среднем. если бы у тебя было, например, 254 бита, и 2 бита незаняты, тогда можно выжать чуть-чуть за счет использования этих 2 бит. почитай про сжатие хаффмена, с математическими выкладками, возможно, наступит просветление.

если какая-то неизвестная закономерность, то надо изучать её, и плясать уже от этих данных

Случайные это и есть белый шум

Написал бы, какое распределение. Мы тут Ванги что ли?

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

Ему, как я понял, не хранить, а передавать.

Нет. Белый шум - это равномерное распределение.

хорошо бы какой то вариант RLE для таких микро случаев, ориентированный не на байты (8 бит) а на что меньшее

Вот интересный совет про битовый RLE https://stackoverflow.com/a/7603969 (с 1 битом оверхеда на все сообщение в худшем случае).

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

Это не то, что можно сжать. Сдавайся, не пытайся делать вечный двигатель, получить 110% КПД

спектр шума бывает не только белым

Вот тут пишут можно достичь сжатия с соотношением 0.3-0.4 на примере википедии, ещё они смазали всё simd чтобы быстро работало. Вроде это оно.

на примере википедии

А разве на википедии есть большое количество случайных данных?

на википедии

В википедии.

А разве на википедии есть большое количество случайных данных?

Ну, говорят, что вся wiki - случайный набор букв, иногда складывающихся в осмысленные фразы. )

Это не случайный шум. Пожми /dev/random

Википедия не Украина.