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

---

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

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

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

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

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

---