Основывается на неравенстве Макмиллана.

Алгоритм

1. Вычисляем потенциальную длину кодового слова каждого символа так:
   1. Берём его частоту
   2. $l_i = \lceil \log_2{p_i}\rceil$
2. Имеем набор длин кодовых слов
3. Придумаем код с такими длинами:
   1. Рисуем префиксное дерево, чтобы построенный код был префиксным
   2. Делаем его насыщенным, тогда стоимость будет маленькой.

Мокеев Д.Б. - Лекции по дискретной математике