Кодирование с минимальной избыточностью

Для практики важно, чтобы коды сообщений имели по возможности наименьшую длину. Алфавитное кодирование пригодно для любых типов сообщений . Если про более ничего не известно, то сформулировать задачу оптимизации сложно. Однако, на практике, часто имеется дополнительная информация. Например, для текстов на естественных языках известно распределение вероятности появления букв в сообщении. Использование такой информации позволяет корректно поставить и решить задачу оптимизации алфавитного кодирования.

Идея оптимизации алфавитного кодирования может состоять в том, чтобы наиболее часто применяемым буквам входного алфавита сопоставить наиболее короткие элементарные коды. Если длины элементарных кодов равны, как в случае двоично–десятичного кодирования, то данный подход не имеет смысла. Но если длины элементарных кодов различны, то длина кода сообщения зависит от состава букв в сообщении и от того, каких элементарные коды каким буквам назначены.

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

Рассмотрим количественную оценку, позволяющую сравнивать между собой различные схемы алфавитного кодирования. Пусть задан алфавит и вероятность появления букв в сообщении , где – вероятность появления буквы . Будем считать, что .

Для каждой разделимой схемы алфавитного кодирования математическое ожидание длины сообщения при кодировании определяется следующим образом:

, где , (4.1)

и называется средней ценой кодирования при распределении вероятностей .

Пример. Для разделимой схемы , , при распределении вероятностей цена кодирования равна 0,5*1+0,5*2=1,5; а при распределении вероятностей {0.9,0.1} она равна 0.9*1+0.1*2=1,1.

Алфавитное кодирование , для которого средняя цена кодирования минимальна, называется кодированием с минимальной избыточностью, или оптимальным кодированием, для распределения вероятности .