Алфавитный подход к измерению информации

Беда в том, что «важность» или «полезность» сообщения измерить невозможно. Фраза «Завтра контрольная» для одного человека – новость, а для другого – то, что он и так знал. Любая мера, опирающаяся на смысл, окажется своей у каждого получателя, а значит, никакого общего расчёта на ней не построить.

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

Чтобы не возникло ложного впечатления, что мера всего одна: существует и содержательный (вероятностный) подход, где количество информации зависит от того, насколько неожиданным было сообщение. Его развил Клод Шеннон в работе 1948 года – той самой, где закрепился термин «бит» (урок 5.1). Алфавитный подход старше: его основу заложил Ральф Хартли в статье «Transmission of Information» 1928 года, работая в Bell Labs. Хартли считал логарифм по основанию 10, и его единица («хартли», один десятичный разряд $\approx 3{,}32$ бита) сегодня почти не используется – но сама идея «количество информации – это логарифм числа возможных вариантов» осталась ровно его.

Алфавит – конечный набор символов, из которых составляются сообщения. Мощность алфавита N – количество символов в этом наборе.

Слово «алфавит» здесь шире школьного значения: это любой набор различимых знаков, а не только буквы.

• двоичный алфавит {0, 1} – $N = 2$;
• десятичные цифры – $N = 10$;
• русские буквы – $N = 33$, а если различать прописные и строчные, добавить пробел и знаки препинания, получится уже под сотню;
• четыре нуклеотида ДНК {A, T, G, C} – $N = 4$, и это не натяжка: в биоинформатике геном действительно хранят как текст в четырёхсимвольном алфавите;
• 64 клетки шахматной доски, если записывать ход как «откуда-куда».

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

Здесь $N$ – мощность алфавита, $b$ – количество битов, нужное для кодирования одного его символа.

Формула та же, что в уроке 5.1, только прочитанная в другую сторону. Там мы спрашивали: «дано $n$ битов – сколько значений влезет?». Здесь: «дано $N$ вариантов – сколько битов на них нужно?». Обоснование прежнее: каждый добавленный бит удваивает число различимых комбинаций, потому что любую старую комбинацию можно продолжить и нулём, и единицей. Один бит – 2 варианта, два бита – 4, три – 8, восемь – 256.

Обратная запись той же формулы – через логарифм:

$b = \log_2 N$

Если логарифмы вы ещё не проходили, читайте эту запись просто как вопрос «в какую степень надо возвести двойку, чтобы получить $N$». Для школьных примеров подобрать степень двойки в уме обычно быстрее, чем считать на калькуляторе.

Информационный вес символа – количество информации, которое несёт один символ алфавита при алфавитном подходе. Измеряется в битах и вычисляется как $b = \log_2 N$.

Несколько алфавитов и их вес:

Три последние строки – это ровно темы уроков 7.2 и 7.3: семь битов таблицы ASCII, один байт на символ в однобайтовых кодировках и Unicode, который в байт не влезает физически.

В таблице выше все мощности были степенями двойки – так получается красиво, но так бывает далеко не всегда.

Возьмём 33 русские буквы. $2^5 = 32$ – мало, не хватает ровно одной буквы. $2^6 = 64$ – хватает с большим запасом. Формально $\log_2\,33 \approx 5{,}04$, но «5,04 бита на символ» в равномерном коде записать невозможно: биты целые.

Берём минимальное целое $b$, при котором $2^b \ge N$, то есть округляем логарифм вверх.

Примеры: 10 цифр → 4 бита (шесть комбинаций из шестнадцати останутся неиспользованными), 33 буквы → 6 битов (лишняя 31 комбинация), 100 символов → 7 битов.

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

Отсюда два наблюдения:

• запас почти всегда пропадает впустую, и при равномерном коде за него платят все символы одинаково;
• дробный ответ $\log_2 N$ – это теоретический минимум, до которого равномерный код не дотягивается. Обойти ограничение можно, но только отказавшись от равномерности: если частым символам давать короткие коды, а редким – длинные, средняя длина опускается ниже. Это и есть темы уроков 7.4 и 7.5.

Вес мы считали для одного символа. Сообщение – это $K$ символов подряд, и каждый из них стоит одинаково: в этом и состоит равномерность кода. Значит, общий объём получается простым умножением.

$K$ – количество символов в сообщении, $b$ – информационный вес одного символа, $I$ – объём сообщения в битах.

Про $K$ есть ловушка, на которой спотыкаются чаще всего: пробелы и знаки препинания – полноправные символы алфавита, и считать их нужно наравне с буквами.

Разберём на примере. Страница текста – 40 строк по 60 символов, алфавит на 256 символов.

• $b = 8$ битов, потому что $2^8 = 256$, то есть ровно 1 байт на символ;
• $K = 40 \cdot 60 = 2400$ символов;
• $I = 2400 \cdot 8 = 19\,200$ битов = 2400 байтов $\approx 2{,}34$ КБ.

И сразу напоминание из урока 5.1: чтобы перейти к килобайтам, делим на 1024, а не на 1000.

Задача 1 (прямая). Сообщение из 200 символов записано алфавитом из 33 букв. Каков его минимальный информационный объём?

$b = 6$, потому что $2^6 = 64 \ge 33$. Дальше $I = 200 \cdot 6 = 1200$ битов = 150 байтов.

Задача 2 (обратная). Сообщение из 40 символов заняло 30 байтов. Какова максимальная мощность алфавита?

30 байтов – это 240 битов, значит $b = 240 / 40 = 6$ битов на символ, откуда $N \le 2^6 = 64$. Обратите внимание на «не больше»: шесть битов гарантируют, что символов было не более 64, но сколько их было на самом деле – 64, 40 или 33 – задача не говорит.

Задача 3 (на сравнение). Один и тот же текст из 500 символов записали двумя способами: в однобайтовой кодировке (256 символов) и в UTF-32, где на символ отводится 4 байта. Во сколько раз отличаются объёмы?

500 байтов против 2000 байтов – ровно в четыре раза. Текст один, смысл один, а объём разный: он зависит не от самого сообщения, а от выбранного способа кодирования. Мысль, которая понадобится в уроке 7.3.

В листинге ниже встретится строчка, которой раньше в учебнике не было. Логарифм – не встроенная операция: функция log2 лежит в модуле math, и, прежде чем ею пользоваться, модуль нужно подключить.

import math
print(math.log2(8))   # 3.0

import math открывает доступ к содержимому модуля через точку: math.log2, math.ceil, math.pi – читается как «возьми из math». Есть и короткая форма from math import log2: тогда приставка не нужна и пишут просто log2(8).

Сам math идёт в комплекте с Python – это стандартная библиотека, ставить ничего не надо. Сторонние библиотеки (numpy, requests и прочие) сначала устанавливают командой pip install имя, а подключают тем же import.

Одно замечание про две последние строчки первой половины. math.log2 возвращает вещественное число, а с ним на границах степеней двойки бывают сюрпризы из урока 5.3: результат может оказаться чуть больше целого, и округление вверх добавит лишний бит. Целочисленный вариант (N - 1).bit_length() таких проблем не имеет и считает то же самое – сколько битов нужно, чтобы записать номера символов от $0$ до $N - 1$.

Вернёмся к разминке. Все три сообщения – по 15 символов одного алфавита, значит по формуле $I = K \cdot b$ объём у них одинаковый. Мера не сломалась: она с самого начала обещала измерять только объём записи и никогда – смысл.

Но у такой честности есть цена, и лучше всего её видно на третьем сообщении. «яяяяяяяяяяяяяяя» очевидно можно записать короче – например, «я $\times 15$». Алфавитный подход этого не заметит: он считает все символы равновероятными и не смотрит на повторы. В настоящем русском тексте буква «о» встречается в десятки раз чаще, чем «ъ», – и этим ресурсом подход тоже не пользуется.

Отсюда два продолжения:

• содержательный подход Шеннона учитывает вероятности символов и даёт меньшую оценку – теоретический минимум, ниже которого сжать нельзя в принципе;
• неравномерное кодирование (урок 7.4) и алгоритм Хаффмана (урок 7.5) – практические способы к этому минимуму приблизиться.

Так что алфавитный подход – не «неправильный», а верхняя оценка: столько битов точно хватит, если о содержании сообщения ничего не известно. Именно так и рассуждают, когда проектируют кодировку: она должна работать на любом тексте, а не только на удобном.