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