Алгоритм Шеннона
В области сжатия данных, код Шеннона, названный в честь его создателя, Клода Шеннон, — это алгоритм сжатия данных без потерь с помощью построения префиксных кодов на основе набора символов и их вероятностей (расчётное или измеренное). Он является субоптимальным в том смысле, что не позволяет достичь минимально возможных кодовых длин как в кодировании Хаффмана, и никогда не будет лучше, но иногда равным с кодом Шеннона-Фано.
Этот метод был первым в своём роде, эта методика была использована для доказательства теоремы Шеннона о помехоустойчивом кодировании в 1948 в его статье «Математическая Теория связи»[1].
В кодировании Шеннона символы располагаются в порядке от наиболее вероятных к наименее вероятным. Им присваиваются коды, путём взятия первых <math>l_i = \left\lceil {-\log} p_i \right\rceil </math> цифр из двоичного разложения кумулятивной вероятности <math> \sum\limits_{k=1}^{i-1} p_k</math> . Здесь <math>\left\lceil x \right\rceil</math> обозначает функцию потолок, которая округляет <math>x</math> до ближайшего целого значения, большего либо равного <math>x</math>.
Пример
В данной таблице представлен пример кодирования методом Шеннона. Можно сразу заметить по итоговым кодом, что он является менее оптимальным, чем метод Фано-Шеннона.
Первым шагом будет подсчёт вероятностей каждого символа. Затем считается число <math>l</math> для каждой вероятности. Например, для a2 оно равно трём (<math>2^{-3} \leq 0,18 \leq 2^{-2}</math> — минимальная степень двойки −3, следовательно <math>l</math> равно трём). После этого считается сумма вероятностей от 0 до i-1 и переводится в двоичную форму. Потом дробная часть усекается слева на <math>l_i</math> число знаков.
| ai | p(ai) | li | Сумма pi до i-1 | Сумма по p(ai) bin | Итоговый код |
|---|---|---|---|---|---|
| a1 | 0.36 | 2 | 0.0 | 0.0000 | 00 |
| a2 | 0.18 | 3 | 0.36 | 0.0100 | 010 |
| a3 | 0.18 | 3 | 0.54 | 0.1000 | 100 |
| a4 | 0.12 | 4 | 0.72 | 0.1011 | 1011 |
| a5 | 0.09 | 4 | 0.84 | 0.1101 | 1101 |
| a6 | 0.07 | 4 | 0.93 | 0.1110 | 1110 |
Напишите отзыв о статье "Алгоритм Шеннона"
Ссылки
- ↑ «A Mathematical Theory of Communication» cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf
|
Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Отрывок, характеризующий Алгоритм Шеннона
Наташа подошла под благословенье, и настоятель посоветовал обратиться за помощью к богу и его угоднику.Тотчас после ухода настоятеля Нашата взяла за руку свою подругу и пошла с ней в пустую комнату.
– Соня, да? он будет жив? – сказала она. – Соня, как я счастлива и как я несчастна! Соня, голубчик, – все по старому. Только бы он был жив. Он не может… потому что, потому… что… – И Наташа расплакалась.
– Так! Я знала это! Слава богу, – проговорила Соня. – Он будет жив!
Соня была взволнована не меньше своей подруги – и ее страхом и горем, и своими личными, никому не высказанными мыслями. Она, рыдая, целовала, утешала Наташу. «Только бы он был жив!» – думала она. Поплакав, поговорив и отерев слезы, обе подруги подошли к двери князя Андрея. Наташа, осторожно отворив двери, заглянула в комнату. Соня рядом с ней стояла у полуотворенной двери.
Князь Андрей лежал высоко на трех подушках. Бледное лицо его было покойно, глаза закрыты, и видно было, как он ровно дышал.
– Ах, Наташа! – вдруг почти вскрикнула Соня, хватаясь за руку своей кузины и отступая от двери.
– Что? что? – спросила Наташа.
– Это то, то, вот… – сказала Соня с бледным лицом и дрожащими губами.
Наташа тихо затворила дверь и отошла с Соней к окну, не понимая еще того, что ей говорили.
– Помнишь ты, – с испуганным и торжественным лицом говорила Соня, – помнишь, когда я за тебя в зеркало смотрела… В Отрадном, на святках… Помнишь, что я видела?..
– Да, да! – широко раскрывая глаза, сказала Наташа, смутно вспоминая, что тогда Соня сказала что то о князе Андрее, которого она видела лежащим.
– Помнишь? – продолжала Соня. – Я видела тогда и сказала всем, и тебе, и Дуняше. Я видела, что он лежит на постели, – говорила она, при каждой подробности делая жест рукою с поднятым пальцем, – и что он закрыл глаза, и что он покрыт именно розовым одеялом, и что он сложил руки, – говорила Соня, убеждаясь, по мере того как она описывала виденные ею сейчас подробности, что эти самые подробности она видела тогда. Тогда она ничего не видела, но рассказала, что видела то, что ей пришло в голову; но то, что она придумала тогда, представлялось ей столь же действительным, как и всякое другое воспоминание. То, что она тогда сказала, что он оглянулся на нее и улыбнулся и был покрыт чем то красным, она не только помнила, но твердо была убеждена, что еще тогда она сказала и видела, что он был покрыт розовым, именно розовым одеялом, и что глаза его были закрыты.
