Неравномерное кодирование

Сначала назовём вещи своими именами.

Равномерный код – код, в котором все кодовые слова имеют одинаковую длину.
Неравномерный код – код, в котором длины кодовых слов различаются.

Все кодировки из прошлых уроков были равномерными: ASCII – 7 битов на символ, код Бодо – 5, Windows-1251 – 8. Плюс у равномерного кода один, зато решающий: декодирование тривиально. Читаем ленту кусками известной длины, границы заданы заранее, неоднозначности взяться неоткуда. Цена – на редкий символ тратится ровно столько же, сколько на частый.

Отдельно про UTF-8: он неравномерный, от 1 до 4 байтов. Но границы в нём размечены явно – метками в старших битах каждого байта, и метки эти занимают место. К концу урока станет видно, что UTF-8 – не просто «код с метками», а аккуратно построенный код того самого типа, о котором пойдёт речь.

Возьмём алфавит из четырёх букв с известными частотами:

Равномерный код здесь короче некуда: букв четыре, $4 = 2^2$, значит, 2 бита на символ, и сообщение из 200 символов займёт 400 битов.

Теперь неравномерный. Частой А достался 1 бит, редким В и Г – по три. Считаем те же 200 символов:

А: 100 × 1 = 100
Б:  50 × 2 = 100
В:  25 × 3 =  75
Г:  25 × 3 =  75
             ───
             350 битов вместо 400

Экономия 12,5%, и берётся она не из воздуха: мы заранее знали, что буквы встречаются неодинаково, и воспользовались этим знанием.

Важно понимать, что именно происходит. Неравномерный код ничего не «сжимает» магией – он перераспределяет биты, отбирая их у частых символов и отдавая редким. Общий выигрыш появляется только потому, что частых символов в тексте больше.

Здесь $p_i$ – доля (частота) символа в тексте, $l_i$ – длина его кодового слова в битах. Для нашей таблицы:

$L = 0{,}5 \cdot 1 + 0{,}25 \cdot 2 + 0{,}125 \cdot 3 + 0{,}125 \cdot 3 = 1{,}75$ бита на символ против ровно 2 у равномерного кода.

Именно эту величину и стараются уменьшить, когда строят код. Но обратите внимание на честную оговорку: частоты должны быть угаданы верно. Если код построен под английский текст, а кодируют им русский, средняя длина легко окажется больше двух битов – неравномерный код проиграет равномерному.

Прежде чем читать дальше – короткая задача. Не подглядывайте в следующий блок, там разбор.

Кодовая таблица выглядит очень экономно, все коды по 1–2 бита:

А = 0     Б = 1     В = 01     Г = 10

Пришла лента: 0101. Какое слово было закодировано?

Ответов как минимум пять:

0 | 1 | 0 | 1   →  АБАБ
01 | 01         →  ВВ
0 | 10 | 1      →  АГБ
01 | 0 | 1      →  ВАБ
0 | 1 | 01      →  АБВ

Лента одна, слов пять, и – самое неприятное – ни одно из прочтений не более правильное, чем другие. Сама лента не содержит никаких сведений о том, где границы символов.

Поставим диагноз аккуратно. Беда не в том, что коды короткие, и не в том, что они разной длины. Беда в том, что код 0 – это начало кода 01. Прочитав первый бит 0, декодер не может решить: символ уже кончился (А) или это только первый бит из двух (В). И оба варианта имеют право на жизнь.

Значит, нужен признак, по которому заранее, глядя только на таблицу кодов, можно сказать: возможна ли такая неоднозначность хоть на каком-нибудь сообщении.

Условие Фано: никакое кодовое слово не является началом (префиксом) другого кодового слова. Код, удовлетворяющий этому условию, называется префиксным.

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

Проверим на примерах:

Про название и про людей. Роберт Фано (1917–2016) – американский учёный итальянского происхождения, профессор Массачусетского технологического института; вместе с Клодом Шенноном он стоял у истоков теории информации, а способ построения экономного кода из его отчёта 1949 года известен как код Шеннона – Фано. Стоит сказать прямо: термин «условие Фано» закрепился в русскоязычной учебной традиции, в англоязычной литературе то же самое свойство называют просто префиксным (prefix-free code).

Есть переформулировка условия Фано, после которой оно перестаёт быть правилом, которое надо запоминать, и становится очевидным. Но сначала – про схему, на которой всё будет нарисовано. В учебнике она встречается впервые, а в следующем уроке, про алгоритм Хаффмана, будет работать всё время.

Дерево – схема из точек (узлов), соединённых линиями (рёбрами), устроенная так: есть одна выделенная точка – корень, и из корня в любой другой узел ведёт ровно один путь. Никаких развилок, которые потом сходятся обратно, и никаких замкнутых колец в дереве нет.

Рисуют деревья в информатике вверх ногами: корень сверху, ветви растут вниз. Дальше словарь такой:

• лист – узел, из которого вниз уже ничего не растёт, тупик ветви;
• внутренний узел – узел, из которого ветви идут дальше (корень тоже внутренний, если дерево не состоит из него одного);
• глубина узла – сколько рёбер надо пройти от корня до него.

Дерево называют двоичным, если из каждого узла вниз выходит не больше двух рёбер. Именно такое нам и нужно: битов ровно два.

Теперь соберём кодовое дерево. Из каждого узла проведём два ребра: влево – 0, вправо – 1. Тогда кодовое слово – это маршрут от корня, а символ ставится в ту точку, где маршрут заканчивается. Код 110 читается как «вправо, вправо, влево», и приводит он ровно в один узел – потому что путь от корня в дереве всегда единственный.

• Если все символы сидят в листьях, условие Фано выполняется автоматически: маршрут в тупик нельзя продолжить, а значит, он не может быть началом другого маршрута.
• Если символ оказался во внутреннем узле, через него проходят маршруты к другим символам – это и есть нарушение.

Отсюда правило, которым удобно проверять таблицу глазами: символы – только в листьях.

И здесь же видно, откуда берётся ограничение на жадность. Отдать короткий код 0 одному символу – значит забрать вместе с ним всю левую половину дерева. Бесплатных коротких кодов не бывает: за каждый платят удлинением остальных.

Обратное условие Фано: никакое кодовое слово не является окончанием (суффиксом) другого. Такой код тоже декодируется однозначно – но читать ленту придётся с конца.

Пример: А = 0, Б = 01, В = 011. Условие Фано нарушено – 0 является началом и 01, и 011. А вот окончанием другого слова здесь не является ни одно, и лента 011010 с конца читается единственным способом: 011 | 01 | 0, то есть ВБА.

Отсюда оговорка, которую в кратких пересказах часто теряют: условие Фано достаточно, но не необходимо. Выполнено – код точно однозначен. Нарушено – код может оказаться однозначным (как только что), а может и не оказаться (как в ловушке с 0101). Проверять придётся отдельно.

Почему же на практике почти всегда берут именно префиксные коды, а не суффиксные? Потому что префиксный код декодируется на лету: символ выдаётся сразу, как только дочитан его код. Суффиксный требует сначала получить сообщение целиком – для потока данных из сети это неприемлемо.

Типовая задача, ради которой условие Фано обычно и изучают: часть кодов уже роздана, нужно достроить таблицу.

Условие. Для букв А, Б, В используются коды А = 0, Б = 100, В = 101. Закодируйте ещё букву Г так, чтобы код остался префиксным, а кодовое слово было как можно короче.

Разбор. Однобитовые кандидаты: 0 занят; 1 – начало и 100, и 101, не годится. Двухбитовые: 10 – начало 100, отпадает; 11 – не начинается ни с одного выданного кода и само не является началом ни одного из них. Ответ: Г = 11, два бита.

По дереву тот же ответ виден за один взгляд: А занял левую ветвь целиком, Б и В сидят в правой-левой части, а вся ветка 11 свободна. Загляните в виджет выше – там есть готовый пример «Задача про Г», и подсказка про самое короткое свободное слово пересчитывается на лету.

Вопрос посложнее. Сколько всего букв можно закодировать, если три из них уже получили коды 00, 01 и 10? Свободна ровно одна ветка – 11, так что четвёртой букве достанется код 11. Но если букв нужно больше, эту ветку можно разбить дальше: 110 и 111 дадут пятую и шестую. Вариантов достройки обычно несколько, и требование «как можно короче» выбирает из них конкретный.

В этой программе стоит заметить одну вещь. В ней нет ни одной проверки вида «а вдруг здесь неоднозначность» – и появиться ей неоткуда: цикл просто копит биты и сравнивает копилку с кодами. На плохой таблице он молча выдаст первое подошедшее прочтение, а не «правильное». Для кодов А = 0, Б = 1, В = 01, Г = 10 и ленты 0101 такая программа вернёт АБАБ, хотя ВВ ничем не хуже – проверьте это в конструкторе выше, он покажет все пять прочтений. Ответственность за однозначность лежит на том, кто составлял таблицу, а не на программе, которая по ней читает.

Три примера, чтобы условие Фано не осталось школьным упражнением.

UTF-8 – префиксный код. Вспомните метки из урока 7.3: ведущие байты начинаются с 0, 110, 1110, 11110, а байты-продолжения с 10. Ни одна из этих меток не является началом другой – именно поэтому декодер находит границы символов, не глядя на соседей. То, что мы называли «самосинхронизацией», и есть условие Фано, применённое к старшим битам байта. Проверьте сами: в виджете выше есть готовый пример «Метки UTF-8».

Телефонные номера. Экстренные службы получили короткие номера (112), обычные абоненты – длинные, и ни один короткий номер не является началом длинного. Иначе, набрав первые цифры, станция не знала бы: соединять уже или ждать продолжения.

Код Морзе – контрпример. Он условию Фано не удовлетворяет: E = · является началом A = ·−. Поэтому Морзе и потребовалась пауза – по сути, третий знак, физически разделяющий буквы. Уберите паузы, и сообщение станет неоднозначным ровно так же, как лента 0101 из начала урока.