7
правок
Изменения
Нет описания правки
{{Определение
|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>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>
! Символ || a || b || c || d || e || f
|-
| <tex>p_{x}</tex> || 0,.10 || 0,.20 || 0,.10 || 0,.10 || 0,.35 || 0,.15
|}
! Символ || e || b || f || a || c || d
|-
| <tex>p_{x}</tex> || 0,.35 || 0,.20 || 0,.15 || 0,.10 || 0,.10 || 0,.10
|}
! Символ || e || b || f || a || c || d
|-
| <tex>b_{x}</tex> || 0,.00 || 0,.35 || 0,.55 || 0,.70 || 0,.80 || 0,.90
|}
! Символ || e || b || f || a || c || d
|-
| <tex>b_{x}</tex> || 0,.00000 || 0,.01010 || 0,.10001 || 0,.10110 || 0,.11001 || 0,.11100
|}
В двоичной записи числа в правой части мы имеем после запятой <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.5
|-
| <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]]
* [[Арифметическое кодирование]]
