Равномерное и неравномерное кодирование

В ЕГЭ по информатике есть две вещи: 

◾Равномерное кодирование — все коды одинаковой длины. 

◾Неравномерное кодирование — НЕ все коды одинаковой длины. 

В целом, в школе этому обычно не уделяют никакого внимания, особенно схожести и связности и смыслу этих подходов. Сегодня мы как раз попробуем разобраться, почему существует два подхода и что у них общего. 

◾РАВНОМЕРНОЕ кодирование

Есть N объектов. Каждый из них кодируется минимально возможным и одинаковым кол-вом бит. Берём формулу log2(N), округляем в большую сторону до целого!

Пример:

Дано 6 объектов. Log2(6) = 2,584962500721156 = 3 бита, но вот этот момент, что по идее нужно не 3, а 2,5849… бита настораживает.

Наступление события с заданной вероятностью несёт какое-то количество информации. Вот наши 6 объектов. И про вероятность ни слова. Значит, что «вероятности объектов» равны.

Поясним: среди 6 объектов (совершенно разных) можно достать один с вероятностью p = 1/6. И информации это несёт -log2(1/6)=2.584962500721156…

◾НЕРАВНОМЕРНОЕ кодирование

А этот вариант как раз позволяет нам обойтись минимумом бит для кодирования заданных объектов. Строятся такие коды на основании частоты (вероятности) появления таких объектов (или кодовых слов). 

Для того, чтобы это продемонстрировать, построим коды для наших 6 объектов. Назовём их A B C D E F и присвоим им двоичные коды. Вероятность каждого объекта p = 1/6. 

Какой алгоритм действий? 

1) Выписываем объекты с вероятностями;

2) Объединяем по парам объекты с наименьшими вероятностями в один объект с вероятностью p = p1 + p2;

3) Повторяем пункт 2) пока не получим сумму p=1 ;

4) Теперь каждой веточке на каждом уровне присваиваем свой «код» 0 или 1 — последовательность вообще неважна — главное, чтобы из одного узла выходила в одну сторону единичка, а в другую нолик;

5) Теперь идём от корня к нашим исходным объектам и получаем код… 

В нашем случае получилось: 

A — 000 

B — 001 

C — 010 

D — 011 

E — 10 

F — 11 

💡 Тут ещё выполняется условие Фано, которое можно сформулировать следующим образом: «ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова». 

То есть если у нас есть код «000», то мы уже не можем использовать код «0001» или «0000», так как код «000» уже занят буквой А, в таких случаях лучше строить дерево как на картинке!

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter. Мы обязательно поправим!

Редакция Без Сменки
Честно. Понятно. С душой.
Где вы учитесь?

Вам так же будет интересно

Степени и логарифмы
Давно хотели освежить в памяти тему логарифмов, чтобы сдать ЕГЭ по математике на высший балл? Тогда...
Религии в современном мире, свобода совести
В современном мире можно найти родоплеменные верования (тотемизм, анимизм и др.),...
Свойства средних солей
1) + металлы Соль вступает в реакцию замещения с металлом, если этот металл стоит левее металла из...
Орфоэпические нормы
Чтобы научиться находить ошибки в постановке ударения, тебе придется запомнить немало сложных слов....
Химические свойства бензола
Устойчивая 6π-система объясняет нежелание бензола вступать в реакции присоединения, однако...
Система отсчёта
Системой отсчёта в физике называют совокупность тела отсчета, системы координат, связанной с телом...

0 комментария

Авторизуйтесь, чтобы оставить комментарий.

Подпишитесь на еженедельную рассылку полезных материалов про ЕГЭ, высшее образование и вузы и получите скидку на курсы Вебиума

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: