В предыдущем разделе мы убедились в том, что источники информации, вообще
говоря, избыточны в том смысле, что, при эффективном кодировании можно уменьшить
затраты на передачу или хранение порождаемой ими информации. Для представления
данных потребуется тем меньше бит, чем меньше энтропия. Это значит, что для
эффективного кодирования удобны источники, в которых некоторые буквы
(последовательности букв) имеют существенно большую вероятность, чем другие буквы
(последовательности). Не нужно долго изучать теорию информации, чтобы догадаться,
что для таких источников нужно использовать кодирование, сопоставляющее часто
встречающимся сообщениям короткие кодовые комбинации, а редким сообщениям –
длинные. Реализация этой простой идеи является предметом исследования в данном
разделе.
Мы начнем с кодирования отдельных букв источника. Оптимальным побуквенным
кодом является известный код Хаффмана. Однако, для того, чтобы понять, как правильно
кодировать последовательности, нам придется изучить неоптимальные побуквенные коды
– код Шеннона и код Гилберта-Мура. От них – один шаг к пониманию арифметического
кодирования, которое позволяет предельно эффективно кодировать длинные
последовательности и обладает при этом относительно невысокой сложностью.
2.1. Постановка задачи неравномерного побуквенного кодирования
Предположим, что для некоторого дискретного источника X с известным распределением вероятностей
{ p( x), x ? X }
требуется построить эффективный неравномерный двоичный код над алфавитом A = {a} . Как и в предыдущем разделе, мы сосредоточим внимание на двоичных кодах, т.е. мы предполагаем, что
A = {0,1} . Дело втом, что, во-первых, все идеи в полной мере иллюстрируются на этом примере. Во-
трудности. Помимо этого, на практике для кодирования источников используются почти
исключительно двоичные коды.
В качестве примера источника рассмотрим алфавит русского языка. Сразу же
вспоминается азбука Морзе, которая сопоставляет каждой букве комбинацию точек «•» и
тире «?». Например, часто встречающейся букве «е» соответствует комбинация «•», а
более редкой букве «ч» соответствует комбинация «? ? ? •». Однако, более пристальный
взгляд убеждает, что мы не получим хорошего кода просто заменив точки нулями, а тире
– единицами. Нам будет не хватать пауз, разделяющих символы внутри букв (эта пауза
соответствует интервалу времени равному времени передачи точки), пауз,