LINUX.ORG.RU

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

 


0

1

Есть последовательность из 256 случайных бит, нужно попытаться их чем то эффективно пожать. Те я буду выдавать на выход некий заголовок в котором буду указывать применял ли я сжатие, какое и данные (сжатые или нет). Подскажите плиз чем (в идеале каким алгоритмом но пойдет и библиотека/тулза) эффективно пожать 256 случайных бит? Если несколько алгоритмов, то совсем хорошо. Пока то что у меня придумывается не особо хорошо.

Ответ на: комментарий от Harald

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

quester ★★ ()
Ответ на: комментарий от Harald

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

quester ★★ ()
Ответ на: комментарий от quester

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

linuxnewbie ()

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

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

i-rinat ★★★★★ ()

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

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

annulen ★★★★★ ()

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

annulen ★★★★★ ()

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

anonymous ()
Ответ на: комментарий от quester

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

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

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

annulen ★★★★★ ()
Ответ на: комментарий от quester

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

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

Deleted ()

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

V1KT0P ★★ ()
Ответ на: комментарий от Harald

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

next_time ★★★★★ ()
Ответ на: комментарий от next_time

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

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

Harald ★★★★★ ()
Ответ на: комментарий от Harald

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

next_time ★★★★★ ()

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

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

pfg ★★★★★ ()
Ответ на: комментарий от Deleted

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

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

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

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

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

anonymous ()
Ответ на: комментарий от anonymous

а чего надо?

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

Deleted ()

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

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

peregrine ★★★★★ ()
Ответ на: комментарий от peregrine

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

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

annulen ★★★★★ ()

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

mul4 ★★★★★ ()
Последнее исправление: mul4 (всего исправлений: 1)
Ответ на: комментарий от quester

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

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

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

MyTrooName ★★★★★ ()

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

deadplace ()

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

Deleted ()
Ответ на: комментарий от peregrine

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

annulen ★★★★★ ()
Ответ на: комментарий от quester

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

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

Deleted ()

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

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

I-Love-Microsoft ★★★★★ ()

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

linuxnewbie ()
Ответ на: комментарий от V1KT0P

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

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

Deleted ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.