Навіщо потрібна формула Шеннона

На «Теорії інформації та кодуванні» дійшли до формули Шеннона:

H(X) = -Σ p(x) log₂ p(x)

Дивився на неї й не міг зрозуміти, навіщо вона мені взагалі потрібна. Ймовірності, логарифми, якась абстрактна ентропія — чудовий набір, щоб закрити конспект і піти писати код 😅

Зрозуміліше стало після простого пояснення: формула показує, скільки інформації в середньому несе одне повідомлення. Чим рідше трапляється символ або подія, тим більше інформації дає її поява.

Уявімо чотири символи. Якщо вони трапляються однаково часто, кожен можна записувати двома бітами. Але якщо символ A займає 70% тексту, витрачати на нього стільки ж місця, як на рідкісний символ, — марнотратство.

Частому A можна дати короткий код, а рідкісним символам — довші. Завдяки цьому більша частина тексту записуватиметься меншою кількістю бітів. Вихідний текст не зміниться, але середній розмір одного символу зменшиться.

Ось навіщо потрібна статистика: вона показує, де дані передбачувані й де можна не витрачати зайві біти. На цьому принципі працює стиснення без втрат. Ентропія не стискає файл сама, але показує нижню межу його середнього розміру. Хаффман і арифметичне кодування вже намагаються підібратися до цієї межі 📦

З контрольними сумами логіка трохи інша. Великий файл перетворюється на коротке значення фіксованої довжини. Наприклад, контрольна сума довжиною 8 біт має лише 256 можливих значень.

Файлів може бути значно більше ніж 256. Отже, рано чи пізно два різні файли отримають однакову контрольну суму. Це і називається колізією: дані різні, а результат перевірки однаковий 🎭

Контрольна сума довжиною b біт має 2ᵇ можливих значень. Для однієї випадково пошкодженої копії шанс збігу з початковою сумою становить приблизно:

1 / 2ᵇ

Що більше бітів, то менша ймовірність пропустити випадкову помилку. Але якщо файлів багато, порівнюється вже величезна кількість пар, тому шанс хоча б однієї колізії зростає.

Формула Шеннона не створює алгоритм стиснення або готову контрольну суму. Вона дає основу для розрахунків: скільки інформації містять дані, скільки бітів потрібно для їх кодування та наскільки надійно коротке значення може їх розрізняти.

Коли це пояснили людською мовою, логарифм нарешті влаштувався на роботу 😄