Оптимальный префиксный код с длиной кодового слова не более L бит

Определение:

Оптимальный префиксный код с длиной кодового слова не более L бит — это код, обладающий следующими свойствами: длина кодового слова не превышает заданной константы, является оптимальным среди всех префиксных кодов, удовлетворяющих первому условию.

Здесь будет приведен алгоритм, решающий эту задачу за время [math] O(nL) [/math], где [math]L[/math] — максимальная длина кодового слова, [math]n[/math] — размер алфавита, c помощью сведения задачи к задаче о рюкзаке.

Пример

Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из [math]5[/math] символов [math]A=\{A, B, C, D, E\}[/math], а частоты символов являются степенями двойки: [math]P=\{1, 2 ,4, 8, 16\}[/math]. Тогда классический код Хаффмана будет выглядеть следующим образом:

Символ	Частота	Код
A	1	1111
B	2	1110
C	4	110
D	8	10
E	16	0

Самое длинное кодовое слово здесь имеет длину [math]4[/math]. Пусть мы хотим, чтобы слова в нашем коде были не длиннее трех бит. Тогда алгоритм, который будет описан ниже, генерирует такой код:

Символ	Частота	Код
A	1	000
B	2	001
C	4	010
D	8	011
E	16	1

Важно заметить следующий факт: в худшем случае все кодовые слова будут иметь длину [math]L[/math] бит. Тогда мы можем закодировать [math] 2^L [/math] символов. Таким образом, нельзя получить описанный выше код, если [math] n \gt 2^L [/math].

Сведение к задаче о рюкзаке

Пусть [math]L[/math] — ограничение на длину кодового слова, а [math]P=\{p_{1},p_{2},\dots,p_{n}\}[/math] — частоты символов алфавита. Алгоритм генерации кода будет следующим:

1. Для каждого символа создадим [math]L[/math] предметов ценностью [math]2^{-1}\dots2^{-L}[/math], каждый из которых имеет вес [math]p_{i}[/math].
2. С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью [math]n - 1[/math] ([math]n[/math] — размер алфавита) с минимальным суммарным весом.
3. Посчитаем массив [math]H=\{h_{1},h_{2},\dots,h_{n}\}[/math], где [math]h_{i}[/math] — количество предметов ценностью [math]p_{i}[/math], которые попали в наш набор.

При этом [math]h_{i}[/math] — это длина кодового слова для [math]i[/math]-го символа. Зная длины кодовых слов, легко восстановить и сам код.

Из последнего утверждения и шага два легко заметить, что длина кодового слова, сгенерированного приведенным алгоритмом, действительно не превысит [math]L[/math]. Это так, потому что мы создаем ровно [math]L[/math] предметов веса [math]p_{i}[/math] (частота символа). А значит, если в худшем случае мы возьмем все предметы данного веса, то их количество не превысит [math]L[/math].

Убедимся также, что необходимую сумму ([math]n - 1[/math]) всегда можно набрать. Зафиксируем размер алфавита равным  [math]n = 2^k[/math]. Теперь вспомним неравенство, которым связаны  [math]n[/math] и [math]L[/math]: [math] n \leqslant 2^L [/math]. Возьмем минимально возможное значение [math]L[/math] такое, что [math]2^L = n[/math]. По условию у нас есть по [math]n[/math] монет номинала [math]2^{-i}[/math], где [math]1 \leqslant i \leqslant L[/math]. Попробуем посчитать суммарную стоимость имеющихся монет:

[math]\frac{n}{2^1} + \frac{n}{2^2} + \dots + \frac{n}{2^L} [/math]

Поскольку [math]n = 2^L[/math]:

[math]\frac{2^L}{2^1} + \frac{2^L}{2^2} + \dots + \frac{2^L}{2^L}[/math][math] = 2^{L - 1} + 2 ^ {L - 2} + \dots + 2^{L - L} = 2^L - 1 = n - 1 [/math]

Таким образом, мы набрали необходимую сумму, используя все предметы. Но так как мы рассматривали граничный случай, при бОльших значениях [math]L[/math] данную сумму гарантированно можно набрать.

Оптимальность же кода следует из оптимальности решения задачи о рюкзаке. Действительно, частота символа — это вес предметов, соответствующих ему. Значит, чем чаще символ встречается в тексте, тем реже он будет попадать в наш рюкзак (будет выгоднее брать предметы аналогичной ценности, но меньшего веса, соответствующие более редким символам), а значит, его код будет короче. Таким образом, код, сгенерированный данным алгоритмом, будет оптимальным среди кодов с длиной кодового слова не более [math]L[/math].

Восстановление ответа.

Рассмотрим процедуру восстановления ответа по заданному алфавиту и известным длинам кодовых слов.

1. Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин — в алфавитном порядке.
2. Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
3. Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.

Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (ведь мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Значит, код, сгенерированный таким образом является префиксным.

Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит

Пусть [math]A=\{A,B,C\}[/math] — алфавит из трех различных символов, [math]P=\{1,2,3\}[/math] — соответствующий ему набор частот. Пусть [math]L = 2[/math] — ограничение на длину кодового слова.

Сначала создадим необходимый набор предметов;

Символ	Частота	Предметы
[math]A[/math]	[math]1[/math]	[math] (2^{-1}, 1), (2^{-2}, 1) [/math]
[math]B[/math]	[math]2[/math]	[math](2^{-1}, 2), (2^{-2}, 2)[/math]
[math]C[/math]	[math]3[/math]	[math] (2^{-1}, 3), (2^{-2}, 3)[/math]

Решим задачу о рюкзаке для заданного набора и выберем предметы суммарной ценностью [math] n - 1 = 2 [/math] с минимальным суммарным весом. В нашем случае в оптимальный набор попадут следующие предметы:

[math](2^{-1}, 1), (2^{-1}, 2), (2^{-1}, 3), (2^{-2}, 1), (2^{-2}, 2) [/math]

Посчитаем массив [math] H [/math]:

[math]H=\{2,2,1\}[/math]

Итак, мы получили длины кодовых слов для символов. Осталось восстановить ответ.

Пример восстановления ответа.

Итак, у нас есть [math]A=\{A,B,C\}[/math] — алфавит из [math]n[/math] различных символов, а также [math]H=\{2,2,1\}[/math] — соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами.

Сопоставим первому символу код, состоящий из одного нуля:

[math] C = 0 [/math]

Сопоставим следующему символу следующее двоичное число. Так как длина кода увеличилась на один, то припишем справа ноль:

[math] B = 10 [/math]

Сопоставим следующему символу следующее двоичное число.

[math] A = 11 [/math]

См. также

• Алгоритм Хаффмана
• Алгоритм Ху-Таккера

Источники информации

• Wikipedia — Package-merge algorithm
• Wikipedia — Canonical Huffman code