Русская Википедия:Алгоритм Шеннона

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

В кодировании Шеннона символы располагаются в порядке от наиболее вероятных к наименее вероятным. Им присваиваются коды, путём взятия первых <math>l_i = \left\lceil -\log_2 p_i \right\rceil </math> цифр из двоичного разложения кумулятивной вероятности <math> \sum\limits_{k=1}^{i-1} p_k</math> . Здесь <math>\left\lceil x \right\rceil</math> обозначает функцию потолок, которая округляет <math>x</math> до ближайшего целого значения, большего либо равного <math>x</math>.

Пример

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

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

ai	p(ai)	li	Сумма 0 до 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