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

Редакция Без Сменки
Честно. Понятно. С душой.

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

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

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

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

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

Есть 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» уже занят буквой А, в таких случаях лучше строить дерево как на картинке!

Где вы учитесь?

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

Металлы и неметаллы
Неорганическая химия сложна своим многообразием реакций, которые порой очень трудно запомнить, но...
Основные сражения Великой Отечественной войны
Основные сражения ВОВ ⚔️ БИТВА ЗА МОСКВУ 👉🏻 Германская операция «Тайфун» — уничтожение...
Темы для ЕГЭ по профильной математике
Без теории никуда, поэтому составили список тем по каждому заданию из ЕГЭ по математике, чтобы ты...
ЗАДАНИЕ 13 | центры тяжёлого машиностроения России
X тип — центры тяжёлого машиностроения России 📚 Теория для задания: Главные центры тяжёлого...
Литературный герой: лишний человек, маленький человек, новый человек, лирический герой
Какими чертами обладает «лишний человек»?  невозможность реализовать себя в обществе ...
1 КУЧА КАМНЕЙ — решение задачи
👁️ Условие задачи: Петя и Ваня играют в камни, перед ними лежит 1 камень. У каждого игрока есть...

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

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