Равномерные коды — все символы кодируются словами одинаковой длины. Неравномерные коды — разные символы получают коды разной длины, что позволяет экономить память.
Коды фиксированной длины: простота и надёжность
Равномерный код — код, в котором все символы алфавита кодируются кодовыми словами одинаковой длины.
Минимальная длина кода для N символов: k = ⌈log₂(N)⌉ бит.
Все символы位於 на одном уровне (глубина 2) — коды одинаковой длины.
Коды переменной длины: экономия за счёт частых символов
Неравномерный код — код, в котором разные символы кодируются словами разной длины.
Принцип: частые символы получают короткие коды, редкие — длинные.
Символы位於 на разных уровнях — A на глубине 1, B на глубине 2, C и D на глубине 3.
| Свойство | Равномерный | Неравномерный |
|---|---|---|
| Длина кода | Одинаковая | Разная |
| Декодирование | Простое (блоки) | Сложнее (нужен префиксный код) |
| Экономия | Нет | Да (до 30-50%) |
| Условие Фано | Всегда выполняется | Нужно проверять |
| Пример | ASCII, UTF-32 | Код Хаффмана, Морзе |
Введите сообщение и коды символов. Сравните равномерный и неравномерный варианты.
Как определить, сколько бит нужно для N символов
Введите количество символов — получите минимальную длину равномерного кода.
Практика: декодируйте двоичную строку по заданному коду
Задайте коды символов и двоичную строку для декодирования.