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

Кодування Шеннона, назване на честь творця, Клода Шеннона, — безвтратна техніка стиснення даних для побудови префіксного коду, яка ґрунтується на наборі символів і їх імовірностях (розрахованих або виміряних). Кодування Шеннона субоптимальне в тому сенсі, що не досягає найменшої можливої очікуваної довжини кодового слова, подібно до кодування Гаффмана, і не краще але інколи рівне кодуванню Шеннона — Фано.

Метод був першим у своєму роді, цю методику використано під час доведення Шаблон:Нп в його статті 1948 року «Математична теорія зв'язку».

Цей метод кодування породив галузь теорії інформації, і без нього світ не мав би жодного з багатьох наступників; наприклад кодування Шеннона — Фано, кодування Гаффмана або арифметичного кодування. Значна частина нашого повсякденного життя пов'язана з цифровими даними, і це було б неможливим без кодування Шеннона та постійної еволюції його методів.

У кодуванні Шеннона символи розміщуються в порядку від найбільш імовірних до найменш імовірних. Їм призначаються коди з перших $l_i=\lceil -\log p_i\rceil$ цифр двійкового розкладу кумулятивної ймовірності $\sum _{k=1}^{i-1}{p}_k$. Тут $\lceil x\rceil$ позначає функцію стеля, яка округлює $x$ до найближчого цілого значення, більшого або рівного $x$.

Приклад

У таблиці наведено приклад кодування методом Шеннона. За підсумковим кодом можна помітити, що він є менш оптимальним, ніж алгоритм Шеннона — Фано.

Перший крок — підрахунок імовірностей кожного символу. Потім рахується число $l$ для кожної ймовірності. Наприклад, для $a_2$ воно дорівнює 3 ($2^{-3}\le 0,18\le 2^{-2}$ — найменший степінь двійки —3, отже $l=3$). Після цього підраховується сума ймовірностей від 0 до i—1 і переводиться в двійкову форму. Потім дробова частина усікається зліва до $l_i$ знаків.

ai	p (ai)	li	Сума pnвід n=0 до i—1	Сума за p(ai) bin	підсумковий  код
a 1	0.36	2	0.0	0.0000	00
a 2	0.18	3	0.36	0.0100	010
a 3	0.18	3	0.54	0.1000	100
a 4	0.12	4	0.72	0.1011	1011
a 5	0.09	4	0.84	0.1101	1101
a 6	0.07	4	0.93	0.1110	1110