Арифметическое кодирование: меньше бита на символ

Если ты сузишь отрезок для сообщения aab, объяснишь, почему число бит равно логарифму от ширины, и скажешь, что в настоящих кодировщиках заменяет дроби неограниченной точности, - листай до «Теперь сам».

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

В сообщении два символа: a в 95 позициях из ста, b в пяти. Энтропия - 0,29 бита на символ. Код Хаффмана даёт a код 0, а b код 1: один бит на символ, в три с половиной раза больше энтропии. И короче одного бита код символа быть не может.

Прежде чем читать дальше, подумай: как вообще можно потратить на символ ТРЕТЬ бита? Запись состоит из целых битов. Что должно измениться в самом способе кодирования, чтобы дробные биты получили смысл?

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

Представь почтовый адрес. Страна, область, город, улица, дом: каждое слово сужает место на карте. Но сужает по-разному. «Москва» отсекает меньше, чем название деревни, - в Москве живёт каждый десятый, и письму туда хватило бы совсем короткой пометки. Название деревни отсекает почти всё, и за такое уточнение приходится платить длинным словом.

Адрес не кодирует каждое слово отдельным ящиком фиксированного размера. Он задаёт одну точку на карте, и длина всей записи зависит от того, насколько мала итоговая область. Частое уточнение сужает слабо и стоит дёшево - в том числе меньше одного знака.

Механизм: отрезок, который сужается

Договоримся, как делить отрезок: каждому символу - часть, пропорциональная его доле. Пусть a - три четверти, b - одна четверть, и a занимает нижнюю часть.

Кодируем aba. Начинаем с отрезка от 0 до 1. Каждый символ выбирает свою часть текущего отрезка, и дальше делится уже она - в тех же пропорциях. В записи отрезка квадратная скобка значит «граница входит», круглая - «не входит»: число 3/4 принадлежит уже части символа b.

начало                    [0,      1)          ширина 1
символ a - нижние 3/4     [0,      3/4)        ширина 3/4
символ b - верхняя 1/4    [9/16,   3/4)        ширина 3/16
символ a - нижние 3/4     [9/16,   45/64)      ширина 9/64

Ширина на каждом шаге умножается на долю символа: 3/4 · 1/4 · 3/4 = 9/64. Любое число из итогового отрезка однозначно называет сообщение aba: другое сообщение той же длины попало бы в другой отрезок, и отрезки разных сообщений не пересекаются.

Осталось назвать число. Двоичная дробь читается как десятичная, только разряды после запятой - половина, четверть, восьмая. Возьмём 5/8 = 1/2 + 1/8 - в двоичной записи 0,101. Оно лежит между 9/16 = 0,5625 и 45/64 ≈ 0,703. В код идут цифры после запятой: три бита 101 - и сообщение закодировано.

Сколько бит нужно в общем случае. Двоичные дроби из k бит стоят на числовой прямой с шагом 1/2ᵏ. Чтобы хоть одна наверняка попала в отрезок ширины w, шаг должен быть не больше w: 2ᵏ ≥ 1/w, то есть k ≥ log₂(1/w). Логарифм здесь - число удвоений точности, нужное, чтобы сетка стала мельче отрезка.

И последний шаг - откуда энтропия. Ширина - произведение долей, а логарифм произведения равен сумме логарифмов: чтобы сетка стала мельче произведения двух долей, её надо удвоить столько раз, сколько нужно для первой доли, и ещё столько, сколько для второй. Значит, каждый символ с долей p добавляет к длине кода log₂(1/p) бит. Символ с долей p встречается в сообщении длины n примерно p · n раз, и сумма по всему сообщению равна n · Σ p · log₂(1/p) - энтропии, умноженной на длину.

Правило

Ширина итогового отрезка равна произведению долей всех символов сообщения. Число бит - log₂(1/ширина) плюс не больше двух. Логарифм произведения - сумма логарифмов, поэтому длина кода равна сумме log₂(1/p) по всем символам сообщения, то есть энтропии, умноженной на длину, плюс два бита. Символ с долей 0,95 добавляет к длине log₂(1/0,95) = 0,074 бита - дробные биты складываются внутри одного числа. Распаковщику нужны те же доли и длина сообщения.

Разбор: программа на целых числах

Дроби с плавающей точкой не годятся: после нескольких десятков символов отрезок станет уже, чем их точность. Программа ведёт отрезок точно - числитель нижней границы, числитель ширины и общий знаменатель. Целые числа в Python не ограничены по длине, и это всё, что здесь нужно. Доли берутся из самого сообщения. Отрезок - это [lo / znam, (lo + shir) / znam). Шаг «взять часть символа» сдвигает нижнюю границу на долю nachalo[c] / n от текущей ширины и умножает ширину на kol[c] / n; чтобы остаться в целых числах, знаменатель умножается на n, а вместе с ним и lo. Прибавка znam - 1 перед делением нацело - округление вверх.

def arif(s):
    kol = {}
    for c in s:
        kol[c] = kol.get(c, 0) + 1
    nachalo = {}                      # сколько символов лежит на отрезке ниже данного
    nizhe = 0
    for c in sorted(kol.keys()):
        nachalo[c] = nizhe
        nizhe = nizhe + kol[c]
    n = len(s)
    lo = 0                            # отрезок [lo / znam, (lo + shir) / znam)
    shir = 1
    znam = 1
    for c in s:
        lo = lo * n + shir * nachalo[c]
        shir = shir * kol[c]          # ширина умножилась на долю kol[c] / n
        znam = znam * n
    bit = 0
    while True:
        bit = bit + 1
        m = (lo * 2 ** bit + znam - 1) // znam            # первая дробь m / 2^bit не левее lo
        if (m + 1) * znam <= (lo + shir) * 2 ** bit:      # её клетка целиком внутри отрезка
            break
    return [bit, m]

print(arif("abracadabra"))            # [23, 2338649]

Последний цикл ищет самую короткую двоичную дробь, у которой внутри отрезка лежит не только она сама, но и вся её клетка сетки - до следующей дроби. Тогда после этих бит можно дописывать что угодно, и распаковщик не собьётся. За это и платятся «плюс два бита».

Распаковка идёт тем же путём: смотрим, в чью часть текущего отрезка попало число, выписываем этот символ, сужаем отрезок до этой части - и так n раз.

Разбор: замер против Хаффмана и граница выигрыша

сообщение                  символов    энтропия · n    Хаффман    арифметическое
abracadabra                    11          22,4           23            23
("a" * 19 + "b") * 5          100          28,6          100            30
"aaaab" * 20                  100          72,2          100            74
"ab" * 50                     100         100            100           100

Ответ на вопрос из начала урока - вторая строка. Тридцать бит на сто символов: 0,3 бита на символ. Никакой отдельный символ не получил «треть бита»; закодировано число, и каждая буква a сузила отрезок чуть-чуть - на множитель 0,95.

Первая и последняя строки - граница. Когда доли равны степеням двойки - половина, четверть, восьмая, - код Хаффмана стоит точно на пределе, а когда близки к ним - почти на пределе, и арифметическое кодирование ничего не добавляет. Выигрыш появляется при перекосе: чем ближе доля частого символа к единице, тем дальше Хаффман от энтропии.

Во всех четырёх строках не посчитана таблица долей, которую надо передать распаковщику, - её цена одинакова для обоих методов.

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

Первое: числа растут без предела. В программе выше lo и znam - числа длиной во всё сообщение, и каждое умножение стоит тем дороже, чем дальше мы зашли: квадратичное время. Рабочие кодировщики держат границы в машинном слове. Как только старшие биты нижней и верхней границы совпали, они уже не изменятся - их выдают в выходной поток, а границы сдвигают влево. То же в десятичной записи: у границ 0,4172 и 0,4188 цифры «0,41» уже общие и при любом сужении останутся такими - их можно записать и забыть. Такой вариант называют кодированием диапазона.

Второе: доли у сторон разошлись. Распаковщик делит отрезок по своим долям. Если они хоть немного отличаются от долей упаковщика - например, из-за округления дробей, - с какого-то символа число попадёт в чужую часть, и всё дальнейшее превратится в мусор. Поэтому доли задают целыми счётчиками, а не дробями.

Третье: конец сообщения не обозначен. Число 0,101 кодирует и aba, и abaa, и любое продолжение, отрезок которого его содержит. Нужна либо длина, переданная заранее, либо особый символ конца.

Четвёртое: один испорченный бит. У кода Хаффмана ошибка портит несколько символов, после чего чтение часто возвращается в колею. Здесь всё сообщение - одно число: ошибка в бите меняет его, и с этого места до конца распаковка выдаёт другое сообщение.

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

Первый сюжет - видео и изображения. В видеокодеках H.264 и H.265 последняя ступень - двоичное арифметическое кодирование с долями, которые подстраиваются под контекст. Перекос там огромный: «этот коэффициент равен нулю» верно в подавляющем большинстве случаев, и Хаффман терял бы на каждом таком ответе почти целый бит.

Второй - архиваторы. Формат xz кодирует диапазоном каждый бит выхода LZ77. Формат bzip2 мог бы делать так же: его предшественник использовал арифметическое кодирование и был переведён на код Хаффмана из-за патентов, которые тогда действовали. Патенты истекли, а формат остался.

Третий - то, что пришло на смену. Арифметическое кодирование на каждый символ тратит умножение и деление; код Хаффмана - одно обращение к таблице. В 2009 году Ярек Дуда предложил асимметричные системы счисления (ANS): сжатие как у арифметического кодирования при скорости таблиц. На них работает энтропийная ступень zstd и нескольких новых форматов изображений (энтропийная ступень - последняя часть архиватора, та, что кодирует символы по их долям). Идея та же - копить дробные биты в одном числе, - а арифметика другая.

Теперь сам

Сообщение aab. Доли возьми из него самого: a - 2/3, b - 1/3, a занимает нижнюю часть. Найди итоговый отрезок и его ширину. Лежит ли в нём число 3/8, то есть 0,011 в двоичной записи? Сколько бит потратил бы код Хаффмана?

начало                    [0,       1)
символ a - нижние 2/3     [0,       2/3)
символ a - нижние 2/3     [0,       4/9)
символ b - верхняя 1/3    [8/27,    4/9)       ширина 4/27