Дерево Хаффмана

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

История

Идея оптимального кодирования возникла в контексте теории информации, заложенной Клодом Шенноном в 1940-х годах. Шеннон и Роберт Фано независимо друг от друга предложили метод построения префиксных кодов (код Шеннона — Фано), который, однако, не гарантировал оптимальности для произвольных распределений вероятностей.

В 1951 году Дэвид Хаффман, будучи аспирантом Массачусетского технологического института, под руководством профессора Роберта Фано получил задание разработать наиболее эффективный метод кодирования. Хаффман нашёл решение, которое оказалось проще и оптимальнее существовавших подходов. Его алгоритм, опубликованный в 1952 году в статье «A Method for the Construction of Minimum-Redundancy Codes», гарантирует построение кода с минимальной избыточностью для заданного набора вероятностей символов.

Основные понятия

Префиксный код

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

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

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

Двоичное дерево

Дерево Хаффмана — это полное двоичное дерево, в котором каждый внутренний узел имеет ровно два потомка. Листья дерева представляют символы исходного алфавита, а каждый внутренний узел — объединение двух подмножеств символов.

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

Алгоритм Хаффмана относится к классу жадных алгоритмов. Он последовательно объединяет два наименее вероятных символа (или группы символов) в один узел, пока не останется один корневой узел.

Шаги алгоритма

1. Подготовка: Для каждого символа исходного алфавита определяется его вероятность (или частота появления). Создаётся список листьев, каждый из которых содержит символ и его вероятность.
2. Построение очереди: Все листья помещаются в приоритетную очередь, где приоритетом является вероятность (чем меньше вероятность, тем выше приоритет).
3. Объединение: Из очереди извлекаются два элемента с наименьшими вероятностями. Создаётся новый внутренний узел, вероятность которого равна сумме вероятностей этих двух элементов. Этот узел становится родителем для извлечённых элементов. Новый узел помещается обратно в очередь.
4. Повторение: Шаг 3 повторяется до тех пор, пока в очереди не останется один элемент — корень дерева.
5. Назначение кодов: После построения дерева каждому левому ребру присваивается бит «0», а каждому правому — бит «1» (или наоборот). Кодовое слово для символа получается путём обхода от корня до соответствующего листа и записи битов вдоль пути.

Пример

Рассмотрим алфавит из четырёх символов с частотами: A — 5, B — 9, C — 12, D — 13, E — 16, F — 45.

1. Исходные листья: A(5), B(9), C(12), D(13), E(16), F(45).
2. Объединяем A(5) и B(9): новый узел AB(14).
3. Очередь: C(12), D(13), AB(14), E(16), F(45).
4. Объединяем C(12) и D(13): узел CD(25).
5. Очередь: AB(14), E(16), CD(25), F(45).
6. Объединяем AB(14) и E(16): узел ABE(30).
7. Очередь: CD(25), ABE(30), F(45).
8. Объединяем CD(25) и ABE(30): узел CDABE(55).
9. Очередь: F(45), CDABE(55).
10. Объединяем F(45) и CDABE(55): корень (100).

Коды (при условии, что левое ребро — 0, правое — 1):

• F: 0
• C: 100
• D: 101
• A: 1100
• B: 1101
• E: 111

Свойства

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

Код Хаффмана является оптимальным префиксным кодом для заданного распределения вероятностей. Это означает, что никакой другой префиксный код не может иметь меньшую среднюю длину кодового слова. Доказательство оптимальности основано на том, что в любом оптимальном дереве два наименее вероятных символа находятся на наибольшей глубине и являются братьями.

Избыточность

Избыточность кода Хаффмана определяется как разность между средней длиной кодового слова и энтропией источника. Для источников с неравномерным распределением вероятностей избыточность может быть значительной, но в рамках префиксных кодов она минимальна.

Адаптивность

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

Применение

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

Код Хаффмана широко используется в алгоритмах сжатия данных без потерь. Он является ключевым компонентом многих форматов и стандартов:

• ZIP и GZIP: Используют комбинацию алгоритма LZ77 и кода Хаффмана.
• JPEG: Применяет код Хаффмана для сжатия коэффициентов дискретного косинусного преобразования.
• MP3: Использует код Хаффмана для кодирования частотных компонентов.
• PNG: Применяет код Хаффмана после фильтрации и сжатия методом Deflate.
• Bzip2: Использует преобразование Барроуза — Уилера, затем кодирование длин серий и код Хаффмана.

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

Код Хаффмана сам по себе не является криптографическим методом, но может использоваться как этап в некоторых схемах сжатия перед шифрованием.

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

В системах передачи данных код Хаффмана применяется для сокращения объёма передаваемой информации, например, в протоколах сжатия заголовков.

Разновидности

n-арный код Хаффмана

Обобщение алгоритма на случай кодирования не двоичными, а n-ичными символами. В этом случае на каждом шаге объединяются n наименее вероятных узлов. Для обеспечения полноты дерева может потребоваться добавление фиктивных символов с нулевой вероятностью.

Адаптивный код Хаффмана

В отличие от статического, не требует предварительного подсчёта частот. Дерево строится и обновляется динамически по мере обработки данных. Алгоритм FGK (1978) и алгоритм Витерби (1987) являются примерами адаптивных реализаций.

Код Хаффмана с ограничением длины

В некоторых приложениях требуется ограничить максимальную длину кодового слова. Для этого используются модификации алгоритма, такие как алгоритм Пакета (package-merge algorithm), который позволяет построить оптимальный префиксный код с заданным ограничением на длину.

Критика и ограничения

• Необходимость знания распределения: Статический код Хаффмана требует предварительного подсчёта частот символов, что может быть неудобно для потоковых данных.
• Избыточность для малых алфавитов: Для алфавитов с небольшим числом символов код Хаффмана может быть неэффективен.
• Чувствительность к ошибкам: Ошибка в одном бите закодированной последовательности может привести к неправильному декодированию всей последующей информации.
• Неоптимальность для неравномерных распределений: Хотя код Хаффмана оптимален среди префиксных кодов, существуют более эффективные методы сжатия, такие как арифметическое кодирование, которые могут достигать средней длины, близкой к энтропии.

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

• Дэвид Хаффман разработал свой алгоритм в качестве курсовой работы, не подозревая, что он станет одним из самых известных методов сжатия данных.
• Алгоритм Хаффмана используется в формате факсов (Group 3 и Group 4) для сжатия чёрно-белых изображений.
• В 1991 году Хаффман получил премию IEEE Richard W. Hamming Medal за вклад в теорию информации.

Источники

• Huffman, D. A. (1952). «A Method for the Construction of Minimum-Redundancy Codes». Proceedings of the IRE, 40(9), 1098–1101.
• Cover, T. M., & Thomas, J. A. (2006). «Elements of Information Theory» (2nd ed.). Wiley-Interscience.
• Salomon, D. (2007). «Data Compression: The Complete Reference» (4th ed.). Springer.
• Ветров, А. Н. (2010). «Теория информации и кодирование». М.: Физматлит.