Кодирование сообщений неравномерным кодом

Неравномерные коды

При кодировании каждому символу сообщения сопоставляют двоичный код. Если все коды имеют одинаковую длину, кодирование называют равномерным. В нём легко определить границы символов: просто отсчитываем биты группами фиксированного размера. Но иногда выгоднее частым символам давать короткие коды, а редким — длинные. Тогда код будет неравномерным, и в среднем сообщение займёт меньше места.

Идея неравномерного кодирования проста: чем чаще встречается символ, тем короче должен быть его код. На этом принципе основано сжатие данных. Однако за экономию приходится платить усложнением декодирования, поэтому к таким кодам предъявляют особое требование.

Проблема декодирования

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

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

Разбор примера

Пусть символам назначены такие коды. Проверим, выполняется ли для них условие однозначности.

Здесь ни один код не является началом другого: код 0 начинается с нуля, а все остальные — с единицы, и среди кодов, начинающихся с единицы, тоже нет таких, что один был бы началом другого. Значит, декодирование однозначно. Раскодируем цепочку битов, читая её слева направо до тех пор, пока не встретим один из кодов, затем начинаем читать следующий символ.

Если бы код символа А был, например, 1, то цепочку 10 можно было бы прочитать двумя способами — как «А, а затем ноль» или как код Б. Возникла бы неоднозначность, и восстановить исходное сообщение точно было бы невозможно. Поэтому условие Фано так важно при построении неравномерных кодов.

Удобный способ строить коды, удовлетворяющие условию Фано, — кодовое дерево. Из корня выходят две ветви, помеченные нулём и единицей, от каждой следующей точки тоже по две ветви. Символы помещают только в концах ветвей, в так называемых листьях. Тогда ни один код не окажется началом другого, потому что путь к листу не продолжается дальше. Так автоматически выполняется условие однозначного декодирования.

Декодирование по дереву наглядно: начинаем от корня и по каждому биту сообщения спускаемся по соответствующей ветви. Дойдя до листа, выписываем найденный символ и снова возвращаемся к корню. Этот процесс повторяют, пока не закончатся биты, и в результате однозначно восстанавливают всё сообщение.

Кратко о главном

• Неравномерный код даёт разным символам коды разной длины.
• Частым символам выгодно давать короткие коды для экономии места.
• Условие Фано: ни один код не должен быть началом другого.
• При выполнении условия Фано сообщение декодируется однозначно.