Изменения
Нет описания правки
==Пример.==
Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из <tex>5 </tex> символов <tex>A=\{A,B,C, C, D\}</tex>, а частоты символов являются степенями двойки: <tex>P=\{1,2,4, 8, 16\}</tex>. Тогда классический код Хоффмана Хаффмана будет выглядеть следующим образом:
{| class="wikitable"
Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину <tex>L</tex> бит. Тогда мы можем закодировать <tex> 2^L </tex> символов. Таким образом, нельзя получить описанный выше код, если <tex> n > 2^L </tex>.
== Сведение задачи о рюкзаке к генерации оптимального префиксного кода с длиной кодового слова не более L бит к задаче о рюкзаке ==Пусть <tex>L</tex> — ограничение на длину кодового слова, а <tex>P=\{p_{1},p_{2},...\dots,p_{n}\}</tex> — частоты символов алфавита. Алгоритм генерации кода будет следующим:
# Для каждого символа создадим <tex>L</tex> предметов ценностью <tex>2^{-1}\dots2^{-L}</tex>, каждый из которых имеет вес <tex>p_{i}</tex>.
# С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью <tex>n - 1</tex> (<tex>n</tex> — размер алфавита) с минимальным суммарным весом.
# Посчитаем массив <tex>H=\{h_{1},h_{2},...\dots,h_{n}\}</tex>, где <tex>h_{i}</tex> — количество предметов ценностью <tex>p_{i}</tex>, которые попали в наш набор.
При этом <tex>h_{i}</tex> — это длина кодового слова для <tex>i</tex>-го символа. Зная длины кодовых слов, легко восстановить и сам код.
== Восстановление ответа. ==
Рассмотрим процедуру восстановления ответа по заданному алфавиту и известным длинам кодовых слов.
# Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин — в алфавитном порядке.
# Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
==Источники информации==
*[http://en.wikipedia.org/wiki/Package-merge_algorithm Wikipedia - — Package-merge algorithm]*[http://en.wikipedia.org/wiki/Canonical_Huffman_code Wikipedia - — Canonical Huffman code]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
