В области сжатия данных, код Шеннона, названный в честь его создателя, Клода Шеннона, — это алгоритм сжатия данных без потерь с помощью построения префиксных кодов на основе набора символов и их вероятностей (расчётное или измеренное). Он является субоптимальным в том смысле, что не позволяет достичь минимально возможных кодовых длин как в кодировании Хаффмана, и никогда не будет лучше, но иногда равным с кодом Шеннона-Фано.
Этот метод был первым в своём роде, эта методика была использована для доказательства теоремы Шеннона о помехоустойчивом кодировании в 1948 в его статье «Математическая Теория связи»«A Mathematical Theory of Communication» http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf .
В кодировании Шеннона символы располагаются в порядке от наиболее вероятных к наименее вероятным. Им присваиваются коды, путём взятия первых цифр из двоичного разложения кумулятивной вероятности . Здесь обозначает функцию потолок, которая округляет до ближайшего целого значения, большего либо равного .
Пример В данной таблице представлен пример кодирования методом Шеннона. Можно сразу заметить по итоговым кодам, что он является менее оптимальным, чем метод Фано-Шеннона.
Первым шагом будет подсчёт вероятностей каждого символа. Затем считается число для каждой вероятности. Например, для a2 оно равно трём ( — минимальная степень двойки −3, следовательно равно трём). После этого считается сумма вероятностей от 0 до i-1 и переводится в двоичную форму. Потом дробная часть усекается слева до числа знаков. aip(ai)liСумма 0 до i-1Сумма по p(ai) binИтоговыйкодa10.3620.00.000000a20.1830.360.0101010a30.1830.540.1000100a40.1240.720.10111011a50.0940.840.11011101a60.0740.930.11101110
Ссылки
Категория:Теория кодирования Категория:Сжатие данных Категория:Алгоритмы сжатия без потерь