Зачем я переплачиваю 31 бит на число 1?
Зачем на число 1 я в типах u8, u16, u32 и так далее переплачиваю 7, 15 и 31 бит? Это же бред.
Однозначность декодирования? Быстрая адресация? Сейчас распишу до чего я допёр.
Проблема
Если биты лежат в потоке, то не совсем понятно что они значат без предварительной договорённости. Например:
1110101011
Что это? Одно число? Два? Бог его знает. Без какого-то знания начального подойти к данным не выйдет (я работаю над этим :D).
Можно заранее договориться читать кусками по 8, 16 или 32 бит — тогда ничего не надо придумывать, тупо читай. Но тогда платишь налог на ненужные биты и возможны переполнения. В целом для прикладных задач этого кому-то хватает.
Но я люблю хардкор.
Кодируем длину рядом с данными
Я подумал: а почему бы не записывать длину рядом с данными? Тогда декодер знает сколько бит читать.
Самый тупой способ — унарный код: ставим нолики перед числом, сколько ноликов — столько бит в числе:
0 1 ← один ноль: число из 1 бита → "1" → число 1 00 10 ← два ноля: число из 2 бит → "10" → число 2 000 101 ← три ноля: число из 3 бит → "101" → число 5 0000 1100 ← четыре ноля: число из 4 бит → "1100" → число 12
Работает! Но оверхед — ровно n бит на число длины n. Число из 20 бит потребует 20 нолей перед ним. Мерзкая линейность!
Рекурсия спасает
А что если длину тоже кодировать чем-то компактным? Длина числа 1100 — это 4. Четвёрку можно записать в 2 бита: 100. А длину четвёрки — в 1 бит…
Если так рекурсивно продолжить, то упрёмся в стартовые два бита — потому что только два бита могут закодировать длину больше своей (2 бита кодируют числа до 3, а 3 > 2).
Пример: кодируем число 12 (1100, длина 4):
Цепочка длин: 4 → 2 (длина четвёрки) → стоп (2 влезает в 2 бита) Записываем: 11 ← база: число 3 (говорит "следующий блок из 3 бит") 100 ← число 4 (говорит "следующий блок из 4 бит") 1100 ← само число 12 0 ← терминатор "конец" Итого: 10 100 1100 0 = 10 бит на число 12 Фикса u8 потратила бы 8, но на больших числах рекурсия выигрывает
Поздравляю, мы с вами придумали омега-кодирование Элиаса (1975)!
Оно довольно неплохое, оверхед на число длины n бит:
А если кодировать не длину, а число единиц?
Но я подумал: а почему бы не кодировать не длину, а число единиц (popcount)?
В худшем случае когда все биты — единицы, popcount = длина. Деградация до омеги, которая и так хорошая.
Но в лучшем случае — ммм… Допустим, число 10000000000 (1024). Длина — 11 бит. А единица в нём — всего одна!
Омега кодирует длину 11 → рекурсия на 11, потом на 3, потом база. Много уровней. Мой код кодирует popcount 1 → это сразу влезает в базу из 2 бит. Один уровень!
Вот как это работает пошагово:
Кодируем число 1024 = 10000000000 (11 бит, popcount = 1) Шаг 1: popcount = 1, влезает в 2 бита → база = 01 Шаг 2: записываем число задом наперёд: 00000000001 (реверс нужен чтобы декодер мог считать единицы — последняя единица всегда MSB, он до неё дочитает и остановится) Шаг 3: терминатор = 1 Итого: 01 00000000001 1 = 14 бит u16 потратил бы 16 бит. Мы сэкономили.
А теперь большое число: 10000000000000000000001000000000000001 (попробуйте в u64!):
Длина: 35 бит. Единиц: всего 3. Шаг 1: popcount = 3 → база = 11 (два бита) Шаг 2: число задом наперёд (35 бит) Шаг 3: терминатор = 1 Итого: 11 + 35 + 1 = 38 бит u64 потратил бы 64 бита. Экономия 26 бит!
Почему терминатор вообще работает? Мы перед данными написали число единиц, которое надо прочитать декодеру, значит первая единица которая нарушает это число - терминатор.
Фишка: чем ближе число к степени двойки (мало единиц) — тем меньше метаданных. Я могу конечным числом бит описать декодеру сколь угодно длинное число.
А в худшем случае (все биты единицы)? Popcount = длина, и мой код работает ровно как омега. Никогда не хуже!
А что с VByte?
Кстати, помните унарную длину из начала? 000 101 — три нуля говорят “читай 3 бита”. Это и есть гамма-кодирование Элиаса: длина унарно + данные. Просто и рабочее, но линейный оверхед.
VByte (LEB128/Varint) — это по сути то же самое гамма-кодирование, только каждый бит гаммы кодирует 7 битов длины а не 1. В целом для большинства задач этого хватает.
Но всё равно рост оверхеда линейный: 1 бит на каждые 7 бит данных = 14.3% налог навсегда. И число 1 всё равно стоит минимум 8 бит.
У меня число 1 стоит 4 бита. Число 2 — тоже 4 бита.
Единственная проблема
Единственная проблема моего подхода, как и любого рекурсивного универсального кода — нельзя просто прыгнуть по индексу в потоке и прочитать.
НО. Никто не мешает хранить, например, индекс каждого 16-го узла в той же кодировке. И индексы каждого 16-го индекса. И так далее. В таком случае навигация становится 
, а индекс весит крохи по сравнению с самими данными.
Вот такие фокусы!
Бенчмарки
Я не просто теоретизирую — всё реализовано на Rust и протестировано на миллионе чисел.
Что сравниваем |
Результат |
|---|---|
Оверхед метаданных vs Elias Omega |
на 36% меньше |
Размер vs VByte на плотных дельтах (с индексом) |
в 1.55 раза компактнее |
Сырые данные (дельты ~2) vs VByte |
в 2 раза компактнее |
Число 1 у меня — 4 бита. У VByte — 8 бит. Число 1024 у меня — 14 бит. У VByte — 16 бит. На маленьких числах (а дельты в поисковых индексах почти всегда маленькие) разница огромная.
Round-trip тестирование пройдено для всех значений вплоть до u64::MAX.
Реализация
Рабочий MVP на Rust лежит на GitHub, лицензия MIT. Код, бенчмарки, PDF с доказательством — всё там:
P.S. Хочу опубликовать теорию в научном журнале или на arXiv — PDF с доказательством строгого доминирования уже готов. Если у вас есть возможность помочь с эндорсментом на arXiv (cs.IT / cs.DS) или вы знаете подходящий журнал — буду очень благодарен, пишите в личку!
Комментарии (20)
JBFW
19.05.2026 13:11Откуда-то из леса раздается эхо: код Хаффмана, Рида-Соломона...
Это большая развесистая тема, как можно кодировать поток, избегая передачи лишних бит, но не забывая о помехозащищённости..
Во времена медленных аналоговых модемов было очень востребовано. На канальном уровне OSI оно и сейчас все используется, на прикладном как бы нет необходимости, а микроконтроллеры на Rust вроде пока ещё не программируют
MaxLenPer Автор
19.05.2026 13:11Так я же про хранение написал. О сжатии и передаче даже не заикался!
При чем тут Хаффман и Соломон то…
но тема действительно интересная)
Upd: на счет микроконтроллеров - есть no_std, но если очень хочется переписать на C, 400 строк по образцу написать нынче дело очень простое
Jijiki
19.05.2026 13:11не только, как я понял мы стартуем с самого простого, распологаем в регистр всю инфу - тоесть пакуем битами например в u32/u64/u128 - с u32 выгодно пока инфа влезает в 4 байта и тд, в вокселях встретить можно, суть в том что на координаты и прочие метки памяти типо больше расходуется, так например, координаты, свет, ао, угол - номер вершины, текстуру - id, можно запаковать... оно прикольно работает, но это не новое прям уж чтобы, ну и да там наверно сверху еще дожать можно даже простым каким-нибудь стоковым RLE сжатием и не только..., вот например закинуть это всё в текстуру и запаковать jpegxl ну я предположил может так и нельзя )
ну и соотв, если инфы меньше можно и в u8 всё закидывать, но без координат тогда, если про воксели )
зы, сразу отвечу, вам придётся или процессору или компилятору всё это приводить к одному знаменателю, поэтому данные такие потоковые придётся уплотнять 1 длинной регистра типо
обычно приходят типо к проблеме, переменная длинна таких данных и проводка их по переменной памяти, а вы пошли еще глубже переменная длинна битности, но максимум будет выборкой тогда поидее, тоесть поидее если максимальная последовательность уложилась в 128 лучше в 128 наверно укладывать, или если в 32 в 32 тогда укладывать.
вот пример, чанк 16х16х16 он проходит по u32, и добирает метаданными в себя, но шум в чанк переменной длинны и доступны прыжки по кускам памяти, которые берутся из генератора фиксированной длинны 4096 - типо 1 чанк, проблема в том, что проводить память по чанкам с шумом и есть та проблема, которую надо решить при проводке такой памяти.
MaxLenPer Автор
19.05.2026 13:11Я так понял ты про упаковать несколько чисел в один u32/u64/u128? Когда ты знаешь заранее что и как кладешь и тебе все считать на видеокарте - то так и надо
Но суть моего кода в том, что ты пишешь биты не по фиксированной раскладке фиксированной длины, а сколько надо - столько и пишешь, отсюда и появляется проблема неоднозначности декодирования, которую решают универсальные коды типа моего.
Jijiki
19.05.2026 13:11возможно вы правы, мне показалось вы что-то тривиальное сделали, а вы сравнивали как ваше работает по сравнению с задачей где выбираем упаковку и сверху дожимаем например RLE, не будет ли там тоже самое?
тоесть получается, если это перенести на картинку, то ячейка RGB не фиксированная, мы танцуем от размера по месту? а как память выделять будем? поидее же надо, чтобы было красиво, как-то параметризировать и выделить 1 большой кусок посчитать и раскодировать и освободить память или нет?
ну типо есть пнг, но можно и тга использовать, разницы нету в целом если нужна именно картинка, да и плюс есть jpgxl уже который вроде даже лучше пнг уже работает.
я щас задумался, у меня в демке мир сохраняется кусками по 4096кб, я так задумался, в разрезе со взглядом на сравнение пнг и тга очень похоже, по-сути разницы нету. ну выигрываем 3кб или 80% это много на масштабе?
--
не в тему кстати еще добавлю если ищем что-то классное и хочется не С/С++ есть еще зиг, там comptime интересный, может поможет), но я запускал одну демку на нём, разницы не заметил - типо по моим интересам в другой задачке всё так же бодро работает как в Расте ), но механики и задумка там интересные
titbit
19.05.2026 13:11Конструкция прикольная, но что если битовый поток начинается с двух нолей? Еще к недостаткам я бы отнес использование непредсказуемого числа раз popcount при кодировании, тем более что не везде эта операция аппаратно ускорена. И невозможность заранее быстро оценить сколько займет закодированное значение, это тоже бывает важно при расчете “стоимости” хранения, когда есть выбор как кодировать.
p.s. например есть же всякие дельта коды, которые по сути гамма, у которых экспонента тоже закодирована гамма кодом - вполне себе похожие конструкции получаются.
MaxLenPer Автор
19.05.2026 13:1100 - 0 единиц, можно кодировать сколько угодно нулей, если не нужно - всегда можно сдвинуть все числа и назначить на 00 одну единицу или что то другое вообще
Насчет оценки сколько попкаунтов. Верхняя оценка - столько же сколько и у омеги, а точно без попкаунтов посчитать и не выйдет
Если надо выбирать из нескольких стратегий то надо их как то кодировать по идее log2(число стратегий) битами, или заранее выбрать одну - смотря какие числа чаще будут встречаться, на 16к-2кк vbyte самый вкусный потому что паддинг нули почти пропадают в процентном соотношении а сумма битовых флагов еще более менее сравнима с омегой
По факту для маленьких штучек лучше писать фиксированные кастомные структуры исходя из статистического распределения данных которые через нее будут проходить и желаемой точности, универсальные коды тут и по длине и по вычислениям могут быть не оптимальны
jin_x
19.05.2026 13:11По технологии: почему у вас одно из значений 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? Или мы работаем только с натуральными числами?
MaxLenPer Автор
19.05.2026 13:11Поправил примерчики, опечаток не было - просто неочевидные формулировки.
Читаем мы не до одной единицы, а до следующей после закодированной, иначе все нули не учитывались бы. Если бы мы заранее знали что все данные, которые мы кодируем заканчиваются на 1 - могли бы сэкономить бит на терминаторе.
wataru
19.05.2026 13:11Не могли бы вы привести побольше примеров кодирования и формализовать алгоритм?
Нулевой терминатор в рекурсином коде работает, только потому что все записанные числа всегда начинаются с 1. У вас же числа могут начинаться и с 0 (ведь они развернутые). А так вы не можете различить 30 и 4.
30:
01 <- 1 единица
001 <- 4 единицы
01111 <- 30 задом на перед
0 - терминатор.
4:
01 <- 1 единица
001 <- число 4
0 <- терминатор.
Тут код для 4 является префиксом кода для 30.
Или у вас код не рекурсивный? А зачем тогда вообще терминатор?
Вообще, вы прогоняли тесты? Закодируйте вашим алгоритмом все числа до 100000 хотя бы и проверьте, что все раскодируется обратно.
MaxLenPer Автор
19.05.2026 13:11Прогонял, собственно и ссылка на репозиторий есть.
Код рекурсивный, данные разворачивать не надо - после них и так терминатор, разворот происходит только у кодов, сделать я это могу потому что последовательность чисел монотонно возрастает, и начинаются потому все числа всегда на единицу - которую я и использую как терминатор
wataru
19.05.2026 13:11Формализуйте, пожалуйста, алгоритм.
MaxLenPer Автор
19.05.2026 13:11В обратном порядке:
0101 0110 - исходные данные, 4 единицы
100 - 4, означает число единиц у верхнего уровня
01 - 1, число единиц верхнего уровня
Первые два бита переворачивать не надо, так как декодер и так знает что ему читать ровно два бита.
Второй уровень(и любые следующие, кроме данных) всегда начинается на 1, так как должны быть строго больше прошлого (иначе нет смысла от нового уровня).
Таким образом единица в начале каждого уровня очевидна и хранить ее не обязательно, но нам нужен терминатор.
Поэтому мы переворачиваем коды каждого уровня кроме первого и самих данных, чтобы эта единица была в конце и декодер читал все до нее.
Итого имеем 01 001 01010110 1
wataru
19.05.2026 13:11Вы понимаете, что значит "формализовать алгоритм"?
Я все еще явно не понимаю ваш алгоритм, потому что то, что я понял, не работает.
Я вижу что "100" вы записали развернутыми. А сами данные и первый блок - нет. Видимо, все остальные блоки идут задом-наперед. Но вот при чтении второго блока вы заканчиваете сразу на первой единице (потому что их должно быть 1 в блоке). А при чтении третьего блока (с данными) вы заканчиваете перед 5-той единицей. Как вы определяете когда хватит читать блок?
Закодируйте, пожалуйста, данные 1111. Там же будет 01 001 1111 1?
Блоки наоборот будут:
1111 - данные.
100 - там 4 единицы
01 база.
А как будет тогда 111111111111111 (15 единиц)? Не 01 001 1111 111111111111111 1?
MaxLenPer Автор
19.05.2026 13:11Извините за путаницу, в статье забыл написать про унарный префикс, который обозначает число блоков кодирования. Но в бенчмарке он учтен. Т. е. у вас все правильно, но терминатор не нужен, а нужно перед кодом 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_valwataru
19.05.2026 13:11Блин, ну как можно это забыть? Это вообще другой подход же.
Вам этот алгоритм нейросетка нагенерила и вы его даже не читали досконально?
Но это работает, да. Только еще отличие от предыдущих ваших сообщений: данные тоже должны быть развернуты в потоке. Потому что при чтении блока вы всегда читаете до последней единицы (а еще вы храните не количество единиц, а количество минус 1). Если данные заканчиваются на 0, то этот алгоритм не может их прочитать, но развернутые данные всегда кончаются старшим значимым разрядом.
Теперь, когда я понял ваш метод, я могу выдать свое мнение. Напишу отдельным комментарием.
wataru
19.05.2026 13:11Идея интересная, но практической и теоретической ценности несет мало.
Метод еще более рекурсивный и медленный в чтении чем другие коды. Тут как минимум один лишний блок есть всегда (для записи количества блоков). А главное, никак нельзя читать несколько бит сразу. Даже если что-то с look-ahead хитрое сделать и считать количество бит в прочитанном спекулятивно куске, то все равно в конце придется все биты разворачивать. Это ужасно медленно. Обрезать прочитанное машинное слово можно за пару битовых операций, перевернуть его - это кошмар.
Если же вам не важна скорость декодирования, то вместо вашего метода можно использовать какое-нибудь сжатие и оно будет на порядки более компактно вашего метода (да и других универсальных кодов). Поэтому практической пользы тут мало.
С теоретической точки зрения тут тоже проблемы: ваш метод точно должен проигрывать Омега коду Элиаса во многих случаях, потому что экономия от записи количества единиц вместо длины не всегда большая, а дополнительные биты от унарного количества блоков есть всегда.
В некоторых случаях, ваш метод выигрывает, да. Но чисел, где не менее половины единичных бит - больше половины среди всех 2^n-1 чисел длины n.
Для этих чисел вы экономите не более одного бита в блоке (ведь вы записываете половину от длины числа), но вы всегда тратите один бит на количество блоков. Т.е. для подавляющего большинства длинных чисел вы тратите больше, чем экономите.
В среднем, чем больше блоков - тем хуже ваш метод. Т.е. чем больше число, тем хуже.
Конечно, для каких-то конкретных примеров ваш код лучше. Но с теоретической точки зрения важна ассимптотика и для каких распределений ваш код оптимален. Так вот, с асимптотикой тут все плохо, по крайней мере не лучше чем у Омега кода.
danilovmy
А что там с отрицательными значениями? Или я упустил?
MaxLenPer Автор
Биты они и есть биты) универсальный же код!
Upd: если мы знаем еще что это вдобавок и число то можно еще бит сэкономить не тратя память на очевидную первую единицу
На счет отрицательных я сейчас подумал и можно 1 бит флаг писать в конец перед терминатором, но вообще это зависит от того как вы отрицательные числа кодируете, флагом в начале или по стандарту который сейчас везде