Код Шеннона–Фано
Метод Шеннона–Фано (Клод Шеннон, Роберт Фано, 1948–1949) — исторически первый практический способ построить эффективный префиксный код. Он строит дерево «сверху вниз», деля символы на группы с близкими суммарными частотами. Метод прост и нагляден, но, в отличие от кода Хаффмана, не всегда оптимален.
Идея
Хороший код должен давать каждому биту как можно больше информации — в идеале по одному биту на двоичный символ. Для этого первый бит кодового слова должен делить все символы на две группы, которые встречаются одинаково часто: тогда «0» и «1» равновероятны. Затем то же самое повторяется внутри каждой группы.
Алгоритм
- Упорядочить символы по убыванию частоты.
- Разделить список на две части (не меняя порядок) так, чтобы суммы частот частей были как можно ближе.
- Символам первой части дописать к коду «0», второй — «1».
- Рекурсивно повторить для каждой части, пока в ней больше одного символа.
Поскольку разбиение делается по непрерывным отрезкам упорядоченного списка, лучшую точку раздела можно найти одним проходом: сумма левой части растёт, и нужно остановиться там, где разность сумм минимальна.
Пример: «абракадабра»
Упорядоченный список: а 5, б 2, р 2, к 1, д 1 (сумма 11).
| Группа | Разбиение | Суммы | Результат |
|---|---|---|---|
| а б р к д | а | б р к д | 5 и 6 | а → 0 |
| б р к д | б | р к д | 2 и 4 | б → 10 |
| р к д | р | к д | 2 и 2 | р → 110 |
| к д | к | д | 1 и 1 | к → 1110, д → 1111 |
Во второй строке разбиения «б | р к д» и «б р | к д» одинаково хороши (разность 2); выбор влияет на коды, но здесь не на итог. Длина слова: 5·1 + 2·2 + 2·3 + 1·4 + 1·4 = 23 бита — столько же, сколько у кода Хаффмана, хотя коды получились другие.
Шеннон–Фано против Хаффмана
| Шеннон–Фано | Хаффман | |
|---|---|---|
| Построение дерева | сверху вниз: делим группы | снизу вверх: объединяем редкие узлы |
| Оптимальность | не гарантирована | минимальная средняя длина среди префиксных кодов |
| Сложность | O(N log N) на сортировку + разбиения | O(N log N) с кучей |
| Префиксность | оба кода префиксные: символы стоят в листьях дерева | |
Вероятности 0,35; 0,17; 0,17; 0,16; 0,15.
- Шеннон–Фано: первое разбиение {0,35; 0,17} | {0,17; 0,16; 0,15} (0,52 и 0,48), длины 2, 2, 2, 3, 3, L = 2,31 бита.
- Хаффман: объединяем 0,15 + 0,16 = 0,31, затем 0,17 + 0,17 = 0,34, затем 0,31 + 0,34 = 0,65; длины 1, 3, 3, 3, 3, L = 0,35 + 3·0,65 = 2,30 бита.
Жадное деление «сверху» не может учесть, как разбиение повлияет на следующие уровни дерева.
Историческая справка
В статье 1948 года Шеннон предложил код, в котором длина слова символа равна ⌈−log₂ p_i⌉, а сами слова берутся из двоичной записи накопленных вероятностей. Фано независимо описал метод последовательного деления на равновероятные группы. Оба способа сегодня называют кодированием Шеннона–Фано. В 1952 году студент Фано Дэвид Хаффман, решая курсовую задачу, нашёл оптимальный алгоритм, построив дерево в обратном направлении.
Закодируйте одно и то же сообщение кодами Шеннона–Фано и Хаффмана и сравните длины битовых строк и форму деревьев. Открыть код Шеннона–Фано →
Вопросы для самопроверки
- Почему символы перед делением сортируют по убыванию частоты?
Ответ
Чтобы частые символы попадали в небольшие группы у вершины дерева и получали короткие коды, а точку раздела можно было искать среди непрерывных отрезков. - Постройте код Шеннона–Фано для частот 4, 2, 1, 1. Совпадает ли он с кодом Хаффмана по длинам?
Ответ
Разбиения 4 | 2 1 1, затем 2 | 1 1, затем 1 | 1: коды 0, 10, 110, 111 — длины совпадают с кодом Хаффмана. - Чему равна избыточность кода из примера «абракадабра»?
Ответ
R = 1 − H/L ≈ 1 − 2,04/2,09 ≈ 2,4%.