Код Хаффмана и условие Фано
Как закодировать текст короче — и так, чтобы его можно было
прочитать обратно. 11 класс, углублённый уровень — пара вторая.
Продолжаем тему «Алгоритмы сжатия данных». На прошлой паре было RLE —
сжатие серий. Сегодня — коды, где частые буквы получают короткие кодовые
слова, а редкие — длинные.
Это же — задание 4 ЕГЭ: кодирование и декодирование, условие Фано. Здесь
хвост пары по программе и подготовка к экзамену совпадают.
Равномерный код
У всех букв кодовые слова одной длины. Какая длина нужна на n букв?
Нужно наименьшее i, при котором 2i ≥ n. Пример: 5 букв.
Три бита различают 23 = 8 слов, занято 5 —
ещё 3 буквы можно добавить, не удлиняя код.
Плюс равномерного кода — читать просто: режь поток по i бит. Минус — частая
буква «А» стоит столько же, сколько редкая «Ъ».
Неравномерный код и беда с ним
Дадим частым буквам короткие слова: А = 
, Б = 
,
В = 
. Пришло . Что это?
Два прочтения — сообщение
не декодируется
однозначно. Виновато то, что
— начало слова
.
Условие Фано
Ни одно кодовое слово не должно быть началом
другого кодового слова.
Годится
,
,
,
— ни одно не начало другого.
Код с условием Фано называют префиксным. Его поток читается
слева направо однозначно, без разделителей.
Какое слово ещё можно добавить к А = , Б = ?
Перебираем слова по длине:
Алгоритм Хаффмана
Строит префиксный код, при котором сообщение выходит самым коротким.
Частоты: А — 5, Б — 2, В — 1, Г — 1.
- Взять две наименьшие частоты и слить в один узел с весом-суммой.
- Повторять, пока не останется один узел.
Длина сообщения = сумма всех слияний:
2 + 4 + 9 = 15 бит.
Почему сумма слияний
При равных весах дерево строят по-разному, и коды
отдельных букв выходят разными — а сумма всегда одна. Поэтому в задачах
спрашивают длину сообщения, а не «код буквы Б».
Выигрыш против равномерного кода
Тот же пример: 4 буквы, в сообщении 5 + 2 + 1 + 1 = 9 букв.
выигрыш = K · i − (сумма слияний)
K — букв в сообщении, i — длина равномерного кода. Если частоты близки,
дерево выходит ровным и выигрыша нет: Хаффман помогает там, где буквы
встречаются по-разному часто.
Что делаем дальше
- Обзорный практикум — шесть задач, все сразу на странице, в любом
порядке: код Хаффмана, выигрыш против равномерного, условие Фано,
декодирование, равномерный код, проверка префиксности.
- Слияния и перебор слов — на черновике таблицей, как на слайдах.
- Ответ везде — целое число, без единиц.
Ошибся — сразу виден разбор, а «Новые числа» дают ту же задачу с другими
данными. Отметка: закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3».
За работу
Практикум «Код Хаффмана и условие Фано» — в общей папке и на
сайте. Не успел на уроке — пройди дома: вариант будет другой, сдаётся тем же
кодом.
Карточку в тетрадь можно взять с собой: на ней равномерный код, алгоритм
Хаффмана, условие Фано, декодирование и формула выигрыша.
: 
.