Коды целых чисел: разности, гамма Элиаса, Райс и varint

Если ты знаешь, зачем хранить разности, как устроены гамма Элиаса, код Райса и varint и какой когда брать, листай до «Теперь сам».

Как думаешь, сколько бит нужно на номер документа

Слово встречается в 20 тысячах документов из десяти миллионов. Список номеров: 437, 1012, 1203, 2899, …. По 32 бита на номер - 640 тысяч бит.

Прежде чем читать дальше, ответь себе: номера отсортированы, и в среднем соседние отличаются на 500. Сколько бит нужно, чтобы записать число около 500? И как декодеру понять, где кончается одно число и начинается следующее, если у них разная длина?

На что это похоже

Журнал пробега машины. Можно записывать каждый раз показание одометра целиком: 128 437, 128 512, 128 601. Можно записывать, сколько проехал с прошлой записи: 75, 89 - короче в разы, а одометр восстанавливается сложением. Остаётся договориться, как писать числа разной длины подряд без разделителей, - и каждый код целых чисел это своя договорённость.

Механизм: разности и три кода

РАЗНОСТИ: d_1 = a_1 + 1,  d_i = a_i − a_(i−1)  (все ≥ 1 при различных a)
восстановление: префиксные суммы

ГАММА ЭЛИАСА, x ≥ 1:  (длина двоичной записи − 1) нулей + двоичная запись
    1 → 1,  2 → 010,  5 → 00101,  500 → 00000000111110100
    длина 2·⌊log₂ x⌋ + 1; декодер считает нули и читает на 1 бит больше

ГОЛОМБ-РАЙС с параметром k:  q = (x − 1) // 2^k,  r = (x − 1) % 2^k
    q единиц, ноль, затем r ровно k битами
    k = 8: 500 → q = 1, r = 243 → 10 11110011  (10 бит)
    хорош, когда разности примерно одного порядка: 2^k ≈ 0.69 · среднее

VARINT: число по 7 бит, в каждом байте старший бит = «дальше есть байт»
    500 = 3·128 + 116 → байты [116 + 128, 3] - 2 байта, 16 бит
    кратно байтам - декодер не возится с битами

Откуда 0.69: если номера разбросаны случайно, малые разности встречаются чаще больших, и вероятность падает с ростом разности по показательному закону; для таких данных лучший параметр кода Голомба - около ln 2 · среднее. Предел сжатия для таких разностей - примерно log₂(e · среднее) бит, для среднего 500 это 10.4; код Райса приходит почти к нему.

Правило

Отсортированные номера хранят разностями: числа маленькие, порядок восстанавливается сложением. Разности кодируют кодом переменной длины без таблицы: гамма Элиаса - 2·log₂ x + 1 бит, без параметров; Голомб-Райс - частное унарно и k бит остатка, с 2^k ≈ 0.69 · среднее почти достигает предела; varint - по 7 бит в байт с флагом продолжения, хуже по размеру, но быстрее и выровнен по байтам.

Разбор: пять номеров тремя способами

номера: 3 7 8 20 21     разности: 4 4 1 12 1

гамма:  4 → 00100   4 → 00100   1 → 1   12 → 0001100   1 → 1
        00100 00100 1 0001100 1           = 19 бит
Райс k = 2:  x − 1 = 3, 3, 0, 11, 0
        3 → 0 11,  3 → 0 11,  0 → 0 00,  11 = 2·4 + 3 → 110 11,  0 → 0 00
        011 011 000 11011 000             = 17 бит
varint: каждая разность меньше 128 → по байту, 5 байт = 40 бит
по 32 бита: 160 бит

Декодирование гаммы: 00100 - два нуля, значит дальше три бита 100 = 4. Код Райса: единицы до нуля - частное, затем ровно k бит - остаток. Ни одному коду не нужны разделители.

Разбор: список из двадцати тысяч номеров

Программа берёт 20 тысяч случайных номеров из десяти миллионов, кодирует разности тремя способами, раскодирует и сверяет, затем сравнивает размеры.

import random

rng = random.Random(32)
dokumenty = sorted(rng.sample(range(10 ** 7), 20000))   # где есть слово
raznosti = [dokumenty[0] + 1] + [b - a for a, b in
                                 zip(dokumenty, dokumenty[1:])]


def gamma(x):                         # Элиас: нули + двоичная запись
    b = format(x, "b")                # x ≥ 1
    return "0" * (len(b) - 1) + b


def iz_gamma(bity, i):
    nuli = 0
    while bity[i + nuli] == "0":
        nuli += 1
    return int(bity[i + nuli:i + 2 * nuli + 1], 2), i + 2 * nuli + 1


def rajs(x, k):                       # Голомб-Райс: частное x // 2^k
    q, r = divmod(x - 1, 2 ** k)      # единицами, остаток - k битами
    return "1" * q + "0" + format(r, f"0{k}b")


def iz_rajsa(bity, i, k):
    q = 0
    while bity[i + q] == "1":
        q += 1
    r = int(bity[i + q + 1:i + q + 1 + k], 2)
    return q * 2 ** k + r + 1, i + q + 1 + k


def varint(x):                        # по 7 бит в байт, старший бит -
    out = []                          # «дальше ещё байт»
    while True:
        x, b = divmod(x, 128)
        out.append(b + (128 if x else 0))
        if not x:
            return out


def raspakovat(potok, chitat):
    i, chisla = 0, []
    while i < len(potok):
        x, i = chitat(potok, i)
        chisla.append(x)
    return chisla


srednee = (dokumenty[-1] + 1) / len(dokumenty)
k = len(format(round(srednee * 0.69), "b")) - 1   # 2^k ≈ 0.69·среднее
g = "".join(map(gamma, raznosti))
r = "".join(rajs(x, k) for x in raznosti)
v = [b for x in raznosti for b in varint(x)]
assert raspakovat(g, iz_gamma) == raznosti
assert raspakovat(r, lambda p, i: iz_rajsa(p, i, k)) == raznosti
print(f"номеров {len(dokumenty)}, средняя разность {srednee:.0f},"
      f" k = {k}")
for imya, bit in (("по 32 бита", 32 * len(dokumenty)),
                  ("разности + varint", 8 * len(v)),
                  ("разности + гамма", len(g)),
                  ("разности + Райс", len(r))):
    print(f"{imya:18} {bit:7} бит,"
          f" {bit / len(dokumenty):5.1f} на номер")

номеров 20000, средняя разность 500, k = 8
по 32 бита          640000 бит,  32.0 на номер
разности + varint   284184 бит,  14.2 на номер
разности + гамма    326156 бит,  16.3 на номер
разности + Райс     209875 бит,  10.5 на номер

Разности ужали список втрое уже простым varint. Гамма здесь хуже varint: она не знает, что числа около 500, и тратит на длину столько же бит, сколько на само число. Код Райса с подобранным k дал 10.5 бита на номер - в трёх десятых бита от предела 10.4.

Что ломается без этого

Первая ошибка - кодировать сами номера, а не разности: номера огромные, и никакой код переменной длины не поможет. Вторая - подобрать k у Райса не по данным: при k слишком малом частное становится длинным унарным хвостом, при слишком большом остаток тратит лишние биты на каждом числе. Третья - гамма для нуля: она начинается с единицы, и ноль надо сдвигать (x + 1); у разностей различных номеров нулей нет, а у разностей с повторами - есть. Четвёртая - читать varint, забыв про флаг продолжения на последнем байте: декодер «съест» следующий номер.

Зачем это в работе

Инвертированные индексы поисковиков и баз данных (Lucene, Elasticsearch) хранят списки документов разностями с битовой упаковкой и кодами вроде Райса. varint - формат целых в Protocol Buffers, в сетевых протоколах и в файлах SQLite. Коды Голомба сжимают без потерь звук (FLAC) и изображения (JPEG-LS), где остатки предсказания малы. Разности перед сжатием - стандартный ход для отметок времени, координат треков, показаний датчиков: соседние значения близки, и сжимать надо изменение, а не значение.

Теперь сам

Закодируй число 9 гаммой Элиаса и кодом Райса с k = 2. Какой код короче?