Меню Главная Случайная статья Настройки Алгоритм Шеннона Материал из https://ru.wikipedia.org В области сжатия данных, код Шеннона, названный в честь его создателя, Клода Шеннона, — это алгоритм сжатия данных без потерь с помощью построения префиксных кодов на основе набора символов и их вероятностей (расчётное или измеренное). Он является субоптимальным в том смысле, что не позволяет достичь минимально возможных кодовых длин как в кодировании Хаффмана, и никогда не будет лучше, но иногда равным с кодом Шеннона-Фано. Этот метод был первым в своём роде, эта методика была использована для доказательства теоремы Шеннона о помехоустойчивом кодировании в 1948 в его статье «Математическая Теория связи»[1]. В кодировании Шеннона символы располагаются в порядке от наиболее вероятных к наименее вероятным. Им присваиваются коды, путём взятия первых ${\displaystyle l_{i}=\left\lceil -\log _{2}p_{i}\right\rceil }$ цифр из двоичного разложения кумулятивной вероятности ${\displaystyle \sum \limits _{k=1}^{i-1}p_{k}}$ . Здесь ${\displaystyle \left\lceil x\right\rceil }$ обозначает функцию потолок, которая округляет ${\displaystyle x}$ до ближайшего целого значения, большего либо равного ${\displaystyle x}$. Пример В данной таблице представлен пример кодирования методом Шеннона. Можно сразу заметить по итоговым кодам, что он является менее оптимальным, чем метод Фано-Шеннона. Первым шагом будет подсчёт вероятностей каждого символа. Затем считается число ${\displaystyle l}$ для каждой вероятности. Например, для a2 оно равно трём (${\displaystyle 2^{-3}\leq 0,18\leq 2^{-2}}$ — минимальная степень двойки 3, следовательно ${\displaystyle l}$ равно трём). После этого считается сумма вероятностей от 0 до i-1 и переводится в двоичную форму. Потом дробная часть усекается слева до ${\displaystyle l_{i}}$ числа знаков. 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