Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Научпоп доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 20
А что там с отрицательными значениями? Или я упустил?
Биты они и есть биты) универсальный же код!
Upd: если мы знаем еще что это вдобавок и число то можно еще бит сэкономить не тратя память на очевидную первую единицу
На счет отрицательных я сейчас подумал и можно 1 бит флаг писать в конец перед терминатором, но вообще это зависит от того как вы отрицательные числа кодируете, флагом в начале или по стандарту который сейчас везде
Откуда-то из леса раздается эхо: код Хаффмана, Рида-Соломона...
Это большая развесистая тема, как можно кодировать поток, избегая передачи лишних бит, но не забывая о помехозащищённости..
Во времена медленных аналоговых модемов было очень востребовано. На канальном уровне OSI оно и сейчас все используется, на прикладном как бы нет необходимости, а микроконтроллеры на Rust вроде пока ещё не программируют
Так я же про хранение написал. О сжатии и передаче даже не заикался!
При чем тут Хаффман и Соломон то…
но тема действительно интересная)
Upd: на счет микроконтроллеров - есть no_std, но если очень хочется переписать на C, 400 строк по образцу написать нынче дело очень простое
не только, как я понял мы стартуем с самого простого, распологаем в регистр всю инфу - тоесть пакуем битами например в u32/u64/u128 - с u32 выгодно пока инфа влезает в 4 байта и тд, в вокселях встретить можно, суть в том что на координаты и прочие метки памяти типо больше расходуется, так например, координаты, свет, ао, угол - номер вершины, текстуру - id, можно запаковать... оно прикольно работает, но это не новое прям уж чтобы, ну и да там наверно сверху еще дожать можно даже простым каким-нибудь стоковым RLE сжатием и не только..., вот например закинуть это всё в текстуру и запаковать jpegxl ну я предположил может так и нельзя )
ну и соотв, если инфы меньше можно и в u8 всё закидывать, но без координат тогда, если про воксели )
зы, сразу отвечу, вам придётся или процессору или компилятору всё это приводить к одному знаменателю, поэтому данные такие потоковые придётся уплотнять 1 длинной регистра типо
обычно приходят типо к проблеме, переменная длинна таких данных и проводка их по переменной памяти, а вы пошли еще глубже переменная длинна битности, но максимум будет выборкой тогда поидее, тоесть поидее если максимальная последовательность уложилась в 128 лучше в 128 наверно укладывать, или если в 32 в 32 тогда укладывать.
вот пример, чанк 16х16х16 он проходит по u32, и добирает метаданными в себя, но шум в чанк переменной длинны и доступны прыжки по кускам памяти, которые берутся из генератора фиксированной длинны 4096 - типо 1 чанк, проблема в том, что проводить память по чанкам с шумом и есть та проблема, которую надо решить при проводке такой памяти.
Я так понял ты про упаковать несколько чисел в один u32/u64/u128? Когда ты знаешь заранее что и как кладешь и тебе все считать на видеокарте - то так и надо
Но суть моего кода в том, что ты пишешь биты не по фиксированной раскладке фиксированной длины, а сколько надо - столько и пишешь, отсюда и появляется проблема неоднозначности декодирования, которую решают универсальные коды типа моего.
возможно вы правы, мне показалось вы что-то тривиальное сделали, а вы сравнивали как ваше работает по сравнению с задачей где выбираем упаковку и сверху дожимаем например RLE, не будет ли там тоже самое?
тоесть получается, если это перенести на картинку, то ячейка RGB не фиксированная, мы танцуем от размера по месту? а как память выделять будем? поидее же надо, чтобы было красиво, как-то параметризировать и выделить 1 большой кусок посчитать и раскодировать и освободить память или нет?
ну типо есть пнг, но можно и тга использовать, разницы нету в целом если нужна именно картинка, да и плюс есть jpgxl уже который вроде даже лучше пнг уже работает.
я щас задумался, у меня в демке мир сохраняется кусками по 4096кб, я так задумался, в разрезе со взглядом на сравнение пнг и тга очень похоже, по-сути разницы нету. ну выигрываем 3кб или 80% это много на масштабе?
--
не в тему кстати еще добавлю если ищем что-то классное и хочется не С/С++ есть еще зиг, там comptime интересный, может поможет), но я запускал одну демку на нём, разницы не заметил - типо по моим интересам в другой задачке всё так же бодро работает как в Расте ), но механики и задумка там интересные
Конструкция прикольная, но что если битовый поток начинается с двух нолей? Еще к недостаткам я бы отнес использование непредсказуемого числа раз popcount при кодировании, тем более что не везде эта операция аппаратно ускорена. И невозможность заранее быстро оценить сколько займет закодированное значение, это тоже бывает важно при расчете “стоимости” хранения, когда есть выбор как кодировать.
p.s. например есть же всякие дельта коды, которые по сути гамма, у которых экспонента тоже закодирована гамма кодом - вполне себе похожие конструкции получаются.
00 - 0 единиц, можно кодировать сколько угодно нулей, если не нужно - всегда можно сдвинуть все числа и назначить на 00 одну единицу или что то другое вообще
Насчет оценки сколько попкаунтов. Верхняя оценка - столько же сколько и у омеги, а точно без попкаунтов посчитать и не выйдет
Если надо выбирать из нескольких стратегий то надо их как то кодировать по идее log2(число стратегий) битами, или заранее выбрать одну - смотря какие числа чаще будут встречаться, на 16к-2кк vbyte самый вкусный потому что паддинг нули почти пропадают в процентном соотношении а сумма битовых флагов еще более менее сравнима с омегой
По факту для маленьких штучек лучше писать фиксированные кастомные структуры исходя из статистического распределения данных которые через нее будут проходить и желаемой точности, универсальные коды тут и по длине и по вычислениям могут быть не оптимальны
popcount = 2 → читай пока не встретишь 2 единицы
Это опечатка? Тут вроде 5.
По технологии: почему у вас одно из значений base-префикса не используется (00)? Почему бы не сделать "repeating until the value is ≤ 4"?
"Decoding Steps" — как понять, что кодирование закончилось? Встретили мы единицу: это новый блок или terminator?
01 100000000000 1 ^^ ^ K=1 терминатор Одна единица в данных → читаем до неё → готово. Число 2048 закодировано в 15 бит. В u16 оно стоило бы 16. Число 4294967296 закодировалось бы в 35 бит. В u64 стоит 64.
А вот тут совсем не понятно. Читаем до 1 единицы. Так, единица же в самом начале, почему мы должны читать ещё 11 нулей? Или у вас тут перевёрнуто?
Вам бы, конечно, несколько примеров привести. По паре штук хотя бы где только база, где +1 popcount, +2 popcount. И без опечаток.
И заодно интересно, как кодировать 0? Или мы работаем только с натуральными числами?
Не могли бы вы привести побольше примеров кодирования и формализовать алгоритм?
Нулевой терминатор в рекурсином коде работает, только потому что все записанные числа всегда начинаются с 1. У вас же числа могут начинаться и с 0 (ведь они развернутые). А так вы не можете различить 30 и 4.
30:
01 <- 1 единица
001 <- 4 единицы
01111 <- 30 задом на перед
0 - терминатор.
4:
01 <- 1 единица
001 <- число 4
0 <- терминатор.
Тут код для 4 является префиксом кода для 30.
Или у вас код не рекурсивный? А зачем тогда вообще терминатор?
Вообще, вы прогоняли тесты? Закодируйте вашим алгоритмом все числа до 100000 хотя бы и проверьте, что все раскодируется обратно.
Прогонял, собственно и ссылка на репозиторий есть.
Код рекурсивный, данные разворачивать не надо - после них и так терминатор, разворот происходит только у кодов, сделать я это могу потому что последовательность чисел монотонно возрастает, и начинаются потому все числа всегда на единицу - которую я и использую как терминатор
Формализуйте, пожалуйста, алгоритм.
В обратном порядке:
0101 0110 - исходные данные, 4 единицы
100 - 4, означает число единиц у верхнего уровня
01 - 1, число единиц верхнего уровня
Первые два бита переворачивать не надо, так как декодер и так знает что ему читать ровно два бита.
Второй уровень(и любые следующие, кроме данных) всегда начинается на 1, так как должны быть строго больше прошлого (иначе нет смысла от нового уровня).
Таким образом единица в начале каждого уровня очевидна и хранить ее не обязательно, но нам нужен терминатор.
Поэтому мы переворачиваем коды каждого уровня кроме первого и самих данных, чтобы эта единица была в конце и декодер читал все до нее.
Итого имеем 01 001 01010110 1
Вы понимаете, что значит "формализовать алгоритм"?
Я все еще явно не понимаю ваш алгоритм, потому что то, что я понял, не работает.
Я вижу что "100" вы записали развернутыми. А сами данные и первый блок - нет. Видимо, все остальные блоки идут задом-наперед. Но вот при чтении второго блока вы заканчиваете сразу на первой единице (потому что их должно быть 1 в блоке). А при чтении третьего блока (с данными) вы заканчиваете перед 5-той единицей. Как вы определяете когда хватит читать блок?
Закодируйте, пожалуйста, данные 1111. Там же будет 01 001 1111 1?
Блоки наоборот будут:
1111 - данные.
100 - там 4 единицы
01 база.
А как будет тогда 111111111111111 (15 единиц)? Не 01 001 1111 111111111111111 1?
Извините за путаницу, в статье забыл написать про унарный префикс, который обозначает число блоков кодирования. Но в бенчмарке он учтен. Т. е. у вас все правильно, но терминатор не нужен, а нужно перед кодом 1110 = 3 написать, число блоков кода: 110 01 001 1111 111111111111111 Псевдокод:
decode(stream):
read unary -> num_blocks
read 2 bits -> current_val
repeat num_blocks times:
ones_needed = current_val
value = 0
pos = 0
while ones_counted < ones_needed:
bit = read 1 bit
if bit == 1:
value |= (1 << pos)
ones_counted += 1
pos += 1
while true:
bit = read 1 bit
if bit == 1:
value |= (1 << pos)
break
pos += 1
current_val = value
return current_val
Блин, ну как можно это забыть? Это вообще другой подход же.
Вам этот алгоритм нейросетка нагенерила и вы его даже не читали досконально?
Но это работает, да. Только еще отличие от предыдущих ваших сообщений: данные тоже должны быть развернуты в потоке. Потому что при чтении блока вы всегда читаете до последней единицы (а еще вы храните не количество единиц, а количество минус 1). Если данные заканчиваются на 0, то этот алгоритм не может их прочитать, но развернутые данные всегда кончаются старшим значимым разрядом.
Теперь, когда я понял ваш метод, я могу выдать свое мнение. Напишу отдельным комментарием.
Идея интересная, но практической и теоретической ценности несет мало.
Метод еще более рекурсивный и медленный в чтении чем другие коды. Тут как минимум один лишний блок есть всегда (для записи количества блоков). А главное, никак нельзя читать несколько бит сразу. Даже если что-то с look-ahead хитрое сделать и считать количество бит в прочитанном спекулятивно куске, то все равно в конце придется все биты разворачивать. Это ужасно медленно. Обрезать прочитанное машинное слово можно за пару битовых операций, перевернуть его - это кошмар.
Если же вам не важна скорость декодирования, то вместо вашего метода можно использовать какое-нибудь сжатие и оно будет на порядки более компактно вашего метода (да и других универсальных кодов). Поэтому практической пользы тут мало.
С теоретической точки зрения тут тоже проблемы: ваш метод точно должен проигрывать Омега коду Элиаса во многих случаях, потому что экономия от записи количества единиц вместо длины не всегда большая, а дополнительные биты от унарного количества блоков есть всегда.
В некоторых случаях, ваш метод выигрывает, да. Но чисел, где не менее половины единичных бит - больше половины среди всех 2^n-1 чисел длины n.
Для этих чисел вы экономите не более одного бита в блоке (ведь вы записываете половину от длины числа), но вы всегда тратите один бит на количество блоков. Т.е. для подавляющего большинства длинных чисел вы тратите больше, чем экономите.
В среднем, чем больше блоков - тем хуже ваш метод. Т.е. чем больше число, тем хуже.
Конечно, для каких-то конкретных примеров ваш код лучше. Но с теоретической точки зрения важна ассимптотика и для каких распределений ваш код оптимален. Так вот, с асимптотикой тут все плохо, по крайней мере не лучше чем у Омега кода.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Мой универсальный код