В русском алфавите 32 буквы, е и ё можно считать за одну букву, предположим их надо закодировать равномерным кодом в алфавите . Тогда длина каждого кодового слова должна быть равна 5, любое сообщение становится длиннее в 5 раз. С другой стороны, такие буквы как щ; ч; ы; ъ; ь и так далее встречаются редко, их можно было бы закодировать более длинными кодовыми словами, а встречающиеся часто – более короткими. Так возникает идея оптимальных кодов, которая связана с частотной (вероятностной) характеристикой букв кодируемого алфавита.
Каждая буква кодируемого алфавита обладает своей частотой (вероятностью) использования в языке, обозначим ее . Пусть задано алфавитное кодирование: , длина равна . Посмотрим, как меняется при кодировании длина слова , ɱ , то есть найдем длину слова .
Буква входит в слово раз, при кодировании она даст длину , следовательно, длина слова будет равна
.
Определение. Ценой кодирования называется число , где
.
Цена кодирования показывает, во сколько раз увеличивается длина любого слова при кодировании, и является средней длиной кодового слова (математическим ожиданием кодового слова).
|
|
При фиксированных алфавитах и рассмотрим множество взаимно-однозначных кодов , цена кодирования каждого .
Найдем на множестве , он очевидно, будет характеристикой кодируемого алфавита :
. (8)
Определение. Код , такой что , называется оптимальным кодом или кодом с минимальной избыточностью.
Пусть – оптимальный код, заданный набором кодовых слов с длинами . Можно построить префиксный код (по теореме о существовании префиксного кода) с тем же набором длин кодовых слов, следовательно, с той же ценой кодирования.
Замечание. Среди оптимальных кодов всегда есть префиксный код.
Пример 7. Пусть даны алфавиты с вероятностями и и кодирующий алфавит .
Рассмотрим два кода и . Код – равномерный, – префиксный, оба однозначно декодируемые. Найдем для каждого цену кодирования.
.
Рассмотрим свойства оптимальных префиксных кодов.