Зачем я переплачиваю 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) или вы знаете подходящий журнал — буду очень благодарен, пишите в личку!
