Энтропия информации

Что измеряет энтропия

Клод Шеннон в статье 1948 года поставил вопрос ребром: сколько информации несёт сообщение? Ответ оказался неожиданным для инженеров того времени — количество информации определяется не смыслом, а неожиданностью. Событие, которое происходит всегда, не несёт ничего. Событие, вероятность которого мала, несёт много.

Формально энтропия источника считается как сумма произведений вероятности каждого исхода на его логарифм с обратным знаком: H = −Σ p_i log₂ p_i. Логарифм по основанию 2 даёт результат в битах. Честная монета: два исхода по 0,5, энтропия ровно 1 бит. Честный шестигранный кубик: log₂ 6 ≈ 2,585 бита. Монета, которая в 99 случаях из 100 падает орлом, — всего 0,08 бита: почти всё известно заранее.

Максимум энтропии достигается при равномерном распределении и равен log₂ n, где n — число исходов. Любая неравномерность её снижает. Отсюда прямое практическое следствие: чем предсказуемее данные, тем меньше в них информации в шенноновском смысле, а значит, тем сильнее их можно сжать.

Энтропия как предел сжатия

Теорема Шеннона о кодировании источника утверждает: средняя длина кодового слова не может быть меньше энтропии источника, но может подойти к ней сколь угодно близко. Это не свойство конкретного архиватора, а физический предел, который не обходится никакими ухищрениями.

Русский текст даёт наглядный пример. Если считать 33 буквы равновероятными, получится log₂ 33 ≈ 5,04 бита на символ. Но буквы распределены неравномерно: «о» и «е» встречаются в десятки раз чаще «ъ», а сочетания подчиняются жёстким правилам — после «ъ» гласная обязательна, после «щ» не бывает «ы». Шеннон оценивал энтропию английского текста с учётом всего контекста в 0,6–1,3 бита на символ; для русского порядок тот же. Разница между 5 битами наивной оценки и полутора битами реальной энтропии и есть избыточность языка — именно её выедают архиваторы, о чём подробнее в материале про сжатие без потерь.

Алгоритмы подбираются под эту цель. Кодирование Хаффмана выдаёт короткие коды частым символам и длинные редким, приближаясь к энтропии с точностью до одного бита на символ. Арифметическое кодирование снимает и это ограничение, работая с дробными долями бита. Словарные методы вроде LZ77 идут другим путём — заменяют повторы ссылками, но упираются в тот же предел.

Энтропия в QR-кодах: почему режимов несколько

Стандарт QR не измеряет энтропию явно, но его конструкция построена ровно на этой логике: чем уже алфавит, тем меньше бит нужно на символ. Отсюда четыре режима кодирования вместо одного универсального.

Цифровой режим кодирует три цифры десятью битами. На цифру приходится 3,33 бита при теоретическом минимуме log₂ 10 ≈ 3,32 — перерасход меньше половины процента. Алфавитно-цифровой режим упаковывает два символа из набора в 45 знаков в 11 бит: 5,5 бита на символ против теоретических 5,49. Байтовый режим тратит 8 бит на байт без всякой оптимизации, а кириллица в UTF-8 занимает два байта на букву, то есть 16 бит на символ. Разница практическая: 100 цифр займут около 42 байт, а те же 100 знаков кириллического текста — 200 байт.

Вывод для того, кто собирает код: подбор содержимого под узкий алфавит экономит ёмкость эффективнее, чем понижение уровня коррекции. Ссылка в верхнем регистре с коротким доменом попадёт в алфавитно-цифровой режим и уместится в меньшую версию символа. Детали переключения между режимами разобраны в термине режимы кодирования QR, а таблицы предельных объёмов — в термине ёмкость QR-кода. Собрать и сравнить варианты можно прямо в генераторе QR-кодов: одна и та же ссылка в разном регистре даёт символы разного размера.

Энтропия паролей, ключей и случайности

Второе большое применение — оценка стойкости секретов. Здесь энтропия отвечает на вопрос, сколько вариантов придётся перебрать атакующему. Пароль из 8 символов, набранный случайно из 95 печатных ASCII-знаков, даёт 8 × log₂ 95 ≈ 52,6 бита. Парольная фраза из шести слов, выбранных честным броском кубиков из списка в 7776 слов, даёт 6 × log₂ 7776 ≈ 77,5 бита — заметно больше, хотя запоминается легче.

Ключевая оговорка: энтропия считается по процессу генерации, а не по внешнему виду результата. Пароль P@ssw0rd2026 выглядит сложным и набирает высокие баллы у наивных индикаторов, но выбран человеком по стандартному шаблону, поэтому его реальная энтропия в разы ниже формальной оценки по длине и алфавиту. Словари для перебора именно такие шаблоны и содержат.

Для криптографических ключей ориентир — 128 бит энтропии: этого достаточно, чтобы перебор был невозможен на любом мыслимом оборудовании. Хеш SHA-256 выдаёт 256 бит, но энтропия результата ограничена энтропией входа: хеш от четырёхзначного PIN-кода содержит не 256 бит неопределённости, а чуть меньше 14, и подбирается перебором всех десяти тысяч вариантов мгновенно. По той же причине генераторы случайных чисел в операционных системах оценивают запас энтропии, собранной с аппаратных источников, а не длину выданной строки. Общий взгляд на то, как данные превращаются в биты и обратно, даёт разбор самого понятия бит.

Частые вопросы

Почему энтропия измеряется в битах?

Потому что логарифм в формуле Шеннона берётся по основанию 2, а один бит — это неопределённость честного подбрасывания монеты. Величина в битах напрямую отвечает на инженерный вопрос: сколько двоичных разрядов в среднем нужно, чтобы записать один символ источника. При основании логарифма e единицу называют натом, при основании 10 — хартли, но в вычислительной технике прижились именно биты.

Можно ли сжать данные ниже их энтропии?

Без потерь — нет, это запрещено теоремой о кодировании источника. Любой алгоритм, который якобы сжимает произвольные данные вдвое, при повторном применении сжал бы их до одного бита, что невозможно по принципу Дирихле: разных входов больше, чем коротких выходов. Сильное сжатие достигается либо за счёт высокой избыточности конкретных данных, либо с потерями, когда часть информации выбрасывается намеренно.

Как оценить энтропию своего пароля?

Считать надо по способу генерации: логарифм по основанию 2 от числа равновероятных вариантов. Случайный выбор 12 символов из 95 даёт около 79 бит, четыре случайных слова из словаря на 7776 позиций — около 52 бит. Если пароль придуман человеком, честная оценка получится заметно ниже: людские шаблоны предсказуемы и уже занесены в словари для перебора.

Как энтропия связана с ёмкостью QR-кода?

Напрямую через выбор режима кодирования. Узкий алфавит означает низкую энтропию на символ, и стандарт позволяет тратить на него меньше бит: 3,33 бита на цифру против 8 бит на байт. Поэтому 100 цифр умещаются в существенно меньший символ, чем 100 произвольных байт. При кириллице каждая буква в UTF-8 занимает два байта, и код разрастается быстрее всего.

Энтропия в информатике и в физике — это одно и то же?

Формулы совпадают с точностью до постоянного множителя, и это не совпадение: и там, и там величина считает число микросостояний, совместимых с наблюдаемым макросостоянием. Больцман пришёл к ней в термодинамике, Шеннон — в теории связи. Физического тепла в информационной энтропии нет, но связь глубже, чем аналогия: принцип Ландауэра задаёт минимальную энергию, выделяемую при необратимом стирании одного бита.