Условие
Буква A появляется с вероятностью 1/2, B и C — по 1/4. Используется префиксный код A→0, B→10, C→11. Найдите ожидаемую длину на символ, докажите оптимальность и вычислите энтропию и perplexity.
Средняя длина
E(L)=1·1/2+2·1/4+2·1/4=3/2 бита. Для n независимых букв ожидаемая длина архива 3n/2.
Энтропия
При log₂:
H=−[1/2·(−1)+1/4·(−2)+1/4·(−2)]=3/2 бита.
Perplexity=2^{3/2}=2√2≈2,828427.
Почему код оптимален
Для любого префиксного двоичного кода средняя длина не меньше энтропии. Здесь средняя длина точно равна H, поэтому улучшить её невозможно.
Это также код Хаффмана: две редкие категории объединяются в ветвь вероятности 1/2, а частая A получает одноразрядное слово.
Префиксность
Ни одно кодовое слово не является началом другого: 0 начинается с нуля, 10 и 11 — с единицы и различаются вторым битом. Поэтому сообщение декодируется однозначно без разделителей.
Борис Демешев и участники · mlearn_pro, задача 79 · CC BY 4.0. Пункты 1 и 3 ключа сохранены; доказательство оптимальности завершено.