Меню
Главная
Случайная статья
Настройки
|
В области сжатия данных, код Шеннона, названный в честь его создателя, Клода Шеннона, — это алгоритм сжатия данных без потерь с помощью построения префиксных кодов на основе набора символов и их вероятностей (расчётное или измеренное). Он является субоптимальным в том смысле, что не позволяет достичь минимально возможных кодовых длин как в кодировании Хаффмана, и никогда не будет лучше, но иногда равным с кодом Шеннона-Фано.
Этот метод был первым в своём роде, эта методика была использована для доказательства теоремы Шеннона о помехоустойчивом кодировании в 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
|
Ссылки
- «A Mathematical Theory of Communication» http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf Архивная копия от 15 июля 1998 на Wayback Machine
|
|