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

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

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

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

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

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

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