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

Алфавит {a,b,c,d}, вероятности p$a$=0.5, p$b$=0.25, p$c$=0.125, p$d$=0.125.

Энтропия $вбитахнасимвол$ H = −∑ p$x$ log2 p$x$ = −0.5·log2 0.5 −0.25·log2 0.25 −0.125·log2 0.125 −0.125·log2 0.125
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 бит/символ.

2) Оптимальный префиксный код $Хаффман$

Построение $коротко$: два наименьших веса 0.125 и 0.125 объединяются в узел 0.25; далее веса 0.25 $отc+d$ и 0.25 $букваb$ объединяются в 0.5; далее 0.5 $b+c+d$ и 0.5 $букваa$ дают корень.

Один из возможных кодов $равнооптимален$:

a : 0 $длина1$b : 10 $длина2$c : 110 $длина3$d : 111 $длина3$

Средняя длина кода
L = ∑ p$x$ · l$x$ = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 бит/символ.

Разница: L − H = 0. Так как вероятности являются степенями 1/2 $диадические$, Хаффман-код достигает энтропии точно — нулевая избыточность.

3) Когда арифметическое кодирование $АК$ даёт значимое преимущество

Коротко:

АК наиболее полезно, когда оптимальные средние длины символов не целочисленны $недиадические$. Тогда АК дает дробное число бит на символ и может приблизить энтропию гораздо точнее, чем Хаффман, у которого длины — целые биты.При статическом распределении: если распределение не диадическое, для длинных сообщений АК обычно даёт лучшее среднее число бит/символ $приближаетсякH$, тогда как простой Хаффман даёт L ≥ H + $\mathrm{0..1}$ бит/символ $частоненулевуюизбыточность$. Для коротких сообщений накладные расходы АК $инициализация,кодированиеграниц$ могут нивелировать преимущество.АК особенно выигрывает при моделях с высокой степенью точности $контекстныемодели,PPM,смешанные/адаптивныемодели$: он позволяет выдавать дробное количество бит для каждого символа и поддерживает адаптацию без экспоненциального роста алфавита.Если вероятность легко представима степенью 1/2 $какввашемпримере$, АК существенного выигрыша не даёт.

Практические замечания:

АК $иегореализация—rangecoding$ более гибок и обычно даёт лучшее сжатие при сложном моделировании источника.АК требует аккуратной реализации $предотвращениепереполнения,точность$, но на практике эти проблемы решаются $rangecoding$.Для очень коротких сообщений и простых задач Хаффман проще и быстрее и может быть предпочтителен.

4) Влияние корреляций между символами на выбор схем сжатия

Энтропия и энтропийная скорость: при наличии корреляций $источникспамятью,напримерМарковский$ важна энтропийная скорость H̄ = lim $1/n$ H$X\mathrm{1..}Xn$. Она обычно меньше энтропии односимвольного распределения H$X$, и это значит, что существует дополнительный потенциал сжатия, если использовать корреляции.Хаффман на одной букве $кодированиенезависимыхсимволовпомаргиналям$ не использует корреляции — он оптимален только для независимых символов. Чтобы использовать память источника в рамках префиксных кодов, нужно кодировать блоки символов $совмещатьнесколькосимволоввсупер-символистроитьХаффманнаихсовместномраспределении$. Но совместный алфавит растёт экспоненциально $|A{|}^k$ и становится непрактичным при больших порядках памяти.Арифметическое кодирование + модель предсказания $contextmodel,n-gram,PPM,переменныепорядки$ — стандартный путь для использования корреляций: модель оценивает условные вероятности p$x_t|контекст$, а АК кодирует последовательность, выдавая близко к сумме −log p$x_t|контекст$ бит на символ. Такой подход эффективно достигает условной энтропии H$X_t|прошлое$.Другие методы: LZ77/LZ78/LZW и их производные $gzip,LZMA$ неявно используют повторяющиеся последовательности $корреляциииповторяемость$ без явного моделирования условных вероятностей; они часто конкурентоспособны и хорошо масштабируются.Практический выбор:
Если корреляции короткоплечные и модель небольшая — можно прибегнуть к АК с контекстной моделью или к блочному Хаффману $малыйблок$.Для длинных зависимостей или повторов лучше LZ-подходы или статистические методы с АК.Если требуется простота и быстрота, и корреляции слабы — Хаффман на маргиналях может быть достаточен.

Короткий пример иллюстрации:

Пусть p$a$=0.5 и часто после a идёт снова a $сильнаяавтокорреляция$. Тогда условная энтропия H$X<em>t|X</em>t-1$ может быть значительно меньше H$X_t$, и код, использующий предсказатель + АК, даст меньше бит/символ, чем символоориентированный Хаффман.

5) Выводы / рекомендации

Для данного распределения {0.5,0.25,0.125,0.125} Хаффман даёт среднюю длину 1.75 бит/символ, равную энтропии — арифметическое кодирование здесь не даёт преимущества.Арифметическое/range-кодирование даёт значимое преимущество, когда распределения не диадические, когда требуется кодирование дробного числа бит на символ, при использовании гибких/адаптивных контекстных моделей и при длинных последовательностях.При наличии корреляций между символами эффективный путь — комбинация хорошей статистической модели $контексты,предикторы$ и арифметического/range-кодера либо использование LZ-подходов; простое односимвольное Хаффман-кодирование в этом случае часто будет субоптимальным.

Если хотите, могу:

показать графическое дерево Хаффмана $вASCII$,построить Хаффман и арифметический код для другого набора вероятностей,или продемонстрировать численный пример выигрыша АК при не-диадическом распределении.