Изменения

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

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

==Пример==Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из <tex>5</tex> символов <tex>A=\{A, B , C, D, E\}</tex>, а частоты символов являются степенями двойки: <tex>P= 1110 \{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> C = 110 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> D = 10 n > 2^L </tex>.

== Сведение к задаче о рюкзаке ==Пусть <tex> E = 0 L</tex> Самое длинное кодовое слово здесь имеет — ограничение на длину 4. Пусть мы хотимкодового слова, а <tex>P=\{p_{1},p_{2},\dots, чтобы слова в нашем коде были не длиннее трех битp_{n}\}</tex> — частоты символов алфавита. Тогда алгоритм, который Алгоритм генерации кода будет описан ниже, генерирует такой кодследующим:

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

При этом <tex> B = 001 h_{i}</tex>— это длина кодового слова для <tex>i</tex>-го символа. Зная длины кодовых слов, легко восстановить и сам код.

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

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

<texdpi = "160"> E = 100 \frac{n}{2^1} + \frac{n}{2^2} + \dots + \frac{n}{2^L} </tex>

Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину L бит. Тогда мы можем закодировать <tex> 2^L </tex> символов. Таким образом, нельзя получить описанный выше код, если Поскольку <tex> n > = 2^L </tex>.:

== Сведение задачи о рюкзаке к генерации оптимального префиксного кода с длиной кодового слова не более L бит. ==Пусть <texdpi = "160">\frac{2^L}{2^1} + \frac{2^L}{2^2} + \dots + \frac{2^L}{2^L}</tex> — ограничение на длину кодового слова, а <tex>P=\{p_2^{L - 1},p_+ 2 ^ {L - 2},...,p_+ \dots + 2^{L - L} = 2^L - 1 = n}\}- 1 </tex> — частоты символов алфавита. Алгоритм генерации кода будет следующим:

# Отсортируем символы алфавита в порядке возрастания их частот.# Для каждого символа создадим <tex>L</tex> предметов ценностью <tex>2^{-1}..2^{-L}</tex>Таким образом, каждый из которых имеет вес <tex>p_{i}</tex>.# С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью <ex>n - 1</tex> (<tex>n</tex> — размер алфавита) с минимальным суммарным весом. # Посчитаем массив <tex>H=\{h_{1}мы набрали необходимую сумму,h_{2},..используя все предметы.Но так как мы рассматривали граничный случай,h_{n}\}при бОльших значениях </tex>, где <tex>h_{i}L</tex> — количество предметов ценностью <tex>p_{i}</tex>, которые попали в наш наборданную сумму гарантированно можно набрать.

При этом <tex>h_Оптимальность же кода следует из оптимальности решения задачи о рюкзаке. Действительно, частота символа {{i---}}</tex> — это длина вес предметов, соответствующих ему. Значит, чем чаще символ встречается в тексте, тем реже он будет попадать в наш рюкзак (будет выгоднее брать предметы аналогичной ценности, но меньшего веса, соответствующие более редким символам), а значит, его код будет короче. Таким образом, код, сгенерированный данным алгоритмом, будет оптимальным среди кодов с длиной кодового слова для не более <tex>iL</tex>-го символа.Зная длины кодовых слов, легко восстановить и сам код.

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

| <tex>A </tex> || <tex>1 </tex> || <tex> (2^{-1}; , 1), (2^{-2}; , 1) </tex>

| <tex>B </tex> || <tex>2 </tex> || <tex>(2^{-1}; , 2), (2^{-2}; , 2)</tex>

| <tex>C </tex> || <tex>3 </tex> || <tex> (2^{-1}; , 3), (2^{-2}; , 3)</tex>

<tex>(2^{-1}; , 1), (2^{-1}; , 2), (2^{-1}; , 3), (2^{-2}; , 1), (2^{-2}; , 2) </tex>

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

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

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

*[[Задача_о_рюкзаке Алгоритм_Ху-Таккера | Задача о рюкзакеАлгоритм Ху-Таккера]]

*[http://en.wikipedia.org/wiki/Package-merge_algorithm Wikipedia — Package-merge algorithm]*[http://en.wikipedia.org/wiki/Canonical_Huffman_code Wikipedia — Canonical Huffman code]