Alterna · 26.2 — Двоичное кодирование

Алгоритм Хаффмана строит оптимальный префиксный код: частые символы получают короткие коды, редкие — длинные.

ФГОСОГЭ №2ЕГЭ №4

Связь. Хаффман использует дерево из главы 25 и принцип жадного выбора: объединяем два символа с наименьшими частотами.

Равномерные и неравномерные коды

Равномерный код — все кодовые слова одной длины (например, ASCII использует 8 бит для каждого символа).

Неравномерный код — слова разной длины (например, код Морзе, код Хаффмана).

Текст «ААББВ» (A:5, B:3, C:2):

Экономия: 3 бита (15%).

Жадный алгоритм: частые символы → короткие коды, редкие → длинные. Оптимальность доказана.

Создать лист для каждого символа с его частотой.
Повторять: взять два узла с наименьшей частотой, объединить в новый узел (сумма частот).
До тех пор, пока не останется один узел (корень).
Присвоить 0 на левом ребре, 1 на правом. Путь до листа = код.

🔧Построитель кода Хаффмана

Текст или частоты (A:5, B:3, C:7)

Средняя длина кода:

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 бит

Оптимальный код достигает энтропии!

📊Сравнение равномерного и Хаффмана

Частоты (символ:частота, через запятую)

🎯

XP: 0

🧩Проверь себя

5 вопросов по кодированию · 20 XP за каждый правильный ответ