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

Энтропия и взаимная информация $дискретныйслучай$

Энтропия случайной величины X с конечным множеством значений X = {x1,...,xn} и вероятностями p$xi$ = P$X=xi$ определяется как
H$X$ = − sum_{i=1}^n p$xi$ log2 p$xi$.
Интерпретация: минимальное среднее число бит на символ при кодировании независимых одинаково распределённых $i.i.d.$ символов при бесконечном блокировании $асимптотически$.

Свойства:

H$X$ ≥ 0; максимум достигается при равномерном распределении $H=log2n$.Аддитивность для независимых: H$X,Y$ = H$X$ + H$Y$ если X ⟂ Y.Неравенство Шеннона для моментальной $префиксной$ кодировки: для любого префиксного кода со средними длинами l_i = длина кода для xi,
H$X$ ≤ E$$L$$ = sum p$xi$ l_i < H$X$ + 1.

Взаимная информация двух дискретных величин X и Y:
I$X;Y$ = sum_{x,y} p$x,y$ log2 $p(x,y)/(p(x)p(y))$.
Интерпретация: уменьшение неопределённости $энтропии$ о X при известном Y: I$X;Y$ = H$X$ − H$X|Y$ = H$Y$ − H$Y|X$.
Свойства: I$X;Y$ ≥ 0, симметрична.

Пример: код Хаффмана для заданного распределения

Пусть алфавит {a,b,c,d} с вероятностями
p$a$=0.4, p$b$=0.3, p$c$=0.2, p$d$=0.1.

Шаги Хаффмана:

Возьмём две наименьшие вероятности: 0.1 $d$ и 0.2 $c$ → объединим в узел cd с вероятностью 0.3.Имеем 0.4 $a$, 0.3 $b$, 0.3 $cd$. Выберем две наименьшие $0.3и0.3$ → объединим в узел B с вероятностью 0.6.Оставшиеся 0.4 $a$ и 0.6 $B$ объединяем в корень.

Назначим биты: a = 0 $длина1$; B = 1 $длина1$ Развернём B: b = 10 $длина2$; cd = 11 $длина2$ Развернём cd: c = 110 $длина3$; d = 111 $длина3$

Итоговые коды:
a: 0 $l_a=1$ b: 10 $l_b=2$ c: 110 $l_c=3$ d: 111 $l_d=3$

Средняя длина:
E$$L$$ = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 1.9 бита/символ.

Энтропия источника:
H$X$ = −$0.4log20.4+0.3log20.3+0.2log20.2+0.1log20.1$ ≈ 1.8464 бит.
Проверка неравенства: H ≈1.8464 ≤ E$$L$$=1.9 < H+1 ≈2.8464 — выполняется.

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

Теорема: код, получаемый алгоритмом Хаффмана, минимизирует среднюю длину E$$L$$ среди всех префиксных $моментальных$ кодов для заданных вероятностей {p_i}.

Доказательство $классическое,поиндукции,саргументомобмена$:

База: для n=2 — единственный префиксный код даёт минимальную длину.Индуктивный шаг: пусть для всех алфавитов с < n символами утверждение верно. Рассмотрим оптимальный префиксный код для n символов {1,...,n} с вероятностями упорядоченными p1 ≥ p2 ≥ ... ≥ pn. В оптимальном префиксном дереве два наимее вероятных символа $pn-1иpn$ можно считать соседями $братьями$: если это не так, можно показать операцией обмена символов в дереве, что существует оптимальный код, где два минимальных вероятностных символа являются листьями с одинаковой глубиной и общим родителем $аргументобменанеухудшаетсреднююдлину$. Тогда можно "сжать" эти два символа в один условный символ с вероятностью pn-1 + pn и рассмотреть задачу для n−1 символов; по индукции оптимальное дерево для уменьшённой задачи получается алгоритмом Хаффмана, а разворачивание узла даёт оптимальное дерево для исходной задачи. Таким образом жадный шаг $объединятьдванаименьших$ является корректным и даёт оптимальный результат.Следствие: Хаффман минимизирует E$$L$$ среди всех префиксных и, следовательно, среди всех однозначно декодируемых кодов $Kraft–McMillan:набордлинl_iдопустимтогдаитолькотогда,когдаsum{2}^{-l_i}\le 1;длялюбыхтакихдлинсуществуетпрефиксныйкодсэтимидлинами$.

Это стандартный и жёстко формализуемый аргумент «greedy + optimal substructure».

Ограничения и нюансы при непрерывных источниках и при требованиях по задержке

Непрерывные источники:

Для непрерывной случайной величины X с плотностью f$x$ определяют дифференциальную энтропию
h$X$ = − ∫ f$x$ log2 f$x$ dx.
Но h$X$ — не прямая замена дискретной энтропии: она не инвариантна относительно непрерывных одномерных преобразований $смещение/шкала$ и может быть отрицательной; дифференциальная энтропия не даёт напрямую нижней границы на число бит для кодирования одной конкретной реализации — для практического кодирования непрерывных сигналов требуется квантование $дискретизацияамплитуды$.Кодирование непрерывного источника обычно осуществляется в два этапа: $i$ квантование $преобразованиевдискретныйалфавит$ либо разрешение ошибки $допускаемоеспогрешностью$; $ii$ сжатие $энтропийноекодирование$ квантованных уровней. При этом будет иметь место потеря информации $дискретизация$ и оптимальный компромисс определяется теорией rate–distortion: минимальная скорость R$D$ для допустимого среднего искажения D.Арифметическое кодирование и кодирование по контексту работают на потоках бит для квантованных значений и позволяют приближать энтропию очень близко, но всё равно требуется дискретизация входа.

Проблемы при бесконечном $неограниченном$ алфавите:

Если алфавит счётный, но бесконечный, алгоритм Хаффмана формально неприменим $нужноконечноедерево$. Для таких случаев используют схемы с отсечением хвоста $приближённо$ или другие подходы $например,универсальныекодыдляцелыхчисел:Elias\gamma ,\delta ит.п.$.

Задержка $латентность$ и компромисс с эффективностью сжатия:

Хаффман в своей базовой форме — посимвольный $возможноблоковый$ префиксный код. Для повышения эффективности часто кодируют блоки длины n $коддляn-символьныхслов$: средняя длина на символ приближается к H$X$ при n→∞ $засчётAEP—асимптотическогоравномерногораспределениятипичныхпоследовательностей$. Однако блокирование увеличивает задержку $нужнонакопитьnсимволовпередкодированием$.Для минимальной задержки используют посимвольные или малые блоки, но это увеличивает избыточность $E[L]-H$.Переменная длина кода снижает среднюю длину, но приводит к непредсказуемому времени декодирования отдельных символов $переменнаязадержка$, требует синхронизации и устойчивости к ошибкам $однобитовоеискажениеможетнарушитьпоследующуюдекодировку$.Арифметическое кодирование даёт очень малую избыточность даже для коротких блоков и работает последовательно $приближённопотоковаясхема$, но требует высокоточной арифметики/контроля перекрытий и может вносить дополнительную задержку из‑за необходимости аккумулировать диапазон вероятностей и выполнять окончательное выравнивание/вывод битов; также более чувствительно к ошибкам в битстриме.Существуют схемы с управляемой задержкой:Fixed-to-variable $Huffman$ — малую задержку, но ограниченная эффективность.Variable-to-fixed $например,Tunstall$ — кодирует переменное число входных символов в фиксированное число выходных битов, что даёт падение вариации задержки, но требует больших словарей.Arithmetic / range coding — отличная эффективность, потоковый режим, но требует буферизации/точности.Практический компромисс зависит от требований: допустимая средняя скорость, максимум задержки, чувствительность к ошибкам, сложность реализации.

Конечные блоки и конечнопроблемность $finite-blocklength$:

Асимптотические результаты $E[L{]}_n\to H$ хороши, но для конечного n существует неизбежная избыточность. Эту избыточность можно оценивать асимптотически: при кодировании блоков длины n из i.i.d. источника разброс суммарной лог‑вероятности имеет порядок sqrt$n$ $центральнаяпредельнаятеорема$, и редундансность/ошибка порядка O$1/n$ или O$(logn)/n$ в среднем; точные выражения зависят от дополнительной информации $варианс«самоинформации»ит.п.$. Следовательно, чтобы получить отступ от энтропии на ε нужно брать блоки достаточно большой длины n, что увеличивает задержку.Краткие практические рекомендацииДля дискретных конечных алфавитов и известных вероятностей: используйте Хаффман $еслинужныпрефиксныекодыипростота$ или арифметическое кодирование $еслихотитеприближатьсякэнтропииболееплотноприразумнойзадержке$.Для непрерывных источников: сначала подходящая дискретизация/квантование или применение методов преобразования $например,преобразованиеКарунена–Лоэве,векторноеквантование$, затем энтропийное кодирование квантованных уровней; оптимальный компромисс задаётся rate–distortion.При жёстких ограничениях по задержке: выбирайте схемы с минимальным блокированием $возможноTunstallилималыеблоки+арифметическоекодирование$, оценивайте допустимую избыточность и устойчивость к ошибкам.

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

Развернуто доказать оптимальность Хаффмана пошагово с формулами;Показать пример с другим распределением и/или кодированием блоков $Huffmanнаблоках$;Рассчитать пример квантования для простого непрерывного источника и показать воздействие на битрейт и искажение;Обсудить конкретные схемы для низкой задержки $Tunstall,Huffman-on-the-fly,arithmeticwithflushing$.