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

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

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

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