Изменения

# является [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза | оптимальным префиксным кодом]]# * длина кодового слова не превышает заданной константы,* является оптимальным среди всех [[Кодирование_информации#Код | префиксных кодов]], удовлетворяющих первому условию.

==Пример.==Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из <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>.

== Сведение задачи о генерации оптимального префиксного кода с длиной кодового слова не более L бит к задаче о рюкзаке ==

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

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