Huffman coding

Huffman coding – классическая lossless-техника сжатия, присваивающая частым символам короткие двоичные коды, а редким – более длинные. Изобретена Дэвидом Хаффманом в качестве домашнего задания в 1952 году и с тех пор была рабочей лошадкой entropy-кодирования во всём – от JPEG и MP3 до раннего MPEG-видео и ZIP-файлов. Математика элегантная: построить бинарное дерево, где частые символы сидят близко к корню (короткие коды), а редкие – глубоко (длинные), и вы доказательно достигаете сжатия близко к энтропийному полу для любого источника с заранее известными частотами символов.

Классический пример: если символ «A» встречается 70 % времени, а три других символа делят оставшиеся 30 %, фиксированное 2-битное кодирование тратит место зря. Huffman может закодировать «A» просто как «0», а другие как «10», «110», «111». Теперь частые случаи используют 1 бит вместо 2, а редкие платят 3 битами. Средняя длина выходит ниже 2 бит на символ – заметная экономия на длинных сообщениях.

Для продуктовой команды чистый Huffman в современном видео – в основном история. JPEG и MPEG-1/2 использовали его напрямую; H.264 использует коды в стиле Huffman внутри более простого entropy-кодера `cavlc`, но более совершенный режим CABAC использует arithmetic coding. Почему сдвиг: Huffman ограничен присвоением целого числа бит каждому символу, тогда как arithmetic coding может использовать дробное число бит и подбираться ближе к энтропийному полу. Выигрыш на символ маленький, но в сумме даёт несколько процентов от bitrate. Huffman выживает в основном как базовое понятие и внутри legacy-форматов.