Код Хаффмана с длиной кодового слова не более L бит

Код Хаффмана с длиной слова не более L бит - это вариация классического кода Хоффмана с дополнительным ограничением: длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время [math] O(nL) [/math], где [math]L[/math] - максимальная длина кодового слова, [math]n[/math] - размер алфавита, c помощью сведения задачи к одной из вариаций задачи о банкомате.

Задача о банкомате.

В вариации задаче о банкомате, которую мы рассмотрим, у вас имеется [math]N[/math] монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы являются степенями двойки и не превышают [math]2^0[/math]. Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен [math]S[/math] (натуральное число), а суммарный вес минимален.

Алгоритм решения задачи о банкомате.

Рассмотрим алгоритм решения приведенной выше вариации задачи о банкомате, считая, что решение существует.

1. Разделим имеющиеся у нас монеты на списки по номиналу (свой список для каждого номинала) и упорядочим монеты по возрастанию весов внутри списков, а списки в порядке возрастания номиналов.
2. Рассмотрим первый список (с монетами самого низкого номинала). Разобьем в нем все монеты на пары (1 и 2, 3 и 4 и т. д.) Заменим каждую пару монет одной новой монетой, номинал и вес которой равен сумме номиналов и весов старых. Если число монет было нечетно, то последнюю монету, которая не имеет пары, исключим из рассмотрения.
3. Объединим первый список со вторым так, чтобы монеты в получившемся списке остались упорядочены по весу.
4. Будем повторять шаги 2-3 до тех пор, пока у нас не останется один список. В нем будут содержаться монеты номиналом 1 ([math]2^0[/math]), упорядоченные по весу. Возьмем первые [math]S[/math] монет из списка. Это и будет ответ к задаче.

Сведение к генерации кода Хоффмана с длиной кодового слова не более L бит.

Пусть [math]L[/math] - ограничение на длину кодового слова, а [math]P=\{p_{1},p_{2},...,p_{n}\}[/math] - частоты символов алфавита.

1. Отсортируем символы алфавита в порядке возрастания их частот.
2. Для каждого символа создадим [math]L[/math] монет номиналами [math]2^{-1}..2^{-L}, каждая из которых имеет вес \lt tex\gt p_{i}[/math].
3. С помощью описанного выше алгоритма выберем набор монет суммарным номиналом [math]n - 1[/math] ([math]n[/math] - размер алфавита) с минимальным суммарным весом.
4. Посчитаем массив [math]H=\{h_{1},h_{2},...,h_{n}\}[/math], где [math]h_{i}[/math] - количество монет номинала [math]p_{i}[/math], которые попали в наш набор.

При этом [math]h_{i}[/math] - это длина кодового слова для [math]i[/math]-го символа.Зная длины кодовых слов, легко восстановить и сам код.