Двоичное кодирование

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 26 · страница 26.2
Двоичное кодирование
Алгоритм Хаффмана и оптимальные коды.
Алгоритм Хаффмана
строит оптимальный префиксный код: частые символы получают короткие коды, редкие — длинные.
ФГОС
ОГЭ №2
ЕГЭ №4
Связь.
Хаффман использует дерево из
главы 25
и принцип жадного выбора: объединяем два символа с наименьшими частотами.
01
Равномерные и неравномерные коды
Равномерный код
— все кодовые слова одной длины (например, ASCII использует 8 бит для каждого символа).
Неравномерный код
— слова разной длины (например, код Морзе, код Хаффмана).
Сравнение
Текст «ААББВ» (A:5, B:3, C:2):
Равномерный 2-битный:
10 символов × 2 =
20 бит
Хаффман:
A=0 (1), B=10 (2), C=110 (3) → 5×1 + 3×2 + 2×3 =
17 бит
Экономия: 3 бита (15%).
02
Алгоритм Хаффмана
Идея
Жадный алгоритм: частые символы → короткие коды, редкие → длинные. Оптимальность доказана.
Алгоритм
Создать лист для каждого символа с его частотой.
Повторять: взять два узла с наименьшей частотой, объединить в новый узел (сумма частот).
До тех пор, пока не останется один узел (корень).
Присвоить 0 на левом ребре, 1 на правом. Путь до листа = код.
🔧
Построитель кода Хаффмана
Текст или частоты (A:5, B:3, C:7)
03
Средняя длина и энтропия
Средняя длина кода:
L = Σ pᵢ × lᵢ   (сумма частоты × длина для всех символов)
Энтропия Шеннона:
H = − Σ pᵢ × log₂(pᵢ)   (минимальная возможная средняя длина)
Для оптимального кода:
L ≈ H
. Разница — избыточность кода.
Пример
Символы A(p=0.5), B(p=0.25), C(p=0.125), D(p=0.125):
H = −(0.5·log₂0.5 + 0.25·log₂0.25 + 0.125·log₂0.125 + 0.125·log₂0.125) = 1.75 бит
Хаффман: A=0, B=10, C=110, D=111 → L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 бит
Оптимальный код достигает энтропии!
04
Калькулятор эффективности
📊
Сравнение равномерного и Хаффмана
Частоты (символ:частота, через запятую)
🎯
Мини-тест: 5 вопросов
XP: 0
🧩
Проверь себя
5 вопросов по кодированию · 20 XP за каждый правильный ответ