Код Шеннона — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
'''''Код Шеннона''''' — алгоритм [[Кодирование информации#Префиксный код | префиксного кодирования]] алфавита, предложенный Клодом Шенноном, в котором используется избыточность сообщения, заключённая в неоднородном распределении частот символов первичного алфавита, то есть заменяет коды более частых символов короткими последовательностями, а коды более редких символов — более длинными последовательностями.
 
'''''Код Шеннона''''' — алгоритм [[Кодирование информации#Префиксный код | префиксного кодирования]] алфавита, предложенный Клодом Шенноном, в котором используется избыточность сообщения, заключённая в неоднородном распределении частот символов первичного алфавита, то есть заменяет коды более частых символов короткими последовательностями, а коды более редких символов — более длинными последовательностями.
 
'''Вход:''' <tex>A=\{a_{1},a_{2},\dots,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов с вероятностями <tex>P=\{p_{1},p_{2},\dots,p_{n}\}</tex>.
 
 
'''Выход:''' <tex>C=\{c_{1},c_{2},\dots,c_{n}\}</tex> — набор кодовых слов, соответствующий входным данным.
 
 
== Определение ==
 
 
 
{{Определение  
 
{{Определение  
 
|definition=
 
|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} \geq p_{y}</tex>, <tex>x > y</tex>.  
+
Пусть <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>, такой, что:
 
<tex>b_{x}=\sum\limits_{i \in [1, x - 1]}p_{i}</tex>.  Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},\dots,c_{n}\}</tex>, такой, что:
  
Строка 87: Строка 80:
  
 
[[Файл:789893856ir842.png|280px|thumb|right|Кодовое дерево для метода Шеннона]]
 
[[Файл:789893856ir842.png|280px|thumb|right|Кодовое дерево для метода Шеннона]]
Код Шеннона является достаточно старым методом сжатия, который не представляет практического применения на сегодняшний день. Это связано с тем, что в общем случае длина последовательности полученная кодированием Шеннона равна длине последовательности, полученной  
+
Код Шеннона является достаточно старым методом сжатия, который не представляет практического применения на сегодняшний день. Это связано с тем, что в общем случае длина последовательности, полученная кодированием Шеннона, равна длине последовательности, полученной  
 
[[Алгоритм Хаффмана | алгоритмом Хаффмана]]. Но можно привести примеры, на которых метод Шеннона формирует неоптимальные коды. Например, если <tex>A=\{a,b,c,d\}</tex> и набор <tex>P</tex>:
 
[[Алгоритм Хаффмана | алгоритмом Хаффмана]]. Но можно привести примеры, на которых метод Шеннона формирует неоптимальные коды. Например, если <tex>A=\{a,b,c,d\}</tex> и набор <tex>P</tex>:
  
Строка 93: Строка 86:
 
! Символ || a || b || c || d
 
! Символ || a || b || c || d
 
|-
 
|-
| <tex>p_{x}</tex> || 0.65 || 0.15 || 0.15 || 0.5
+
| <tex>p_{x}</tex> || 0.65 || 0.15 || 0.15 || 0.05
 
|-
 
|-
 
| <tex>b_{x}</tex> || 0 || 0.65 || 0.80 || 0.95
 
| <tex>b_{x}</tex> || 0 || 0.65 || 0.80 || 0.95

Текущая версия на 19:15, 4 сентября 2022

Код Шеннона — алгоритм префиксного кодирования алфавита, предложенный Клодом Шенноном, в котором используется избыточность сообщения, заключённая в неоднородном распределении частот символов первичного алфавита, то есть заменяет коды более частых символов короткими последовательностями, а коды более редких символов — более длинными последовательностями.

Определение:
Пусть [math]A=\{a_{1},a_{2},\dots,a_{n}\}[/math] — алфавит из [math]n[/math] различных символов, которому соответствует набор вероятностей [math]P=\{p_{1},p_{2},\dots,p_{n}\}[/math] такой, что [math]p_{x} \geqslant p_{y}[/math], [math]x \lt y[/math].

[math]b_{x}=\sum\limits_{i \in [1, x - 1]}p_{i}[/math]. Тогда набор бинарных кодов [math]C=\{c_{1},c_{2},\dots,c_{n}\}[/math], такой, что:

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

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

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


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

Пусть нам даны наборы [math]A[/math] и [math]P[/math], тогда для нахождения кодовых слов необходимо:

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

Пример

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

Символ a b c d e f
[math]p_{x}[/math] 0.10 0.20 0.10 0.10 0.35 0.15

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

Символ e b f a c d
[math]p_{x}[/math] 0.35 0.20 0.15 0.10 0.10 0.10

Каждому символу [math]a_{x}[/math] сопоставляем [math]b_{x}[/math]:

Символ e b f a c d
[math]b_{x}[/math] 0.00 0.35 0.55 0.70 0.80 0.90

Переведём [math]b_{x}[/math] в двоичную систему счисления:

Символ e b f a c d
[math]b_{x}[/math] 0.00000 0.01010 0.10001 0.10110 0.11001 0.11100

Посчитаем [math]L_{x}[/math] и запишем коды:

Символ e b f a c d
[math]L_{x}[/math] 2 3 3 4 4 4
Код 00 010 100 1011 1100 1110
Утверждение:
Код Шеннона является префиксным
[math]\triangleright[/math]

Для доказательства выбираем два произвольных кодовых слова с номерами [math]i[/math] и [math]j[/math], [math]i[/math][math]\lt [/math][math]j[/math]. Кодовое слово [math]c_{i}[/math] заведомо короче, чем [math]c_{j}[/math], поэтому достаточно доказать, что эти слова отличаются в одном из первых [math]L_{i}[/math] символов. Рассмотрим разность: [math]b_{j} - b_{i}[/math] = [math]\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}[/math].

Длина слова и его вероятность связаны соотношением [math]L_{i} = \lceil -\log p_{i}\rceil \geqslant -\log p_{i}[/math]. Поэтому [math]p_{i} \geqslant 2^{-L_{i}}[/math]. С учётом этого неравенства получаем, что [math]b_{j} - b_{i} \geqslant 2^{-L_{i}}[/math].

В двоичной записи числа в правой части мы имеем после запятой [math]L_{i} - 1[/math] нулей и единицу в позиции с номером [math]L_{i}[/math]. Поэтому по меньшей мере в одном из [math]L_{i}[/math] разрядов слова [math]c_{i}[/math] и [math]c_{j}[/math] отличаются и, следовательно, [math]c_{i}[/math] не является префиксов для [math]c_{j}[/math]. Это верно для любой пары слов, так как [math]i[/math] и [math]j[/math] были выбраны произвольно. Значит, код является префиксным.
[math]\triangleleft[/math]

Примечание

Кодовое дерево для метода Шеннона

Код Шеннона является достаточно старым методом сжатия, который не представляет практического применения на сегодняшний день. Это связано с тем, что в общем случае длина последовательности, полученная кодированием Шеннона, равна длине последовательности, полученной алгоритмом Хаффмана. Но можно привести примеры, на которых метод Шеннона формирует неоптимальные коды. Например, если [math]A=\{a,b,c,d\}[/math] и набор [math]P[/math]:

Символ a b c d
[math]p_{x}[/math] 0.65 0.15 0.15 0.05
[math]b_{x}[/math] 0 0.65 0.80 0.95
[math]L_{x}[/math] 1 3 3 5
Код 0 101 110 1111

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

См.также

Источники информации

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