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

2015-01-08T18:21:21Z

84.54.248.47:

'''Оптимальный префиксный код с длиной кодового слова не более 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>. Тогда классический код Хоффмана будет выглядеть следующим образом:

{| class="wikitable"
! Символ || Частота || Код
|- align = "center"
| A || 1 || 1111
|- align = "center"
| B || 2 || 1110
|- align = "center"
| C || 4 || 110
|- align = "center"
| D || 8 || 10
|- align = "center"
| E || 16 || 0
|}

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

{| class="wikitable"
! Символ || Частота || Код
|- align = "center"
| A || 1 || 000
|- align = "center"
| B || 2 || 001
|- align = "center"
| C || 4 || 010
|- align = "center"
| D || 8 || 011
|- align = "center"
| E || 16 || 1
|}

Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину <tex>L</tex> бит. Тогда мы можем закодировать <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}\dots2^{-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>-го символа.Зная длины кодовых слов, легко восстановить и сам код.

Из последнего утверждения и шага 2 легко заметить, что длина кодового слова, сгенерированного приведенным алгоритмом, действительно не превысит <tex>L</tex>. Оптимальность же кода следует из оптимальности решения задачи о рюкзаке. Действительно, частота символа - это вес предеметов, соответствующих ему. Значит, чем чаще символ встречается в тексте, тем реже он будет попадать в наш рюкзак (будет выгоднее брать предметы аналогичной ценности, но меньшего веса, соответствующие более редким символам), а значит, его код будет короче.

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

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

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

Сначала создадим необходимый набор предметов;
{| class="wikitable"
! Символ || Частота || Предметы
|- align = "center"
| <tex>A</tex> || <tex>1</tex> || <tex> (2^{-1}, 1), (2^{-2}, 1) </tex>
|- align = "center"
| <tex>B</tex> || <tex>2</tex> || <tex>(2^{-1}, 2), (2^{-2}, 2)</tex>
|- align = "center"
| <tex>C</tex> || <tex>3</tex> || <tex> (2^{-1}, 3), (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>

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

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

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

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

<tex> C = 0 </tex>

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

<tex> B = 10 </tex>

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

<tex> A = 11 </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]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Алгоритмы сжатия ]]

Викиконспекты - Вклад участника [ru]

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