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

Коды Шеннона — Фано — это один из первых алгоритмов сжатия данных с потерями и без потерь, основанный на неравномерном кодировании символов в зависимости от частоты их появления. Метод был предложен Клодом Шенноном и Робертом Фано в 1948—1949 годах и является предшественником более эффективного алгоритма Хаффмана.

¶История

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

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

¶Принцип работы

¶Основная идея

Алгоритм Шеннона — Фано строит префиксный код, то есть код, в котором ни одно кодовое слово не является началом другого. Это позволяет однозначно декодировать сообщение без использования разделителей.

¶Построение кода

1. Подсчёт частот: для каждого символа в исходном сообщении определяется частота его появления.
2. Сортировка: символы упорядочиваются по убыванию частоты.
3. Разделение: список символов делится на две части так, чтобы суммы частот в каждой части были как можно ближе друг к другу.
4. Присвоение битов: первой части присваивается бит «0», второй — «1».
5. Рекурсия: для каждой части процедура повторяется, пока в каждой части не останется по одному символу.

¶Пример

Пусть имеется сообщение из символов A, B, C, D с частотами: A — 5, B — 3, C — 2, D — 1.

1. Сортировка: A (5), B (3), C (2), D (1).
2. Разделение на две части с близкими суммами: {A} (5) и {B, C, D} (3+2+1=6).
3. Присвоение: A → 0, остальные → 1.
4. Для подмножества {B, C, D}: разделение на {B} (3) и {C, D} (2+1=3). B → 10, {C, D} → 11.
5. Для {C, D}: C → 110, D → 111.

Итоговые коды: A — 0, B — 10, C — 110, D — 111.

¶Характеристики

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

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

¶Оптимальность

В отличие от кодов Хаффмана, коды Шеннона — Фано не гарантируют минимальной средней длины кодового слова. В некоторых случаях средняя длина может быть на несколько процентов больше теоретического минимума (энтропии источника). Это связано с тем, что алгоритм не всегда находит наилучшее разбиение на каждом шаге.

¶Скорость работы

Алгоритм имеет сложность O(n log n) из-за необходимости сортировки символов по частоте, где n — количество различных символов. Для сжатия больших объёмов данных это приемлемо, но уступает более современным методам (например, арифметическому кодированию).

¶Применение

¶Историческое

В 1950-е годы коды Шеннона — Фано применялись в ранних системах сжатия данных, таких как кодирование факсимильных сообщений и телеметрических данных. Однако с появлением алгоритма Хаффмана (1952) и более эффективных методов (LZ77, LZW, арифметическое кодирование) они были вытеснены.

¶Современное

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

¶Сравнение с другими методами

¶Коды Хаффмана

Алгоритм Хаффмана, предложенный Дэвидом Хаффманом в 1952 году, является улучшением метода Шеннона — Фано. Он гарантирует построение оптимального префиксного кода для заданного набора частот. Хаффман использует построение бинарного дерева слиянием наименее частых символов, что даёт более короткие средние длины кодовых слов. В отличие от Шеннона — Фано, код Хаффмана всегда является оптимальным (минимальная средняя длина среди всех префиксных кодов).

¶Арифметическое кодирование

Арифметическое кодирование, разработанное в 1970-х годах, не использует отдельные коды для каждого символа, а представляет всё сообщение как одно число в интервале [0, 1). Этот метод позволяет достичь средней длины, сколь угодно близкой к энтропии, и эффективнее сжимает данные с неравномерным распределением вероятностей.

¶Критика

Основной недостаток кодов Шеннона — Фано — неоптимальность. В некоторых случаях, особенно при неравномерном распределении частот, средняя длина кодового слова может значительно превышать энтропию. Например, при частотах символов 0.4, 0.4, 0.1, 0.1 алгоритм может дать среднюю длину 2.0 бита, тогда как энтропия составляет около 1.72 бита, а код Хаффмана даёт 1.8 бита.

Кроме того, алгоритм чувствителен к порядку сортировки: при одинаковых частотах разные варианты разделения могут давать разные коды, не все из которых оптимальны.

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

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

¶Источники

• Shannon, C. E. (1948). «A Mathematical Theory of Communication». Bell System Technical Journal.
• Fano, R. M. (1949). «The Transmission of Information». Technical Report No. 65, Research Laboratory of Electronics, MIT.
• Huffman, D. A. (1952). «A Method for the Construction of Minimum-Redundancy Codes». Proceedings of the IRE.
• Cover, T. M., Thomas, J. A. (2006). «Elements of Information Theory». Wiley-Interscience.