> huffman | оптимальные | коды <

// Кодирование Хаффмана — оптимальный алгоритм префиксно‑свободного сжатия

ВХОД 0 символов

Показать дерево

Показать таблицу кодов

Форматировать двоичный вид

ВЫХОД 0 символов

>> возможности

[OPTIMAL]

Оптимальные коды

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

[PREFIX-FREE]

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

Ни один код не является префиксом другого, что гарантирует однозначную декодировку.

[ADAPTIVE]

Частотный подход

Более частые символы автоматически получают более короткие коды.

>> техническая информация

Как работает кодирование Хаффмана

Кодирование Хаффмана строит двоичное дерево снизу вверх. Начиная с частот символов, алгоритм многократно объединяет два узла с наименьшей частотой в родительский узел, пока не останется только корень. Левые ветви обозначают '0', правые — '1'. Более частые символы располагаются ближе к корню и получают более короткие коды, обеспечивая оптимальное сжатие для заданного распределения частот.

Пример кодирования Хаффмана

Text: "AABBBCCCC"

Frequencies:
A: 2
B: 3
C: 4

Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)

Tree:
     Root(9)
    /      \
   C(4)    AB(5)
          /     \
        A(2)    B(3)

Codes:
C: 0
A: 10
B: 11

Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000

Зачем использовать кодирование Хаффмана?

Коэффициент сжатия, близкий к теоретическому пределу энтропии
Простая реализация
Основа сжатия ZIP/JPEG
Отсутствие потерь данных
Доказанная эффективность на практике

>> часто задаваемые вопросы

Что такое кодирование Хаффмана?

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

Почему его называют префиксно‑свободным?

Система кодов является префиксно‑свободной, если ни одно кодовое слово не является префиксом другого. Например, если символ 'A' кодируется как '01', ни один другой символ не может иметь код, начинающийся с '01'. Это обеспечивает однозначную декодировку потока бит без разделителей.

Насколько эффективно кодирование Хаффмана?

Для заданного распределения частот кодирование Хаффмана достигает оптимального сжатия и обычно даёт результат в пределах 1 бита от теоретического предела энтропии. Для английских текстов часто достигается сжатие 60–70 %, особенно когда частоты символов сильно различаются.

Где используется кодирование Хаффмана?

Кодирование Хаффмана применяется в JPEG‑сжатии изображений, ZIP‑архивах (в комбинации с LZ77 в DEFLATE), аудио MP3 и многих других форматах. Часто его используют совместно с другими алгоритмами: например, в JPEG Huffman применяется после DCT и квантования, а в ZIP — после LZ77.