Цепи Маркова и информация

В прошлой главе все наблюдения были независимыми: опрошенные не советовались друг с другом, чашки чая ничего не знали друг о друге. А буквы в тексте, погода по дням, щелчки по ссылкам зависят от предыдущих. Как описать такую зависимость? И можно ли измерить, сколько информации несёт сообщение, — не на глаз, а в единицах, как длину или массу?

На оба вопроса лучше всего ответили бы криптограф и лингвист, если бы сели за один стол. Криптограф знает, что текст выдаёт себя частотами букв: ещё в IX веке арабский философ аль-Кинди описал, как вскрыть шифр, сравнив частоты знаков шифровки с частотами букв языка. Лингвист знает, что буквы не независимы: после одних охотно идут другие. Эта глава — рабочий журнал такого стола. Мы пересчитаем буквы вместе с Андреем Марковым, научим машину писать тексты, выясним, сколько вопросов нужно, чтобы угадать задуманное, и найдём число, которое Клод Шеннон назвал количеством информации.

Двадцать тысяч букв

В январе 1913 года Андрей Андреевич Марков доложил Академии наук необычную работу. Математик, известный теоремами о суммах случайных величин, взялся за «Евгения Онегина». Он выписал первые $20\,000$ букв романа — без пробелов, знаков препинания, твёрдого и мягкого знаков — и сосчитал гласные и согласные. Гласных оказалось $8638$, согласных $11\,362$, то есть доля гласных $0{,}432$.

Это было только начало. Марков сосчитал ещё пары соседних букв. Гласная сразу за гласной встретилась $1104$ раза, согласная за согласной — $3827$ раз. Если бы буквы шли независимо, как броски монеты, то за гласной гласная следовала бы с той же вероятностью $0{,}432$, что и вообще. На деле

$$P(\text{гласная} \mid \text{гласная}) = \frac{1104}{8638} \approx 0{,}128, \qquad P(\text{гласная} \mid \text{согласная}) = 1 - \frac{3827}{11\,362} \approx 0{,}663.$$

После гласной гласная идёт втрое с лишним реже, чем в среднем, а после согласной — в полтора раза чаще. Буквы помнят соседа: гласные и согласные предпочитают чередоваться.

Зачем академику считать буквы? Марков вёл спор. Московский математик Павел Некрасов утверждал, что закон больших чисел требует независимости наблюдений, и делал из этого далеко идущие философские выводы. Ещё в 1906 году Марков доказал, что закон больших чисел верен и для величин, каждая из которых зависит от предыдущей, а в 1913-м проверил свою модель на самом живом материале, какой нашёл, — на стихах Пушкина.

Модель Маркова проста. Текст — последовательность двух состояний, «гласная» и «согласная». Следующая буква выбирается случайно, но вероятности зависят только от текущей. Это цепь Маркова с двумя состояниями — та же конструкция, что у самокатов в главе 38. Её вероятности переходов собирают в матрицу:

$$P = \begin{pmatrix} 0{,}128 & 0{,}872 \\ 0{,}663 & 0{,}337 \end{pmatrix}.$$

Здесь есть тонкость обозначений. В главе 38 столбец $j$ матрицы переходов говорил, куда уходит состояние $j$, и в единицу складывались столбцы. Теория вероятностей по традиции пишет транспонированную матрицу: строка — откуда, столбец — куда, $p_{ij}$ — вероятность перейти из состояния $i$ в состояние $j$, и в единицу складываются строки. Первая строка нашей матрицы — что бывает после гласной, вторая — после согласной. Распределение по состояниям тогда записывают строкой $\boldsymbol\pi = (\pi_1, \dots, \pi_n)$ и умножают на матрицу справа. Дальше в этой главе — только так.

Строка вероятностей состояний: $\pi_i \ge 0$ и $\pi_1 + \dots + \pi_n = 1$. Матрица переходов: $p_{ij}$ — вероятность из состояния $i$ перейти в $j$, строки складываются в единицу. Произведение $\boldsymbol\pi P$ — распределение через один шаг: $(\boldsymbol\pi P)_j = \sum_i \pi_i p_{ij}$ по формуле полной вероятности. Равенство говорит, что за шаг распределение не меняется. Это тот же собственный вектор с собственным значением $1$, что в главе 38, только записанный строкой: $\boldsymbol\pi P = \boldsymbol\pi$ — всё равно что $P^{\mathsf T}\boldsymbol\pi^{\mathsf T} = \boldsymbol\pi^{\mathsf T}$. Пример: для цепи Маркова $\boldsymbol\pi \approx (0{,}432;\ 0{,}568)$, и действительно $0{,}432 \cdot 0{,}128 + 0{,}568 \cdot 0{,}663 \approx 0{,}432$.

Заметьте: стационарная доля гласных, $0{,}432$, совпала с их долей в тексте до третьего знака. Это не случайность. В любом тексте переходов «гласная → согласная» столько же, сколько переходов «согласная → гласная», с точностью до одного: каждая группа гласных где-то начинается и где-то кончается. А равенство этих потоков, как мы сейчас увидим, и определяет равновесие цепи. Для двух состояний всё можно посчитать до конца.

Хитрость в том, чтобы следить не за буквами, а за потоками вероятности между состояниями.

Пусть сейчас цепь в состоянии $1$ с вероятностью $x$ и в состоянии $2$ с вероятностью $1 - x$. За шаг из $1$ в $2$ перетекает доля $a$ от $x$, то есть $ax$, а обратно — $b(1 - x)$. Распределение не меняется, когда потоки уравновешены: $ax = b(1 - x)$. Это линейное уравнение с единственным решением $x = \frac{b}{a + b}$ (здесь нужно $a + b > 0$). Это и есть $\pi_1$, а $\pi_2 = 1 - \pi_1 = \frac{a}{a + b}$. Теперь возьмём любое начальное $x$. Через шаг $x' = x - ax + b(1 - x) = b + (1 - a - b)\,x$. Для $\pi_1$ шаг ничего не меняет: $\pi_1 = b + (1 - a - b)\,\pi_1$ — это тот же баланс потоков. Вычтем одно равенство из другого: $x' - \pi_1 = (1 - a - b)(x - \pi_1)$. За каждый шаг отклонение от равновесия умножается на одно и то же число $1 - a - b$, поэтому через $k$ шагов оно равно $(1 - a - b)^k\,\delta$. Если $0 < a + b < 2$, модуль множителя меньше единицы, и отклонение тает. У Маркова $1 - a - b \approx -0{,}535$: отрицательный множитель означает, что отклонение каждый раз меняет знак, — цепь приходит к равновесию, раскачиваясь, как чередуются гласные и согласные.

Условие $a + b < 2$ отсекает единственный плохой случай $a = b = 1$: цепь без всякой случайности чередует состояния, и отклонение только меняет знак, не уменьшаясь. А множитель $1 - a - b$ — второе собственное значение матрицы $P$, как множитель $0{,}4$ у самокатов из главы 38.

В некотором тексте после гласной гласная идёт с вероятностью $0{,}2$, а после согласной — с вероятностью $0{,}6$. Какая доля букв длинного текста — гласные? Ответ дайте обыкновенной дробью.

Из гласной цепь уходит в согласную с вероятностью $a = 1 - 0{,}2 = 0{,}8$, из согласной в гласную — с вероятностью $b = 0{,}6$. Стационарная доля гласных $\frac{b}{a + b} = \frac{0{,}6}{1{,}4} = \frac37 \approx 0{,}43$. Проверка балансом потоков: $\frac37 \cdot 0{,}8 = \frac47 \cdot 0{,}6 = \frac{2{,}4}{7}$.

Погода и прогулки

С погодой похожая история: завтрашний день чаще всего похож на сегодняшний. Возьмём цепь с тремя состояниями — ясно, облачно, дождь — и условными вероятностями переходов. После ясного дня завтра ясно с вероятностью $0{,}6$, облачно — $0{,}3$, дождь — $0{,}1$; после облачного — $0{,}3$, $0{,}4$ и $0{,}3$; после дождливого — $0{,}2$, $0{,}4$ и $0{,}4$.

Пусть понедельник ясный: распределение $(1;\ 0;\ 0)$. Во вторник это первая строка матрицы, $(0{,}6;\ 0{,}3;\ 0{,}1)$. В среду — $(0{,}47;\ 0{,}34;\ 0{,}19)$, в четверг — $(0{,}422;\ 0{,}353;\ 0{,}225)$, а к следующему понедельнику — $(0{,}394;\ 0{,}361;\ 0{,}245)$. С какой погоды ни начни, через неделю картина почти та же: цепь забывает, с чего начала. Предел — стационарное распределение $\boldsymbol\pi = \left(\frac{24}{61};\ \frac{22}{61};\ \frac{15}{61}\right)$; проверьте, что $\boldsymbol\pi P = \boldsymbol\pi$. Так будет при любой матрице, в которой все вероятности переходов положительны: это теорема о положительной цепи из главы 38, и её доказательство от транспонирования не зависит.

Самая наглядная цепь Маркова — случайное блуждание по графу (глава 46). Путник стоит в вершине и уходит по случайно выбранному ребру: из вершины степени $d$ — к каждому соседу с вероятностью $1/d$. Где он бывает чаще? Интуиция подсказывает: там, куда ведёт больше дорог. Интуиция права, а ответ умещается в одну дробь.

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

Числа $\frac{\deg v}{2E}$ действительно образуют распределение: они неотрицательны, а их сумма равна $\frac{1}{2E}\sum_v \deg v = 1$, потому что сумма степеней вдвое больше числа рёбер — каждое ребро учтено у обоих концов. Посчитаем поток вероятности по ребру $uv$ за один шаг. Из $u$ в $v$ уходит $\pi_u \cdot \frac{1}{\deg u} = \frac{\deg u}{2E} \cdot \frac{1}{\deg u} = \frac{1}{2E}$. Ровно столько же идёт по этому ребру обратно, из $v$ в $u$. Каждое ребро несёт в обе стороны поровну, $\frac{1}{2E}$. Значит, в каждую вершину за шаг втекает столько же, сколько вытекает: по каждому её ребру приток равен оттоку. Распределение не меняется, оно стационарно. Такое равенство потоков по каждому ребру называют детальным балансом. Теперь единственность. Пусть $\boldsymbol\pi'$ — любое стационарное распределение; положим $h(v) = \pi'_v/\deg v$. Условие стационарности $\pi'_v = \sum_{u \sim v} \pi'_u/\deg u$ (сумма по соседям $v$) превращается в $h(v) = \frac{1}{\deg v}\sum_{u \sim v} h(u)$: в каждой вершине $h$ равно среднему своих значений у соседей. Возьмём вершину, где $h$ наибольшее. Среднее чисел, не превосходящих максимума, равно максимуму, только если все они равны максимуму. Значит, у всех соседей этой вершины $h$ тоже наибольшее. Повторим рассуждение для соседей, потом для их соседей. Граф связен, поэтому так мы дойдём до каждой вершины: $h$ всюду одно и то же число $c$, то есть $\pi'_v = c\deg v$. Сумма вероятностей равна $1$, откуда $c = \frac{1}{2E}$ и $\boldsymbol\pi' = \boldsymbol\pi$.

Стационарное распределение есть и единственно, но сходится к нему прогулка не всегда. Если граф двудольный — вершины можно раскрасить в два цвета так, чтобы рёбра соединяли только разные цвета, — путник попеременно ходит между долями, и распределение по чётным и нечётным шагам не выравнивается никогда. Теорема из главы 38 требовала положительности всех вероятностей переходов именно для того, чтобы исключить такие ловушки. А если путнику иногда разрешить телепортироваться на случайную страницу и сделать рёбра односторонними, получится PageRank (глава 38).

Машина, которая пишет

Вернёмся к тексту. Марков различал только гласные и согласные. А если состояниями сделать сами буквы? Следующая буква выбирается с вероятностями, которые зависят от предыдущей, — и цепь начинает писать. Ещё лучше, если состояние — последние две, три, четыре буквы: тогда цепь помнит больше.

Так поступил Клод Шеннон в статье «Математическая теория связи» (1948). Компьютера у него под рукой не было, и он строил цепь по книге. Открыл книгу наугад, нашёл на странице очередное слово, посмотрел, какое слово идёт за ним, выписал его; открыл книгу в другом месте, нашёл уже это слово — и так дальше. Получилось «приближение второго порядка по словам», которое начинается так: THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER… Смысла нет, но каждая пара соседних слов звучит вполне по-английски.

С ростом памяти модель пишет всё правдоподобнее, но упирается в две стены. Первая — число состояний: при алфавите из $34$ символов (буквы и пробел) у модели с памятью в $k$ символов до $34^k$ состояний, и уже при $k = 5$ это больше $45$ миллионов. Вторая стена следует из первой: почти ни одно из этих состояний в образце не встретится, а если встретится, то один-два раза. Модель с длинной памятью не сочиняет, а цитирует: после редкого контекста у неё есть ровно одно продолжение — то, что стояло в образце.

Современные языковые модели обходят обе стены иначе. Они не хранят таблицу продолжений, а учатся обобщать: оценивать вероятность следующего символа даже после контекста, которого в обучающих текстах никогда не было, по сходству с тем, что было. Как собрать такую модель с нуля и обучить её прямо в браузере, рассказывает курс «Росток» на этом сайте (/utilities/micro-llm). Но и она, как цепь Маркова, на каждом шаге выдаёт распределение вероятностей следующего символа и выбирает из него.

Двадцать вопросов

Теперь второй вопрос: сколько информации в сообщении? Шеннон начал с того, что информация — это снятая неопределённость. Мерить её проще всего игрой: один задумал, другой угадывает вопросами, на которые отвечают «да» или «нет».

В главе 1 шесть карточек угадывали число от $1$ до $63$ — шесть ответов «да» или «нет». Каждый ответ делит круг кандидатов пополам, поэтому $k$ вопросами можно различить $2^k$ вариантов, а чтобы выбрать один из $N$ равновозможных, нужно $\lceil \log_2 N\rceil$ вопросов. Миллион — это двадцать вопросов: $2^{20} = 1\,048\,576$. Отсюда естественная мера: сообщение, которое выбирает один из $N$ равновозможных вариантов, несёт $\log_2 N$ бит. Меру через логарифм числа вариантов предложил инженер Ральф Хартли ещё в 1928 году.

Но варианты редко равновозможны. Пусть задумана случайная буква русского текста. Буква «о» встречается в сотни раз чаще «ъ», и хороший угадывающий не станет спрашивать «буква в первой половине алфавита?». Он спросит «это о, е или а?» — одна эта тройка покрывает больше четверти букв текста. Хороший вопрос делит пополам не число вариантов, а их вероятность. Тогда редкая буква потребует много вопросов, частая — мало, и в среднем их понадобится меньше, чем $\log_2 N$.

Сколько вопросов «стоит» исход вероятности $p$? Если каждый вопрос делит вероятность пополам, то после $k$ ответов остаются варианты общей вероятностью $2^{-k}$. Исход вероятности $p$ опознан, когда $2^{-k} = p$, то есть $k = \log_2\frac1p$. Шеннон взял это число за меру.

Логарифм здесь не прихоть. Для независимых событий вероятности перемножаются, а информация должна складываться: узнать исход двух монет — то же, что узнать исход каждой, $\log_2 4 = \log_2 2 + \log_2 2$. Логарифм как раз превращает произведение в сумму: $-\log_2(pq) = -\log_2 p - \log_2 q$. Среднее количество информации на одно сообщение Шеннон назвал энтропией.

Вероятность $i$-го исхода — его вес в среднем. Со знаком минус — собственная информация исхода: чем он реже, тем больше. Исходы с $p_i = 0$ в сумму не входят: $p\log_2 p \to 0$ при $p \to 0$. Пример: у честной монеты $H = 1$ бит, у честного кубика $\log_2 6 \approx 2{,}58$ бита. Монета, которая выпадает гербом в $90$ % бросков, даёт лишь $0{,}47$ бита: исход почти всегда предсказуем. Распределение $\left(\frac12;\ \frac14;\ \frac18;\ \frac18\right)$ даёт $\frac12 \cdot 1 + \frac14 \cdot 2 + \frac18 \cdot 3 + \frac18 \cdot 3 = 1{,}75$ бита.

Буква «ъ» в русских текстах очень редкая. Сколько информации несёт каждая буква длинного сообщения «ъъъъъъъъъъ…», если отправитель всегда шлёт только твёрдые знаки?

Ноль бит Много: «ъ» — редкая буква $\log_2 32 = 5$ бит

Информация зависит не от символа, а от распределения, из которого он выбран. Источник, который всегда шлёт одно и то же, ничего не сообщает: его исход известен заранее, $-\log_2 1 = 0$.

Почему у кубика энтропия больше, чем у монеты, понятно: вариантов больше. А какое распределение на $n$ исходах самое непредсказуемое? Ответ даёт неравенство, на котором стоит вся теория информации.

Хитрость в том, что график логарифма лежит под своей касательной, а центр масс точек, лежащих под прямой, тоже под ней.

Натуральный логарифм лежит под касательной в точке $1$: $\ln x \le x - 1$ при всех $x > 0$, и равенство только при $x = 1$. Действительно, у функции $f(x) = x - 1 - \ln x$ производная $1 - \frac1x$ отрицательна при $x < 1$ и положительна при $x > 1$, поэтому наименьшее значение функции — $f(1) = 0$ (глава 27). Разность правой и левой частей неравенства равна $-\sum p_i\log_2\frac{q_i}{p_i}$ (сумма по тем $i$, где $p_i > 0$), а $\log_2 y = \frac{\ln y}{\ln 2}$. Нужно доказать, что $\sum p_i \ln x_i \le 0$, где $x_i = \frac{q_i}{p_i}$. Положим в точки $(x_i;\ \ln x_i)$ на графике грузы $p_i$. Центр масс этих грузов имеет абсциссу $\sum p_i x_i = \sum q_i \le 1$ (сумма по $p_i > 0$) и ординату $\sum p_i \ln x_i$ — ровно то, что нужно оценить. Все грузы лежат на графике, а значит, не выше прямой $y = x - 1$; их центр масс тоже не выше: $\sum p_i\ln x_i \le \sum p_i (x_i - 1) = \sum q_i - 1 \le 0$. Это и есть неравенство Гиббса. Равенство требует, чтобы каждый груз лежал на касательной, то есть $x_i = 1$ и $q_i = p_i$ при $p_i > 0$, и чтобы $\sum_{p_i > 0} q_i = 1$. Тогда на исходы с $p_i = 0$ не остаётся ничего, а все $q_i$ положительны — значит, таких исходов нет, и $p_i = q_i$ всюду.

Задуманный исход равен одному из пяти вариантов с вероятностями $\frac12$, $\frac14$, $\frac18$, $\frac1{16}$, $\frac1{16}$. Чему равна энтропия этого распределения в битах? Столько вопросов «да/нет» в среднем и нужно, если спрашивать разумно.

$H = \frac12 \cdot 1 + \frac14 \cdot 2 + \frac18 \cdot 3 + \frac1{16} \cdot 4 + \frac1{16} \cdot 4 = \frac12 + \frac12 + \frac38 + \frac14 + \frac14 = \frac{15}8 = 1{,}875$ бита. Стратегия: «это первый вариант?», если нет — «второй?», если нет — «третий?», если нет — «четвёртый?». Первый угадывается за один вопрос, второй за два, третий за три, четвёртый и пятый за четыре; в среднем как раз $1{,}875$ вопроса. Для сравнения: равномерно по пяти вариантам нужно $\log_2 5 \approx 2{,}32$ бита.

Код Хаффмана

Энтропия — не только мера неопределённости, но и цена записи. Вот задача криптографа наоборот: не спрятать сообщение, а передать его как можно короче. Запишем каждую букву цепочкой нулей и единиц. Равномерный код тратит на каждую из $32$ букв по $5$ бит. Выгоднее давать частым буквам короткие коды, а редким — длинные. Так устроена азбука Морзе: самая частая английская буква E передаётся одной точкой.

У кодов разной длины есть опасность. Если «а» — это $0$, а «б» — $01$, то как прочесть $001$: «аб» или «аа» и обрывок? Морзе спасают паузы между знаками. Без пауз спасает правило: ни одно кодовое слово не должно быть началом другого.

Частота $i$-й буквы. Длина её кодового слова в битах. Пример: буквы с частотами $\frac12$, $\frac14$, $\frac18$, $\frac18$ и код $0$, $10$, $110$, $111$ дают $L = \frac12 \cdot 1 + \frac14 \cdot 2 + \frac18 \cdot 3 + \frac18 \cdot 3 = 1{,}75$ бита на букву — ровно энтропию этого распределения. Равномерный код для четырёх букв тратил бы по $2$ бита.

Короткие слова в префиксном коде — дефицит: если $0$ уже занят, все слова, начинающиеся с нуля, запрещены, и половина возможностей потеряна. Точный учёт этого дефицита — одно неравенство.

Хитрость в том, чтобы превратить каждое кодовое слово в кусочек отрезка $[0;\,1)$.

Кодовому слову $w = w_1w_2\dots w_\ell$ сопоставим двоичную дробь $0{,}w_1w_2\dots w_\ell$ и промежуток $\bigl[0{,}w;\ 0{,}w + 2^{-\ell}\bigr)$ длины $2^{-\ell}$: в нём лежат все двоичные дроби, запись которых начинается с $w$. Слову $0$ достаётся левая половина отрезка, слову $10$ — третья четверть, слову $110$ — седьмая восьмушка. Если $w$ — начало слова $v$, то промежуток $v$ лежит внутри промежутка $w$: дописывание цифр только сужает круг дробей. Если же ни одно из слов не начало другого, то в какой-то позиции у одного стоит $0$, а у другого $1$, и их промежутки не пересекаются. У префиксного кода промежутки попарно не пересекаются и все лежат в $[0;\,1)$, поэтому сумма их длин не больше единицы: $\sum 2^{-\ell_i} \le 1$. Обратно: упорядочим длины по возрастанию и будем класть промежутки длин $2^{-\ell_1}, 2^{-\ell_2}, \dots$ вплотную друг к другу, начиная с нуля. Неравенство гарантирует, что все поместятся в $[0;\,1)$. Очередной промежуток начинается в точке, равной сумме предыдущих длин $2^{-\ell_j}$ с $\ell_j \le \ell_i$, — это кратное $2^{-\ell_i}$, и его двоичная запись укладывается в $\ell_i$ знаков. Эти знаки и будут кодовым словом: промежуток слова совпадает с положенным промежутком, промежутки не пересекаются, значит, код префиксный.

Теперь можно доказать, что энтропия — предел сжатия.

Лишний бит — плата за целые длины. Её можно сделать сколь угодно малой, если кодировать не буквы, а блоки по $k$ букв: для независимых букв энтропия блока равна $kH$, код блоков тратит меньше $kH + 1$ бит, то есть меньше $H + \frac1k$ бита на букву. Это и есть теорема Шеннона о кодировании источника: сжать сообщение сильнее, чем до $H$ бит на символ, нельзя, а приблизиться к этой границе — можно.

Остался практический вопрос: как найти код с наименьшей средней длиной? В 1951 году его решил аспирант Массачусетского технологического института Дэвид Хаффман. По известному рассказу, профессор Роберт Фано предложил студентам курса по теории информации на выбор: сдать экзамен или написать работу о поиске оптимального кода. Фано не сказал, что вместе с Шенноном сам искал такой способ и не нашёл. Хаффман уже собирался сдаваться и готовиться к экзамену, когда придумал строить дерево кода не сверху, а снизу — от самых редких букв. Статья вышла в 1952 году.

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

Префиксный код — это двоичное дерево: кодовые слова — пути от корня к листьям, влево $0$, вправо $1$, длина слова — глубина листа. В оптимальном дереве у каждой внутренней вершины два потомка: если потомок один, его можно поднять на место родителя, и все слова под ним станут на бит короче. Пусть $x$ и $y$ — две наименее вероятные буквы. Возьмём оптимальное дерево и в нём самый глубокий лист. У его родителя два потомка, и второй тоже лист наибольшей глубины: глубже в дереве ничего нет. Переставим $x$ и $y$ на места этих двух листьев. Средняя длина при этом не растёт. Если буква $x$ с глубиной $\ell_x$ меняется местами с буквой $a$ с глубиной $\ell_a \ge \ell_x$, а $p_x \le p_a$, то длина меняется на $p_x\ell_a + p_a\ell_x - p_x\ell_x - p_a\ell_a = (p_a - p_x)(\ell_x - \ell_a) \le 0$. Значит, есть оптимальное дерево, в котором $x$ и $y$ — братья на самом глубоком уровне. Сольём братьев $x$ и $y$ в одну букву $z$ с вероятностью $p_x + p_y$. Получится дерево для $n - 1$ букв, в котором лист $z$ на один уровень выше. Для любого дерева, где $x$ и $y$ — братья, $L = L' + p_x + p_y$, где $L'$ — средняя длина после слияния: только слова $x$ и $y$ были на бит длиннее слова $z$. Индукция по $n$. Для двух букв коды $0$ и $1$ длины $1$ лучшие: короче слов не бывает. Пусть для $n - 1$ букв код Хаффмана оптимален. Для $n$ букв алгоритм сливает $x$ и $y$ и строит код Хаффмана для $n - 1$ букв, поэтому $L_{\text{Хаффман}} = L'_{\min} + p_x + p_y$. А по шагу 2 у оптимального кода $x$ и $y$ можно сделать братьями, и тогда его длина $L' + p_x + p_y \ge L'_{\min} + p_x + p_y$. Код Хаффмана не длиннее оптимального, то есть сам оптимален.

Четыре буквы встречаются с частотами $40$ %, $30$ %, $20$ % и $10$ %. Найдите среднюю длину кода Хаффмана в битах на букву.

Сливаем две редкие: $0{,}1 + 0{,}2 = 0{,}3$. Остались $0{,}4$, $0{,}3$ и $0{,}3$; сливаем две по $0{,}3$ в $0{,}6$. Последнее слияние: $0{,}4 + 0{,}6$. Глубины листьев: у буквы с частотой $0{,}4$ — $1$, у $0{,}3$ — $2$, у $0{,}2$ и $0{,}1$ — по $3$. Средняя длина $0{,}4 \cdot 1 + 0{,}3 \cdot 2 + 0{,}2 \cdot 3 + 0{,}1 \cdot 3 = 1{,}9$ бита. Энтропия этого распределения $\approx 1{,}846$ бита, так что до предела осталось меньше $0{,}06$ бита, а равномерный код потратил бы $2$.

Сколько информации в букве

Вернёмся к вопросу, с которого начали: сколько информации несёт буква русского текста? Будем уточнять ответ, как криптограф, который узнаёт о языке всё больше.

Если бы $33$ буквы и пробел были равновероятны и независимы, каждый символ нёс бы $\log_2 34 \approx 5{,}09$ бита. Учёт частот снижает оценку: у неравномерного распределения энтропия меньше максимума. Посчитайте её в виджете с кодом Хаффмана на тексте этой главы — выйдет около $4{,}4$ бита. Учёт связи с предыдущей буквой снижает ещё. Покажем это на модели Маркова, где различаются только гласные и согласные. Без памяти каждый символ «гласная или согласная» несёт $H(0{,}432) \approx 0{,}987$ бита. С памятью неопределённость другая: после гласной выбор идёт между вероятностями $0{,}128$ и $0{,}872$, после согласной — между $0{,}663$ и $0{,}337$. Усредним энтропии этих выборов по стационарному распределению:

$$0{,}432 \cdot H(0{,}128) + 0{,}568 \cdot H(0{,}663) \approx 0{,}432 \cdot 0{,}551 + 0{,}568 \cdot 0{,}922 \approx 0{,}762 \text{ бита}.$$

Знание предыдущей буквы снимает почти четверть неопределённости. Чем длиннее память, тем меньше остаётся. В 1951 году Шеннон поставил опыт: испытуемый угадывал английский текст буква за буквой, зная всё предыдущее, а Шеннон записывал, с какой попытки угадана каждая буква. По этим данным он оценил энтропию английского текста при длинном контексте — от $0{,}6$ до $1{,}3$ бита на букву, то есть около бита. Из $4{,}75$ бита, которые мог бы нести каждый из $27$ символов — $26$ букв и пробела, — язык использует лишь около четверти.

Уже в статье 1948 года Шеннон писал, что избыточность английского — около $50$ %, если учитывать связи на расстоянии до восьми букв; с длинным контекстом она доходит примерно до $75$ %. Избыточность — не расточительство, а страховка. Смсл ткст пнтн дж бз глснх бкв: вы только что прочли фразу, из которой выброшены все гласные. Опечатку в слове мы не замечаем, в шумном зале понимаем собеседника, и всё это благодаря избыточности. Коды, исправляющие ошибки, добавляют избыточность к данным специально и по расчёту — об этом глава о кольцах и полях.

Предсказание и сжатие — две стороны одного и того же. Чем увереннее модель угадывает следующий символ, тем меньше бит нужно, чтобы записать, что было на самом деле: если модель давала настоящему символу вероятность $p$, хороший кодировщик потратит на него около $-\log_2 p$ бит. Архиваторы строят модель текста на лету и кодируют по ней. А языковые модели, как «Росток», учатся ровно на этой величине: их ошибка при обучении — средняя собственная информация настоящего следующего символа, $-\log p$, обычно в натуральных логарифмах. Модель, которая пишет убедительно, — это модель, которая хорошо сжимает, и наоборот.

Считать энтропии, длины кодов и стационарные распределения можно в тренажёре.

Куда дальше

В этой главе мы свободно пользовались словами «доказательство», «множество», «бесконечность». Мы доказывали от противного и по индукции, рассуждали о множестве всех префиксных кодов и о цепи, которая шагает бесконечно. В прошлых главах было то же самое: «для любого $\varepsilon$ найдётся $\delta$», «существует базис», «для всех натуральных $n$». Но что именно значит «для всех» и «существует»? Почему из ложного утверждения следует что угодно, и почему «множество всех множеств» ведёт к противоречию? На чём стоит всё здание математики, расскажет глава 51.