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

07.03.2021

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

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

В кодировании Шеннона символы располагаются в порядке от наиболее вероятных к наименее вероятным. Им присваиваются коды, путём взятия первых l i = ⌈ − log p i ⌉ {displaystyle l_{i}=leftlceil {-log }p_{i} ight ceil } цифр из двоичного разложения кумулятивной вероятности ∑ k = 1 i − 1 p k {displaystyle sum limits _{k=1}^{i-1}p_{k}} . Здесь ⌈ x ⌉ {displaystyle leftlceil x ight ceil } обозначает функцию потолок, которая округляет x {displaystyle x} до ближайшего целого значения, большего либо равного x {displaystyle x} .

Пример

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

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