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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Код Шеннона»)
Перейти к навигации Перейти к поиску

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

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

В кодировании Шеннона символы располагаются в порядке от наиболее вероятных к наименее вероятным. Им присваиваются коды, путём взятия первых цифр из двоичного разложения кумулятивной вероятности . Здесь обозначает функцию потолок, которая округляет до ближайшего целого значения, большего либо равного .

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

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

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
  1. «A Mathematical Theory of Communication» http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf Архивная копия от 15 июля 1998 на Wayback Machine