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

Зачем я переплачиваю 31 бит на число 1?

Зачем на число 1 я в типах u8, u16, u32 и так далее переплачиваю 7, 15 и 31 бит? Это же бред.

Однозначность декодирования? Быстрая адресация? Сейчас распишу до чего я допёр.

Проблема

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

1110101011

Что это? Одно число? Два? Бог его знает. Без какого-то знания начального подойти к данным не выйдет (я работаю над этим :D).

Можно заранее договориться читать кусками по 8, 16 или 32 бит — тогда ничего не надо придумывать, тупо читай. Но тогда платишь налог на ненужные биты и возможны переполнения. В целом для прикладных задач этого кому-то хватает.

Но я люблю хардкор.

Кодируем длину рядом с данными

Я подумал: а почему бы не записывать длину рядом с данными? Тогда будет понятно сколько читать после. Но как кодировать саму длину? Фиксой? Некрасиво.

Можно в унарной системе нулями просто обозначать длину:

000 101
^^^
длина = 3 бита → читаем "101" → число 5

Но это всегда n бит оверхеда. Мерзкая линейность!

Рекурсия спасает

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

Поздравляю, мы придумали омега-кодирование Элиаса (1975)!

Оно довольно неплохое, оверхед на битовую строку длины n:

А если кодировать не длину, а число единиц?

Но я подумал: а почему бы не кодировать не длину, а число единиц (popcount)?

В худшем случае когда все биты — единицы, мы получим саму длину. Деградация до омеги, которая и так очень хорошая.

Но в лучшем случае — ммм…

Следите за руками:

10 101 1110000000000000000000001000000000000001 1
^^                                              ^
2 бита базы                               терминатор
   ^^^
   popcount = 2 → читай пока не встретишь 2 единицы
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
       вот наше число, и нулей тут СКОЛЬКО ХОЧЕШЬ

Я могу конечным числом метаданных описать декодеру сколь угодно длинное число, причём чем ближе число к степени двойки — тем меньше мне надо бит на метаданные!

И не обязательно на втором уровне, можно прямо с первого наглеть:

01 100000000000 1
^^              ^
K=1          терминатор

Одна единица в данных → читаем до неё → готово.
Число 2048 закодировано в 15 бит. В u16 оно стоило бы 16.
Число 4294967296 закодировалось бы в 35 бит. В u64 стоит 64.

А что с 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 ^[1]

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