Изменения

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

* длина кодового слова не превышает заданной константы,* является оптимальным среди всех [[Кодирование_информации#Код | префиксных кодов]], удовлетворяющих первому условию.}} Здесь будет приведен алгоритм, решающий эту задачу за время <tex> O(nL) </tex>, где <tex>L</tex> — максимальная длина кодового слова, <tex>n</tex> — размер алфавита, c помощью сведения задачи к [[Задача_о_рюкзаке | задаче о рюкзаке]]. ==Пример.==Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из <tex>5 </tex> символов <tex>A=\{A,B,C, CD, DE\}</tex>, а частоты символов являются степенями двойки: <tex>P=\{1,2,4, 8, 16\}</tex>. Тогда классический код Хоффмана Хаффмана будет выглядеть следующим образом:

Важно заметить следующий факт. В : в худшем случае все кодовые слова будут иметь длину <tex>L</tex> бит. Тогда мы можем закодировать <tex> 2^L </tex> символов. Таким образом, нельзя получить описанный выше код, если <tex> n > 2^L </tex>. == Сведение к задаче о рюкзаке ==Пусть <tex>L</tex> — ограничение на длину кодового слова, а <tex>P=\{p_{1},p_{2},\dots,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},\dots,h_{n}\}</tex>, где <tex>h_{i}</tex> — количество предметов ценностью <tex>p_{i}</tex>, которые попали в наш набор. При этом <tex>h_{i}</tex> — это длина кодового слова для <tex>i</tex>-го символа. Зная длины кодовых слов, легко восстановить и сам код. Из последнего утверждения и шага два легко заметить, что длина кодового слова, сгенерированного приведенным алгоритмом, действительно не превысит <tex>L</tex>. Это так, потому что мы создаем ровно <tex>L</tex> предметов веса <tex>p_{i}</tex> (частота символа). А значит, если в худшем случае мы возьмем все предметы данного веса, то их количество не превысит <tex>L</tex>. Убедимся также, что необходимую сумму (<tex>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 = n</tex>. По условию у нас есть по <tex>n</tex> монет номинала <tex>2^{-i}</tex>, где <tex>1 \leqslant i \leqslant L</tex>. Попробуем посчитать суммарную стоимость имеющихся монет: <tex dpi = "160">\frac{n}{2^1} + \frac{n}{2^2} + \dots + \frac{n}{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]