Код Шеннона — Фано¶

Код Шеннона — Фано — это один из первых алгоритмов префиксного кодирования, разработанный для сжатия данных без потерь. Он относится к классу энтропийных кодов, то есть ставит в соответствие каждому символу исходного алфавита двоичное кодовое слово, длина которого обратно пропорциональна вероятности появления этого символа. Алгоритм был независимо предложен Клодом Шенноном и Робертом Фано в конце 1940-х годов и является предшественником более эффективного кода Хаффмана.

¶История

Клод Шеннон, основоположник теории информации, и Роберт Фано, его коллега по Массачусетскому технологическому институту (MIT), в 1948–1949 годах работали над методами эффективного кодирования сообщений. В 1948 году Шеннон опубликовал статью «Математическая теория связи», где заложил основы теории информации и ввёл понятие энтропии как меры неопределённости. Вскоре после этого Фано предложил простой рекурсивный алгоритм построения префиксного кода, основанный на разбиении множества символов на две примерно равновероятные группы. Шеннон, в свою очередь, разработал метод, основанный на кумулятивных вероятностях, который также приводил к построению префиксного кода. Оба подхода оказались эквивалентными по сути, и алгоритм получил двойное название — код Шеннона — Фано.

Несмотря на то, что код Шеннона — Фано не всегда даёт оптимальную длину кодового слова (в отличие от кода Хаффмана, опубликованного в 1952 году), он сыграл важную роль в развитии теории сжатия данных и является классическим примером рекурсивного построения кодовых деревьев.

¶Алгоритм построения

Алгоритм кодирования Шеннона — Фано строится на основе вероятностей появления символов в сообщении. Он состоит из следующих шагов:

1. Сортировка символов по убыванию вероятности. Все символы алфавита упорядочиваются от наиболее вероятного к наименее вероятному.
2. Разбиение на две группы. Множество символов делится на две части так, чтобы суммарные вероятности символов в каждой части были как можно ближе друг к другу. Это разбиение производится рекурсивно: сначала для всего алфавита, затем для каждой подгруппы, пока в каждой группе не останется один символ.
3. Присвоение кодовых слов. Каждому разбиению соответствует один бит кода: левой группе присваивается 0, правой — 1 (или наоборот). Таким образом, каждому символу ставится в соответствие последовательность битов, определяемая путём от корня дерева до листа.

¶Пример

Пусть дан алфавит из четырёх символов с вероятностями: A (0.5), B (0.25), C (0.125), D (0.125).

1. Сортируем: A (0.5), B (0.25), C (0.125), D (0.125).
2. Разбиваем на две группы: первая группа — символ A (0.5), вторая группа — B, C, D (0.5). Присваиваем A код 0.
3. Для второй группы (B, C, D) повторяем разбиение: B (0.25) и C, D (0.25). Присваиваем B код 10, а C и D — код 11.
4. Для группы C, D разбиваем: C (0.125) и D (0.125). Присваиваем C код 110, D — код 111.

Итоговые коды: A — 0, B — 10, C — 110, D — 111. Средняя длина кода: 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75 бит на символ.

¶Свойства

¶Префиксность

Код Шеннона — Фано является префиксным: ни одно кодовое слово не является началом другого. Это обеспечивает однозначное декодирование без необходимости в разделителях.

¶Эффективность

Средняя длина кодового слова для кода Шеннона — Фано всегда не меньше энтропии источника (по теореме Шеннона о кодировании источника) и не превосходит энтропии плюс 1 бит. Однако в ряде случаев код может быть неоптимальным: существуют распределения вероятностей, для которых код Хаффмана даёт меньшую среднюю длину. Например, для распределения с вероятностями {0.4, 0.3, 0.2, 0.1} код Шеннона — Фано может дать среднюю длину 1.9 бит, тогда как код Хаффмана — 1.8 бит.

¶Сложность

Алгоритм построения кода Шеннона — Фано имеет сложность O(n log n) из-за необходимости сортировки символов по вероятности. Рекурсивное разбиение требует O(n) операций, но общая сложность определяется сортировкой.

¶Сравнение с кодом Хаффмана

Код Шеннона — Фано и код Хаффмана решают одну и ту же задачу — построение префиксного кода с минимальной средней длиной, но разными методами.

На практике код Хаффмана почти полностью вытеснил код Шеннона — Фано из-за гарантированной оптимальности. Однако код Шеннона — Фано остаётся важным учебным примером и используется в некоторых специализированных приложениях, где простота реализации важнее минимальной длины кода.

¶Применение

Код Шеннона — Фано редко применяется в современных системах сжатия данных, уступив место более эффективным алгоритмам, таким как код Хаффмана, арифметическое кодирование и LZ-методы (LZ77, LZ78). Тем не менее, он используется в образовательных целях для иллюстрации принципов энтропийного кодирования. В некоторых ранних системах сжатия, например, в архиваторе Pack (1970-е годы), применялся вариант кода Шеннона — Фано.

¶Критика

Основной недостаток кода Шеннона — Фано — отсутствие гарантии оптимальности. В некоторых случаях, особенно при сильно неравномерных распределениях вероятностей, код может быть значительно длиннее оптимального. Кроме того, алгоритм требует точного знания вероятностей символов, что не всегда возможно на практике. Для адаптивного кодирования, где вероятности меняются в процессе обработки данных, код Шеннона — Фано не подходит.

¶Интересные факты

• Код Шеннона — Фано был разработан практически одновременно с кодом Хаффмана, но Хаффман, будучи студентом Фано, предложил более эффективный метод, который впоследствии стал стандартом.
• В некоторых источниках код Шеннона — Фано называют «кодом Шеннона — Фано — Элиаса» из-за схожести с методом арифметического кодирования, предложенным Питером Элиасом.
• Алгоритм лёг в основу более сложных методов, таких как кодирование с помощью дерева разбиения (partition tree coding).

¶Источники

• Шеннон, К. Математическая теория связи. — 1948.
• Fano, R. M. Transmission of Information. — MIT Press, 1961.
• Cover, T. M., Thomas, J. A. Elements of Information Theory. — 2nd ed. — Wiley, 2006.
• Huffman, D. A. A Method for the Construction of Minimum-Redundancy Codes. — Proceedings of the IRE, 1952.