Код Шеннона

2019-10-24T18:44:24Z

178.69.55.235: Исправление опечатки в p(d)

'''''Код Шеннона''''' — алгоритм [[Кодирование информации#Префиксный код | префиксного кодирования]] алфавита, предложенный Клодом Шенноном, в котором используется избыточность сообщения, заключённая в неоднородном распределении частот символов первичного алфавита, то есть заменяет коды более частых символов короткими последовательностями, а коды более редких символов — более длинными последовательностями.
{{Определение
|definition=
Пусть <tex>A=\{a_{1},a_{2},\dots,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов, которому соответствует набор вероятностей <tex>P=\{p_{1},p_{2},\dots,p_{n}\}</tex> такой, что <tex>p_{x} \geqslant p_{y}</tex>, <tex>x < y</tex>.
<tex>b_{x}=\sum\limits_{i \in [1, x - 1]}p_{i}</tex>. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},\dots,c_{n}\}</tex>, такой, что:

1. <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>

2. <tex>c_{i}</tex> представляет собой <tex>\lceil -\log p_{i}\rceil</tex> коэффициентов двоичного разложения числа <tex>{b_{i}}</tex>

называется '''кодом Шеннона'''.
}}

== Алгоритм построения бинарного кода Шеннона ==

Пусть нам даны наборы <tex>A</tex> и <tex>P</tex>, тогда для нахождения кодовых слов необходимо:
# Отсортировать элементы алфавита по не возрастанию вероятности встречи символа.
# Элементу <tex>a_{x}</tex> поставить в соответствие число <tex>b_{x}=\sum\limits_{i \in [1, x - 1]}p_{i}</tex>, при этом <tex>b_{1}=0</tex>.
# Представить каждое число <tex>{b_{x}}</tex> в виде двоичной дроби.
# В качестве кодового слова для <tex>a_{x}</tex> использовать первые <tex>L_{x}=\lceil -\log p_{x}\rceil</tex> коэффициентов представления <tex>{b_{x}}</tex>. (<tex>\lceil z \rceil</tex> — наименьшее целое число, не меньшее <tex> z </tex>)

=== Пример ===

Для примера возьмём алфавит <tex>A=\{a,b,c,d,e,f\}</tex> и набор <tex>P</tex>:

{| class="wikitable"
! Символ || a || b || c || d || e || f
|-
| <tex>p_{x}</tex> || 0.10 || 0.20 || 0.10 || 0.10 || 0.35 || 0.15
|}

По алгоритму сортируем элементы алфавита по не возрастанию <tex>p_{x}</tex>:

{| class="wikitable"
! Символ || e || b || f || a || c || d
|-
| <tex>p_{x}</tex> || 0.35 || 0.20 || 0.15 || 0.10 || 0.10 || 0.10
|}

Каждому символу <tex>a_{x}</tex> сопоставляем <tex>b_{x}</tex>:

{| class="wikitable"
! Символ || e || b || f || a || c || d
|-
| <tex>b_{x}</tex> || 0.00 || 0.35 || 0.55 || 0.70 || 0.80 || 0.90
|}

Переведём <tex>b_{x}</tex> в двоичную систему счисления:

{| class="wikitable"
! Символ || e || b || f || a || c || d
|-
| <tex>b_{x}</tex> || 0.00000 || 0.01010 || 0.10001 || 0.10110 || 0.11001 || 0.11100
|}

Посчитаем <tex>L_{x}</tex> и запишем коды:

{| class="wikitable"
! Символ || e || b || f || a || c || d
|-
| <tex>L_{x}</tex> || 2 || 3 || 3 || 4 || 4 || 4
|-
| Код || 00 || 010 || 100 || 1011 || 1100 || 1110
|}

{{Утверждение
|statement=
Код Шеннона является префиксным
|proof=
Для доказательства выбираем два произвольных кодовых слова с номерами <tex>i</tex> и <tex>j</tex>, <tex>i</tex><tex><</tex><tex>j</tex>. Кодовое слово <tex>c_{i}</tex> заведомо короче, чем <tex>c_{j}</tex>, поэтому достаточно доказать, что эти слова отличаются в одном из первых <tex>L_{i}</tex> символов. Рассмотрим разность:
<tex>b_{j} - b_{i}</tex> = <tex>\sum\limits_{k \in [1, j - 1]}p_{k} - \sum\limits_{k \in [1, i - 1]}p_{k} = \sum\limits_{k \in [i, j - 1]}p_{k} \geqslant p_{i}</tex>.

Длина слова и его вероятность связаны соотношением
<tex>L_{i} = \lceil -\log p_{i}\rceil \geqslant -\log p_{i}</tex>.
Поэтому <tex>p_{i} \geqslant 2^{-L_{i}}</tex>. С учётом этого неравенства получаем, что <tex>b_{j} - b_{i} \geqslant 2^{-L_{i}}</tex>.
В двоичной записи числа в правой части мы имеем после запятой <tex>L_{i} - 1</tex> нулей и единицу в позиции с номером <tex>L_{i}</tex>. Поэтому по меньшей мере в одном из <tex>L_{i}</tex> разрядов слова <tex>c_{i}</tex> и <tex>c_{j}</tex> отличаются и, следовательно, <tex>c_{i}</tex> не является префиксов для <tex>c_{j}</tex>. Это верно для любой пары слов, так как <tex>i</tex> и <tex>j</tex> были выбраны произвольно. Значит, код является префиксным.
}}

=== Примечание ===

[[Файл:789893856ir842.png|280px|thumb|right|Кодовое дерево для метода Шеннона]]
Код Шеннона является достаточно старым методом сжатия, который не представляет практического применения на сегодняшний день. Это связано с тем, что в общем случае длина последовательности, полученная кодированием Шеннона, равна длине последовательности, полученной
[[Алгоритм Хаффмана | алгоритмом Хаффмана]]. Но можно привести примеры, на которых метод Шеннона формирует неоптимальные коды. Например, если <tex>A=\{a,b,c,d\}</tex> и набор <tex>P</tex>:

{| class="wikitable"
! Символ || a || b || c || d
|-
| <tex>p_{x}</tex> || 0.65 || 0.15 || 0.15 || 0.05
|-
| <tex>b_{x}</tex> || 0 || 0.65 || 0.80 || 0.95
|-
| <tex>L_{x}</tex> || 1 || 3 || 3 || 5
|-
| Код || 0 || 101 || 110 || 1111
|}

Изобразим полученный результат в виде кодового дерева. Из этого рисунка видно, что полученные кодовые слова для букв <tex>d</tex> и <tex>b</tex> не являются оптимальными, так как их можно сократить на один бит без потери свойства однозначной декодируемости. Поэтому более эффективным считается сжатие метод Хаффмана.

== См.также ==
* [[Алгоритм LZW]]
* [[Арифметическое кодирование]]

== Источники информации ==
* Ю. М. Штарьков, “Обобщенные коды Шеннона”, Пробл. передачи информ., 20:3 (1984), 3—16 — с. 4.
* Б. Д. Кудряшов Теория информации. С.—Пб.: Питер, 2009 — с. 36.

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Алгоритмы сжатия ]]

Викиконспекты - Вклад участника [ru]

Код Шеннона