Энтропийное кодирование¶

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

¶История

Идея кодирования с переменной длиной кода восходит к телеграфии XIX века, когда для сокращения времени передачи сообщений использовались короткие коды для часто встречающихся букв (например, код Морзе). Однако теоретическое обоснование энтропийного кодирования было дано Клодом Шенноном в его работе «Математическая теория связи» (1948). Шеннон ввёл понятие энтропии как меры неопределённости источника и доказал, что минимальная средняя длина кода для источника без памяти равна его энтропии.

В 1952 году Дэвид Хаффман предложил алгоритм построения оптимального префиксного кода для заданного распределения вероятностей, который до сих пор остаётся одним из самых распространённых методов энтропийного кодирования. В 1970-х годах были разработаны арифметическое кодирование (Дж. Риссанен, 1976) и его модификации, позволяющие достигать энтропийного предела с произвольной точностью. В 1980-х годах появились адаптивные версии алгоритмов, не требующие априорного знания вероятностей.

¶Теоретические основы

¶Энтропия источника

Энтропия \( H \) дискретного источника без памяти, выдающего символы из алфавита \( \{a_1, a_2, \dots, a_n\} \) с вероятностями \( p_1, p_2, \dots, p_n \), определяется по формуле Шеннона:

\[ H = -\sum_{i=1}^{n} p_i \log_2 p_i \]

(бит на символ). Энтропия задаёт нижнюю границу средней длины кодового слова \( \bar{L} \) для любого обратимого кодирования: \( \bar{L} \ge H \). Чем ближе средняя длина к энтропии, тем эффективнее кодирование.

¶Условие префиксности

Для однозначного декодирования кодовых слов переменной длины необходимо, чтобы код был префиксным (ни одно кодовое слово не является началом другого). Префиксные коды могут быть представлены в виде бинарного дерева, где листья соответствуют символам, а пути от корня к листьям — кодовым словам.

¶Основные методы

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

Код Хаффмана строится путём итеративного слияния двух наименее вероятных символов в один узел с суммарной вероятностью. Процесс повторяется до получения корневого узла. Кодовые слова формируются путём присвоения битов (0 и 1) рёбрам дерева. Алгоритм гарантирует минимальную среднюю длину кода для заданного распределения вероятностей среди всех префиксных кодов.

Достоинства:

• Простота реализации и высокая скорость кодирования/декодирования.
• Оптимальность для фиксированного распределения вероятностей.

Недостатки:

• Требует априорного знания вероятностей (или их оценки).
• При неравномерном распределении вероятностей может быть неэффективным для символов с очень малой вероятностью (длина кода округляется до целого числа битов).
• Не достигает энтропийного предела, если вероятности не являются степенями 1/2.

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

Арифметическое кодирование представляет всё сообщение как одно число в интервале [0, 1). Интервал последовательно сужается в зависимости от вероятностей символов. В отличие от кода Хаффмана, оно кодирует не отдельные символы, а всю последовательность целиком, что позволяет приблизиться к энтропийному пределу с произвольной точностью.

Достоинства:

• Высокая эффективность сжатия, близкая к теоретическому пределу.
• Не требует округления длины кода до целого числа битов на символ.

Недостатки:

• Более сложная реализация, особенно для больших сообщений (требуется арифметика произвольной точности).
• Меньшая скорость по сравнению с кодом Хаффмана.
• Чувствительность к ошибкам (один битовый сбой может разрушить всё сообщение).

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

Метод, предложенный Шенноном и Фано (1948), заключается в сортировке символов по убыванию вероятности и рекурсивном разбиении на две группы с примерно равными суммарными вероятностями. Каждой группе присваивается бит (0 или 1). Код Шеннона — Фано не всегда оптимален (может давать среднюю длину больше, чем код Хаффмана), но исторически предшествовал алгоритму Хаффмана.

¶Универсальные коды

Для кодирования целых чисел без априорного распределения используются универсальные коды, такие как код Элиаса (гамма-, дельта-, омега-коды), код Левенштейна, код Фибоначчи. Они не требуют знания вероятностей, но их эффективность зависит от распределения чисел.

¶Применение

¶Сжатие данных

Энтропийное кодирование является финальным этапом во многих алгоритмах сжатия без потерь:

• Архиваторы: ZIP, gzip, bzip2 (используют код Хаффмана или арифметическое кодирование).
• Изображения: PNG (код Хаффмана после фильтрации), JPEG (код Хаффмана для квантованных коэффициентов).
• Аудио: FLAC (код Хаффмана для остатков предсказания), MP3 (код Хаффмана для квантованных спектральных данных).
• Видео: H.264, H.265, VP9, AV1 (коды Хаффмана и арифметическое кодирование для энтропийного кодирования синтаксических элементов и остатков).

¶Телекоммуникации

В системах связи энтропийное кодирование используется для уменьшения избыточности передаваемых данных:

• Протоколы: HTTP/2 (HPACK — сжатие заголовков с использованием кода Хаффмана), MQTT (сжатие сообщений).
• Спутниковая и сотовая связь: кодирование речи и видео (например, в кодеках AMR, EVS).

¶Криптография

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

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

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

• Алгоритм Хаффмана был разработан Дэвидом Хаффманом в 1952 году как курсовая работа по теории информации. Его преподаватель Роберт Фано предложил студентам задачу построения оптимального кода, и Хаффман решил её, доказав оптимальность своего алгоритма.
• Арифметическое кодирование долгое время не использовалось на практике из-за патентных ограничений (патенты IBM и других компаний истекли в 2000-х годах). Сейчас оно широко применяется в современных кодеках (например, AV1, HEVC).
• В стандарте сжатия JPEG используется код Хаффмана, но в последних версиях (JPEG XL) добавлена поддержка арифметического кодирования для повышения степени сжатия.

¶Источники

• Шеннон К. Математическая теория связи. — 1948.
• Huffman D. A. A Method for the Construction of Minimum-Redundancy Codes // Proceedings of the IRE. — 1952. — Vol. 40, No. 9. — P. 1098–1101.
• Rissanen J., Langdon G. G. Arithmetic Coding // IBM Journal of Research and Development. — 1979. — Vol. 23, No. 2. — P. 149–162.
• Sayood K. Introduction to Data Compression. — 5th ed. — Morgan Kaufmann, 2017.
• Salomon D. Data Compression: The Complete Reference. — 4th ed. — Springer, 2007.