Изменения

'''''Код Шеннона''''' — алгоритм [[Кодирование информации#Префиксный код | префиксного кодирования ]] алфавита, предложенный Клодом Шенноном, в котором используется избыточность сообщения, заключённая в неоднородном распределении частот символов первичного алфавита, то есть заменяет коды более частых символов короткими последовательностями, а коды более редких символов — более длинными последовательностями. '''Вход:''' <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. '''Выход:''' <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex> — набор кодовых слов, соответствующий входным данным. == Определение == 

Пусть <tex>A=\{a_{1},a_{2},...\dots,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов, которому соответствует набор вероятностей <tex>WP=\{w_p_{1},w_p_{2},...\dots,w_p_{n}\}</tex> — соответствующий ему набор положительных целых весовтакой, что <tex>s=\sum\limits_p_{i x} \in [1, n]}w_geqslant p_{iy}</tex>, <tex>x < y</tex>. <tex>b_{x}=\sum\limits_{i \in [1, x - 1]}w_p_{i}</tex>. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...\dots,c_{n}\}</tex>, такой, что:

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

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

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

! Символ || a || b || c || d || e|| f

| Вес <tex>p_{x}</tex> || 5 0.10 || 2 0.20 || 6 0.10 || 1 0.10 || 20.35 || 0.15

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

! Символ || c e || b || a f || b a || e c || d

| Вес <tex>p_{x}</tex> || 6 0.35 || 5 0.20 || 2 0.15 || 2 0.10 || 10.10 || 0.10

! Символ || c e || b || a f || b a || e c || d

| Вес || 6 || 5 || 2 || 2 || 1|-| <tex>b_{x}</tex> || 0.0 || 6 0.35 || 11 0.55 || 13 0.70 || 150.80 || 0.90

Посчитаем Переведём <tex dpi = "160">\frac{b_{x}}{s}</tex> и переведём в двоичную систему счисления:

! Символ || c e || b || a f || b a || e c || d

| <tex dpi = "150">\frac{b_{x}}{s}</tex> || <tex>\frac{0}{16}</tex> .00000 || 0.01010 || <tex>\frac{6}{16}</tex> 0.10001 || <tex>\frac{11}{16}</tex> 0.10110 || <tex>\frac{13}{16}</tex> 0.11001 || <tex>\frac{15}{16}</tex>0.11100

! Символ || e || b || f || a || c || a d|-| <tex>L_{x}</tex> || 2 || 3 || 3 || b 4 || e 4 || d4

| <tex dpi = "150">\frac{b_{x}}{s}</tex> Код || 0.0000 00 || 0.0110 010 || 100 || 0.1011 || 0.1101 1100 || 0.11111110

Посчитаем {{Утверждение|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_{xi} - 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>:

! Символ || a || b || c || a d|-| <tex>p_{x}</tex> || 0.65 || 0.15 || 0.15 || 0.05|-| <tex>b_{x}</tex> || 0 || b 0.65 || e 0.80 || d0.95

| <tex>L_{x}</tex> || 2 || 2 1 || 3 || 3 || 45

| Код || 00 || 01 0 || 101 || 110 || 1111

Для декодирования необходимо последовательно вычислять первые <tex>L_{x}</tex> цифр двоичной дроби <tex dpi = "160">\frac{b_{x}}{s}</tex> и сравнивать их с первыми <tex>L_{x}</tex> символами последовательности кодовых слов. Их совпадение определяет символ <tex>x</tex>= См.также ==* [[Алгоритм LZW]]* [[Арифметическое кодирование]]

== Литература Источники информации ==