Изменения
Нет описания правки
Из последнего утверждения и шага 2 легко заметить, что длина кодового слова, сгенерированного приведенным алгоритмом, действительно не превысит <tex>L</tex>. Это так, потому что мы создаем ровно L предметов веса <tex>p_{i}</tex> (частота символа). А значит, если в худшем случае мы возьмем все предметы данного веса, то их количество не превысит <tex>L</tex>.
Убедимся также, что необходимую сумму (<tex>n - 1</tex>) всегда можно набрать. Зафиксируем размер алфавита равным <tex>n = 2^k</tex>. Теперь вспомним неравенство, которым связаны <tex>n</tex> и <tex>L</tex>: <tex> n <= \le 2^L </tex>. Возьмем минимально возможное значение <tex>L</tex> такое, что <tex>2^L = n</tex>. По условию у нас есть по <tex>n</tex> монет номинала <tex>2^{-i}</tex>, где <tex>-1 \le i \le L<=i<=-1</tex>. Попробуем посчитать суммарную стоимость имеющихся монет:<tex>\frac{n/(}{2^1) } + \frac{n/(}{2^2) } + \dots + \frac{n / (}{2^L) } </tex>
Поскольку <tex>n = 2^L</tex>:
<tex>(\frac{2^L)/(}{2^1) } + (\frac{2^L)/(}{2^2) } + \dots + (\frac{2^L) / (}{2^L) } = 2^({L - 1) } + 2 ^ ({L - 2) } + \dots + 2^({L - L) } = (2^L) - 1 = n - 1 </tex>
Таким образом, мы набрали необходимую сумму, используя все предметы. Но так как мы рассматривали граничный случай, при бОльших значениях L данную сумму гарантированно можно набрать.
[[Категория: Алгоритмы сжатия ]]
