Что проверяет задание
Нужно построить или распознать двоичный префиксный код и по нему закодировать или декодировать сообщение, либо найти код с наименьшей суммарной длиной.
Определения
Алфавит, конечный набор символов, из которых составлены сообщения.
Код символа, последовательность нулей и единиц, сопоставленная этому символу.
Равномерный код, все кодовые слова одной длины. Тогда граница между символами определяется только длиной блока.
Неравномерный код, кодовые слова разной длины. Часто встречающимся символам выгоднее давать более короткие коды.
Префиксный код, ни одно кодовое слово не является началом (префиксом) другого. Тогда сообщение однозначно разбивается на символы слева направо без разделителей.
Условие Фано, формулировка префиксности: никакой код не служит началом другого кода.
Кодовое дерево, двоичное дерево, в котором левое ребро обычно означает 0, правое, 1. Символ лежит в листе. Путь от корня до листа и есть код символа.
Лист, вершина без потомков. Внутренняя вершина кодового дерева символом не кодируется.
Избыточность, запас свободных рёбер или неиспользованных коротких кодов. Она нужна, если требуется добавить ещё один символ, не нарушив префиксность.
Цена кода, суммарная длина закодированного сообщения. Она равна сумме по всем символам: (длина кода символа) × (число его вхождений).
Почему префиксность обязательна
Если код одного символа совпадает с началом кода другого, декодирование неоднозначно: можно «отрезать» символ слишком рано. Префиксный код исключает этот выбор.
Равномерный код всегда префиксный. Неравномерный, только если выполнен условие Фано.
Общий алгоритм решения
- Выписать алфавит и уже известные коды, если они даны.
- Проверить условие Фано: ни один код не должен быть префиксом другого.
- Если нужно построить коды, размещать символы в листьях двоичного дерева так, чтобы более частые символы были ближе к корню.
- Для кодирования заменить каждый символ сообщения его кодом и записать получившуюся битовую строку.
- Для декодирования идти по дереву бит за битом; достигнув листа, выписать символ и вернуться в корень.
- Если спрашивают минимальную длину, считать суммарную цену кода, а не «красивость» отдельных слов.