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

Зачем это в ЕГЭ. В задании 4 проверяется умение работать с кодированием информации, включая равномерные и неравномерные коды. Это задание оценивается в 1 первичный балл и встречается практически в каждом варианте ЕГЭ.

Главная идея. Равномерные коды используют одинаковое количество бит для каждого символа, а неравномерные — разное. Ключ к решению — понимание, как минимизировать длину сообщения при заданных частотах символов.

Алгоритм (чеклист).
1. Определи частоту каждого символа в сообщении.
2. Для равномерного кода вычисли количество бит на символ, исходя из мощности алфавита.
3. Для неравномерного кода используй метод Хаффмана или другой метод минимизации длины кода.
4. Вычисли общую длину сообщения, умножив частоту каждого символа на длину его кода.
5. Проверь, что сумма длин всех кодов соответствует длине сообщения.

Опоры (кратко).
- Формула для равномерного кода: $L = \lceil \log_2 N \rceil$, где $N$ — мощность алфавита.
- Метод Хаффмана: строим дерево, начиная с символов с наименьшей частотой.
- Формула для общей длины сообщения: $L_{\text{общ}} = \sum_{i} f_i \cdot l_i$, где $f_i$ — частота символа, $l_i$ — длина его кода.

Пример 1 (равномерный код).
Дано сообщение из символов A, B, C, D с частотами 2, 3, 4, 1 соответственно.
Шаг 1. Мощность алфавита $N = 4$.
Шаг 2. Длина кода для каждого символа: $L = \lceil \log_2 4 \rceil = 2$ бита.
Шаг 3. Общая длина сообщения: $L_{\text{общ}} = 2 \cdot 2 + 3 \cdot 2 + 4 \cdot 2 + 1 \cdot 2 = 20$ бит.
Шаг 4. Проверка: сумма частот $2 + 3 + 4 + 1 = 10$, умноженная на длину кода $2$, даёт $20$ бит.

Пример 2 (неравномерный код).
Дано сообщение из символов A, B, C, D с частотами 2, 3, 4, 1 соответственно.
Шаг 1. Построим дерево Хаффмана: объединяем символы с наименьшими частотами (D и A).
Шаг 2. Новый узел имеет частоту $1 + 2 = 3$.
Шаг 3. Следующий шаг: объединяем B и новый узел (частоты 3 и 3).
Шаг 4. Последний шаг: объединяем C и получившийся узел (частоты 4 и 6).
Шаг 5. Коды: C — 0, B — 10, A — 110, D — 111.
Шаг 6. Общая длина сообщения: $4 \cdot 1 + 3 \cdot 2 + 2 \cdot 3 + 1 \cdot 3 = 19$ бит.

Типичные ошибки.
1. Неправильное вычисление длины равномерного кода. Например, забывают округлить вверх $\log_2 N$.
2. Ошибки в построении дерева Хаффмана. Например, объединяют не те символы.
3. Неправильный подсчёт общей длины сообщения. Например, забывают умножить частоту на длину кода.
4. Путаница между равномерным и неравномерным кодами. Например, применяют метод Хаффмана для равномерного кода.

Дальше. Изучите методы сжатия данных, такие как алгоритм LZW, для более глубокого понимания кодирования.