Перейти к основному содержимому

Теория информации

НЕ ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ
Архитектору Инженеру

Теория информации (Клод Шеннон, 1948) измеряет передачу, хранение и обработку данных независимо от смысла. Текст, звук, картинка или телеметрия — для теории это последовательности символов с вероятностями.

Энтропия​

Энтропия H — средняя неопределённость символа источника (в битах на символ):

H = −Σ pᵢ · log₂(pᵢ) (сумма по всем символам алфавита с вероятностями pᵢ).

  • Равномерный алфавит — максимум для данного размера алфавита.
  • Перекошенные частоты (частая буква "а") — ниже H, больше избыточности, лучше сжимается.
  • Случайный шифротекст — энтропия близка к пределу, сжатие без потерь почти бесполезно.

Теорема Шеннона об источнике: средняя длина безпотерьного кода не может быть меньше энтропии источника. ZIP, Huffman, arithmetic coding приближаются к этому пределу. Прикладной разбор на примере PNG — Растровые форматы.

От частот к битам (числовой пример)​

Пусть источник выдаёт только A и B с вероятностями p(A)=0.8, p(B)=0.2:

Символpᵢ−pᵢ log₂ pᵢ (бит)
A0.8≈ 0.72
B0.2≈ 0.46
Сумма H≈ 1.18 бит/символ

Если кодировать оба символа по 1 биту, средняя длина 1 бит/символ — уже близко к пределу. При p(A)=0.99, p(B)=0.01 энтропия мала (~0.08 бит), а фиксированный 1 бит на символ — избыточность, которую Huffman и арифметическое кодирование "сжимают".

Play ITЗагрузка интерактивного демо…

Энтропия в коде (оценка по тексту)​


import math

from collections import Counter

def shannon_entropy(text: str) -> float:
    """Энтропия в битах на символ."""
    n = len(text)
    if n == 0:
        return 0.0
    counts = Counter(text)
    h = 0.0
    for c in counts.values():
        p = c / n
        h -= p * math.log2(p)
    return h

sample = "aaaaab" * 100 + "c" * 10
print(f"H ≈ {shannon_entropy(sample):.3f} бит/символ")

На короткой выборке оценки pᵢ шумные — для метрик в продакшене смотрят доверительные интервалы (см. вероятность и статистику).

Энтропия Шеннона и кросс-энтропия в ML​

ПонятиеФормула (идея)Интерпретация
Энтропия H(p)неопределённость истинного распределения меток"насколько трудно угадать класс"
Кросс-энтропия H(p, q)−Σ p(x) log q(x)штраф, если модель q плохо предсказывает реальные p
KL-дивергенцияH(p, q) − H(p)"лишняя" битовая цена неверной модели

В классификации кросс-энтропия — мера расхождения предсказанных вероятностей с one-hot меткой.

Кодирование и избыточность​

Практические коды добавляют избыточность для устойчивости к ошибкам (CRC, Reed–Solomon) — платят объёмом за надёжность канала.

Условная энтропия учитывает контекст: символы не независимы ("q" почти всегда за "u" в английском). Отсюда словарные методы (LZ) и предсказательное моделирование (PPM).

Пропускная способность канала​

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

В IT это объясняет:

  • выбор кодеков и протоколов с учётом BER;
  • trade-off между сжатием, latency и CPU;
  • почему "сжать уже сжатое" (jpeg повторно) не даёт выигрыша.

Инженерная иллюстрация: если байты файла выглядят как случайные (высокая энтропия), gzip почти не уменьшит размер; если в логах повторяются шаблоны (ERROR, user_id=), энтропия ниже — сжатие эффективнее.

Связь с безопасностью и данными​

  • Стойкость пароля — логарифм мощности пространства ключей; словари и утечки снижают эффективную энтропию.
  • Длина хеша — комбинаторика коллизий (см. дискретную математику).
  • ML — кросс-энтропия как мера "расстояния" распределений предсказания и метки.

Обзор блока: Математическая основа IT.

Содержание