символов заменяются на один символ, так что число символов уменьшается на 
Таким образом, нужно разделить число символов на 
и взять остаток. Если остаток больше 1, то следует сгруппировать равное остатку число символов в один новый символ; если остаток равен 1, то при шервой редукции нужно взять 
символов, а если он равен 0, то 
символов. На всех следующих шагах 
символов с наименьшими вероятностями группируются в один символ. Таким образом, окончательно получаем точно 
символов, которые нужно закодировать. Этим 
символам сопоставим кодовые слова 
На рис. 4.11.1 показано такое кодирование с основанием 4 в применении к частному случаю, взятому из оригинальной статьи Хаффмена.
Рис. 4.11.1. Код Хаффмена с основанием 4
Для доказательства эффективности сначала следует, если необходимо, добавить несколько символов, имеющих нулевую вероятность. Это даст возможность получить такой алфавит из символов 
для которого на каждом шаге объединяются точно по 
символов. Тогда все концевые вершины дерева будут заполнены и, рассуждая так же, как для двоичного дерева, получаем, что никакое другое кодирование не может быть более эффективным.
Задача
4.11.1. Рассмотрите добавление символов с нулевой вероятностью для получения точно 
символов.
символов. На каждом шаге можно, вообще говоря, сопоставить не два, а 
различных символов. Однако, если об этом заранее не позаботиться, на последнем шаге может оказаться невозможным найти в точности 
слов для кодирования. Наименьшее увеличение средней длины кода произойдет, если неполная группа состоит из наименее вероятных символов. Поэтому при первом разбиении нужно сопоставить 
символов (верхнюю группу из 
символов), затем следующие 
символов и так далее до тех пор, пока это возможно; последний (нижний) шаг разделения содержит все, что осталось. На каждом шаге редукции 
