'''Код Хаффмана с длиной слова не более L бит''' - это вариация классического кода Хоффмана с дополнительным ограничением: длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время <tex> O(nL) </tex>, где <tex>L</tex> - максимальная длина кодового слова, <tex>n</tex> - размер алфавита, c помощью сведения задачи к одной из вариаций '''задачи задаче о банкомате'''рюкзаке.
Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из 5 символов <tex>A=\{A,B,C, C, D\}</tex>, а частоты символов являются степенями двойки: <tex>P=\{1,2,4, 8, 16\}</tex>. Тогда классический код Хоффмана будет выглядеть следующим образом:
Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину L бит. Тогда мы можем закодировать <tex> 2^L </tex> символов. Таким образом, нельзя получить описанный выше код, если <tex> n > 2^L </tex>.
== Задача о банкомате. ==
В вариации задаче о банкомате, которую мы рассмотрим, у вас имеется <tex>N</tex> монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы являются степенями двойки и не превышают <tex>2^0</tex>. Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен <tex>S</tex> (натуральное число), а суммарный вес минимален.
== Алгоритм решения задачи о банкомате. ==
Рассмотрим алгоритм решения приведенной выше вариации задачи о банкомате, считая, что решение существует.
# Разделим имеющиеся у нас монеты на списки по номиналу (свой список для каждого номинала) и упорядочим монеты по возрастанию весов внутри списков, а списки в порядке возрастания номиналов.
# Рассмотрим первый список (с монетами самого низкого номинала). Разобьем в нем все монеты на пары (1 и 2, 3 и 4 и т. д.) Заменим каждую пару монет одной новой монетой, номинал и вес которой равен сумме номиналов и весов старых. Если число монет было нечетно, то последнюю монету, которая не имеет пары, исключим из рассмотрения.
# Объединим первый список со вторым так, чтобы монеты в получившемся списке остались упорядочены по весу.
# Будем повторять шаги 2-3 до тех пор, пока у нас не останется один список, в котором содержатся монеты номинала 1 (<tex>2^0</tex>), упорядоченные по весу. Возьмем первые <tex>S</tex> монет из списка. Это и будет ответ к задаче.
== Сведение к генерации кода Хоффмана с длиной кодового слова не более L бит. ==
# Отсортируем символы алфавита в порядке возрастания их частот.
# Для каждого символа создадим <tex>L</tex> монет номиналами предметов ценностью <tex>2^{-1}..2^{-L}, каждая каждый из которых имеет вес <tex>p_{i}</tex>.# С помощью описанного выше алгоритма задачи о рюкзаке выберем набор монет суммарным номиналом предметов суммарной ценностью <texex>n - 1</tex> (<tex>n</tex> - размер алфавита) с минимальным суммарным весом. # Посчитаем массив <tex>H=\{h_{1},h_{2},...,h_{n}\}</tex>, где <tex>h_{i}</tex> - количество монет номинала предметов ценностью <tex>p_{i}</tex>, которые попали в наш набор.
При этом <tex>h_{i}</tex> - это длина кодового слова для <tex>i</tex>-го символа.Зная длины кодовых слов, легко восстановить и сам код.
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>P=\{p_{1},p_{2},...,p_{n}\}</tex> — соответствующий ему набор частот. Пусть <tex>L = 2</tex> - ограничение на длину кодового слова.
Сначала создадим необходимый набор монетпредметов;
<tex>(2^{-1}; 1), (2^{-2}; 1), (2^{-1}; 2), (2^{-2}; 2), (2^{-1}; 3), (2^{-2}; 3) </tex>
Распределим их по спискам:{| class="wikitable"| Номинал = <tex> 2^{-2} </tex> || Решим задачу о рюкзаке для заданного набора и выберем предметы суммарной ценностью <tex>(2^{n -2}; 1)</tex> || <tex>(2^{-2}; 2)</tex> || <tex>(2^{-2}; 3)</tex>|-| Номинал = <tex> 2^{-1} </tex> || <tex>(2^{-1}; 1)</tex> || <tex>(2^{-1}; 2)</tex> || <tex>(2^{-2}; 3)</tex>|} Выполним объединение первого списка по парам и исключим последний элемент, т.кс минимальным суммарным весом. для него нет пары: {| class="wikitable"| Номинал = <tex> 2^{-2} </tex> || <tex>(2^{-1}; 3)</tex> || || |-| Номинал = <tex> 2^{-1} </tex> || <tex>(2^{-1}; 1)</tex> || <tex>(2^{-1}; 2)</tex> || <tex>(2^{-2}; 3)</tex>|} Объединим первый список со вторым: {| class="wikitable"| Номинал = <tex> 2^{-2} </tex> || || || |-| Номинал = <tex> 2^{-1} </tex> || <tex>(2^{-1}; 1)</tex> || <tex>(2^{-1}; 2)</tex> || <tex>(2^{-1}; 3)</tex> || <tex>(2^{-1}; 3)</tex>|} Выполним объединение второго списка по парамВ нашем случае в оптимальный набор попадут следующие предметы:
{| class="wikitable"| Номинал = <tex> (2^{-1}; 1), (2^{0-1} </tex> || <tex>; 2), (2^{0-1}; 3)</tex> || <tex>, (2^{-2}; 1), (2^{0-2}; 62)</tex> |}
Теперь нам нужно набрать монеты суммарным номиналом <tex> n - 1 = 2 </tex> с минимальным суммарным весом, т.е. просто возьмем первые две монеты из итогового списка. Посчитаем массив <tex> H </tex>. Обратите внимание, что при подсчете количества монет определенного веса мы учитываем монеты, которые были даны изначально, а не те, которые получились путем слияния исходных.
<tex>H=\{2,2,1\}</tex>
