> shannon | fano | entropy <
// Shannon–Fano — нисходящее энтропийное кодирование для сжатия данных
На основе энтропии
Использует теорию информации для построения эффективных кодов переменной длины.
Подход сверху вниз
Рекурсивно делит символы на группы с близкими вероятностями.
Исторический алгоритм
Пионерный метод, повлиявший на современные алгоритмы сжатия.
>> техническая информация
Как работает кодирование Шеннона–Фано:
Кодирование Шеннона–Фано упорядочивает символы по частоте и рекурсивно делит их на две группы с максимально близкими суммарными вероятностями. Каждый раздел добавляет один бит к коду (0 для левой группы, 1 для правой). Результат — префиксный код переменной длины.
Пример кодирования:
Текст: "AAABBCD" Частоты: A:3, B:2, C:1, D:1 Разделение: [A] | [B,C,D] Коды: A: 0 B: 10 C: 110 D: 111 Закодированная последовательность: 0 0 0 10 10 110 111
Зачем использовать Shannon–Fano:
- >Просто реализовать
- >Хороший коэффициент сжатия
- >Историческая значимость
- >Удобен для обучения
- >Префиксные коды
>> часто задаваемые вопросы
Что такое кодирование Шеннона–Фано?
Кодирование Шеннона–Фано — это метод энтропийного кодирования, разработанный Клодом Шенноном и Робертом Фано в 1940‑е годы. Это один из первых алгоритмов, использующих коды переменной длины, основанные на вероятностях символов.
Shannon–Fano или Хаффман?
Оба метода создают коды переменной длины, но алгоритм Хаффмана оптимален и минимизирует среднюю длину кода. Shannon–Fano проще, но может давать несколько более длинные коды. Хаффман строит дерево снизу вверх, Shannon–Fano — сверху вниз.
Как выполняется разделение символов?
Символы сортируются по частоте и делятся на две группы с максимально близкими суммарными вероятностями. Этот процесс повторяется рекурсивно, пока в каждой группе не останется по одному символу.
Используется ли Shannon–Fano сегодня?
Сегодня Shannon–Fano в основном используется как исторический и учебный пример. На практике его почти полностью вытеснило кодирование Хаффмана, гарантирующее оптимальность. Однако Shannon–Fano остаётся полезным для объяснения принципов сжатия.
// Разобранный пример
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Примеры кода
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> Другие вопросы
В: Чем Шеннон — Фано отличается от Хаффмана?
О: Шеннон — Фано делит отсортированный список сверху вниз на две части с как можно более равной суммой частот; Хаффман строит дерево снизу вверх, объединяя самые редкие символы. Оптимальность Хаффмана доказана, у Шеннона — Фано — не всегда.
В: Всегда ли Шеннон — Фано оптимален?
О: Нет. В примере ему нужно 89 бит, а Хаффману 87. Оба дают беспрефиксные коды, но правило деления Шеннона — Фано может выбрать неудачные разрезы.
В: Где применяется Шеннон — Фано?
О: В основном как исторический и учебный метод (Клод Шеннон и Роберт Фано, 1948/49). Вариант есть в алгоритме IMPLODE формата ZIP; современные компрессоры используют Хаффмана или арифметическое кодирование.