82
правки
Изменения
Нет описания правки
'''Код Хаффмана с длиной слова не более 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>L</tex> - — ограничение на длину кодового слова, а <tex>P=\{p_{1},p_{2},...,p_{n}\}</tex> - — частоты символов алфавита.
# Отсортируем символы алфавита в порядке возрастания их частот.
# Для каждого символа создадим <tex>L</tex> предметов ценностью <tex>2^{-1}..2^{-L}, каждый из которых имеет вес <tex>p_{i}</tex>.
# С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью <ex>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> - — ограничение на длину кодового слова.
Сначала создадим необходимый набор предметов;
== Пример восстановления ответа. ==
Итак, у нас есть <tex>A=\{A,B,C\}</tex> — алфавит из n различных символов, а также <tex>H=\{2,2,1\}</tex> - — соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами.
Сопоставим первому символу код, состоящий из 1 нуля:
