Двоичное кодирование · Алгоритм Хаффмана · Декодирование
Глава 26 посвящена префиксным кодам — кодам, которые декодируются однозначно без разделителей. Изучаем условие Фано, кодовое дерево, алгоритм Хаффмана и практику.
Глава 25 · Деревья — бинарные деревья, обход, двоичное дерево — фундамент для дерева кода.
Глава 27 · Энтропия — количественная мера информации, связь с оптимальным кодированием.
| Понятие | Формула | Описание |
|---|---|---|
| Условие Фано | Ни одно кодовое слово не префикс другого | Однозначное декодирование |
| Неравенство Крафта | ∑ 2−Li ≤ 1 | Условие существования префиксного кода |
| Хаффман | min-heap → дерево → коды | Жадный алгоритм оптимального кодирования |
| Средняя длина | L = Σ pᵢ × lᵢ | Взвешенная сумма длин по частотам |
| Энтропия | H = −Σ pᵢ log₂(pᵢ) | Минимальная возможная средняя длина |