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

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

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

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

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

Приклад

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

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