Алгоритм Шеннона

В области сжатия данных, код Шеннона, названный в честь его создателя, Клода Шеннона, — это алгоритм сжатия данных без потерь с помощью построения префиксных кодов на основе набора символов и их вероятностей (расчётное или измеренное). Он является субоптимальным в том смысле, что не позволяет достичь минимально возможных кодовых длин как в кодировании Хаффмана, и никогда не будет лучше, но иногда равным с кодом Шеннона-Фано.

Этот метод был первым в своём роде, эта методика была использована для доказательства теоремы Шеннона о помехоустойчивом кодировании в 1948 в его статье «Математическая Теория связи».

В кодировании Шеннона символы располагаются в порядке от наиболее вероятных к наименее вероятным. Им присваиваются коды, путём взятия первых $l_{i}=\left\lceil {-\log }p_{i}\right\rceil$ цифр из двоичного разложения кумулятивной вероятности $\sum \limits _{k=1}^{i-1}p_{k}$ . Здесь $\left\lceil x\right\rceil$ обозначает функцию потолок, которая округляет $x$ до ближайшего целого значения, большего либо равного $x$.

Пример

В данной таблице представлен пример кодирования методом Шеннона. Можно сразу заметить по итоговым кодам, что он является менее оптимальным, чем метод Фано-Шеннона.

Первым шагом будет подсчёт вероятностей каждого символа. Затем считается число $l$ для каждой вероятности. Например, для a₂ оно равно трём ($2^{-3}\leq 0,18\leq 2^{-2}$ — минимальная степень двойки −3, следовательно $l$ равно трём). После этого считается сумма вероятностей от 0 до i-1 и переводится в двоичную форму. Потом дробная часть усекается слева на $l_{i}$ число знаков.

ai	p(ai)	li	Сумма pi до i-1	Сумма по p(ai) bin	Итоговый код
a1	0.36	2	0.0	0.0000	00
a2	0.18	3	0.36	0.0101	010
a3	0.18	3	0.54	0.1000	100
a4	0.12	4	0.72	0.1011	1011
a5	0.09	4	0.84	0.1101	1101
a6	0.07	4	0.93	0.1110	1110