Изменения

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

== Задача о банкоматеДанный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. ==В вариации задаче о банкоматеНапример, которую мы рассмотрим, у вас имеется пусть дан алфавит из 5 символов <tex>NA=\{A,B,C,D,E\}</tex> монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы , а частоты символов являются степенями двойки и не превышают : <tex>P=\{1,2^0</tex>. Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен <tex>S4, 8, 16\}</tex> (натуральное число), а суммарный вес минимален.Тогда классический код Хоффмана будет выглядеть следующим образом:

== Алгоритм решения задачи о банкомате. ==Рассмотрим алгоритм решения приведенной выше вариации задачи о банкомате, считая, что решение существует.# Разделим имеющиеся у нас монеты на списки по номиналу (свой список для каждого номинала) и упорядочим монеты по возрастанию весов внутри списков, а списки в порядке возрастания номиналов.# Рассмотрим первый список (с монетами самого низкого номинала). Разобьем в нем все монеты на пары (1 и 2, 3 и 4 и т. д.) Заменим каждую пару монет одной новой монетой, номинал и вес которой равен сумме номиналов и весов старых. Если число монет было нечетно, то последнюю монету, которая не имеет пары, исключим из рассмотрения.# Объединим первый список со вторым так, чтобы монеты в получившемся списке остались упорядочены по весу.# Будем повторять шаги 2-3 до тех пор, пока у нас не останется один список, в котором содержатся монеты номинала 1 (<tex>2^0</tex>), упорядоченные по весу. Возьмем первые <tex>SA = 1111 </tex> монет из списка. Это и будет ответ к задаче.

<tex> B = 1110 </tex> <tex> C = 110 </tex> <tex> D = 10 </tex> <tex> E = 0 </tex> Самое длинное кодовое слово здесь имеет длину 4. Пусть мы хотим, чтобы слова в нашем коде были не длиннее трех бит. Тогда алгоритм, который будет описан ниже, генерирует такой код: <tex> A = 000 </tex> <tex> B = 001 </tex> <tex> C = 010 </tex> <tex> D = 011 </tex> <tex> E = 100 </tex> Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину L бит. Тогда мы можем закодировать <tex> 2^L </tex> символов. Таким образом, нельзя получить описанный выше код, если <tex> n > 2^L </tex>. == Сведение задачи о рюкзаке к генерации оптимального префиксного кода Хоффмана с длиной кодового слова не более L бит. ==Пусть <tex>L</tex> - — ограничение на длину кодового слова, а <tex>P=\{p_{1},p_{2},...,p_{n}\}</tex> - — частоты символов алфавита.Алгоритм генерации кода будет следующим:

# Для каждого символа создадим <tex>L</tex> монет номиналами предметов ценностью <tex>2^{-1}..2^{-L}</tex>, каждая каждый из которых имеет вес <tex>p_{i}</tex>.# С помощью описанного выше алгоритма задачи о рюкзаке выберем набор монет суммарным номиналом предметов суммарной ценностью <tex>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>-го символа.Зная длины кодовых слов, легко восстановить и сам код.

# Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин - — в алфавитном порядке.

== Пример работы алгоритма Заметим, что при генерации кода Хоффмана с длиной каждого следующего кодового слова не более L бит ==Пусть <tex>A=\{a_{1},a_{2}в качестве его префикса выступает последовательность, лексикографически большая,чем предыдущее кодовое слово (т.к..,a_{n}\}</tex> — алфавит из n различных символов, <tex>P=\{p_{1},p_{2}мы берем следующее двоичное число),а значит ни для каких двух кодовых слов одно не может быть префиксом другого.Т.е.код,p_{n}\}</tex> — соответствующий ему набор частот. Пусть <tex>L = 2</tex> - ограничение на длину кодового словасгенерированный таким образом является префиксным.

Сначала создадим необходимый набор монет;== Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит == Пусть <tex>(2^A=\{-1}; 1)A,B, (2^{-2C\}; 1)</tex> — алфавит из трех различных символов, (2^<tex>P=\{-1}; 2), (2^{-2}; 2), (2^{-13\}; 3), (</tex> — соответствующий ему набор частот. Пусть <tex>L = 2^{-2}; 3) </tex>— ограничение на длину кодового слова.

! Символ | Номинал | Частота || Предметы|- align = "center"| A || 1 || <tex> (2^{-21} </tex> || ; 1), <tex>(2^{-2}; 1)</tex> |- align = "center"| B || 2 || <tex>(2^{-21}; 2)</tex> || <tex>, (2^{-2}; 32)</tex>|-align = "center"| Номинал = <tex> 2^{-1} </tex> C || <tex>(2^{-1}; 1)</tex> 3 || <tex>(2^{-1}; 23)</tex> || <tex>, (2^{-2}; 3)</tex>

Выполним объединение первого списка по парам Решим задачу о рюкзаке для заданного набора и исключим последний элементвыберем предметы суммарной ценностью <tex> n - 1 = 2 </tex> с минимальным суммарным весом. В нашем случае в оптимальный набор попадут следующие предметы:  <tex>(2^{-1}; 1), (2^{-1}; 2), (2^{-1}; 3), (2^{-2}; 1), (2^{-2}; 2) </tex> Посчитаем массив <tex> H </tex>: <tex>H=\{2,2,1\}</tex> Итак, тмы получили длины кодовых слов для символов.кОсталось восстановить ответ. для него нет пары: == Пример восстановления ответа. ==

{| class="wikitable"| Номинал = Итак, у нас есть <tex> 2^A=\{-2A,B,C\} </tex> || — алфавит из n различных символов, а также <tex>(2^{-1}; 3)</tex> || || |-| Номинал H= <tex> 2^\{-1} </tex> || <tex>(2^{-1}; 1)</tex> || <tex>(,2^{-,1\}; 2)</tex> || <tex>(2^{-2}; 3)</tex>— соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами.|}Сопоставим первому символу код, состоящий из 1 нуля:

Теперь нам нужно набрать монеты суммарным номиналом <tex> n - 1 A = 2 11 </tex> с минимальным суммарным весом, т.е. просто возьмем первые две монеты из итогового списка. Посчитаем массив <tex> H </tex>. Обратите внимание, что при подсчете количества монет определенного веса мы учитываем монеты, которые были даны изначально, а не те, которые получились путем слияния исходных.

<tex>H=\{2,2,1\}</tex>=См. также==*[[Алгоритм_Хаффмана | Алгоритм Хаффмана]]*[[Задача_о_рюкзаке | Задача о рюкзаке]]

Итак, мы получили длины кодовых слов для символов==Источники информации==*[http://en. Осталось восстановить ответwikipedia.org/wiki/Package-merge_algorithm Package-merge algorithm]*[http://en.wikipedia.org/wiki/Canonical_Huffman_code Canonical Huffman code]