Мой универсальный код

Зачем я переплачиваю 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 и протестировано на миллионе чисел.

Число 1 у меня — 4 бита. У VByte — 8 бит. Число 1024 у меня — 14 бит. У VByte — 16 бит. На маленьких числах (а дельты в поисковых индексах почти всегда маленькие) разница огромная.

Round-trip тестирование пройдено для всех значений вплоть до u64::MAX.

Реализация

Рабочий MVP на Rust лежит на GitHub, лицензия MIT. Код, бенчмарки, PDF с доказательством — всё там:

GitHub — Permyakov Code

P.S. Хочу опубликовать теорию в научном журнале или на arXiv — PDF с доказательством строгого доминирования уже готов. Если у вас есть возможность помочь с эндорсментом на arXiv (cs.IT / cs.DS) или вы знаете подходящий журнал — буду очень благодарен, пишите в личку!