Неравномерное кодирование — кодирование, при котором НЕ все коды имеют одинаковую длину.
◾️НЕРАВНОМЕРНОЕ кодирование.
А этот вариант как раз позволяет нам обойтись минимумом бит для кодирования заданных объектов. Строятся такие коды на основании частоты (вероятности) появления таких объектов (или кодовых слов).
Для того, чтобы это продемонстрировать, построим коды для наших 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» уже занят буквой А, в таких случаях лучше строить дерево как на картинке!
Авторизуйтесь, чтобы оставить комментарий.