3622
правки
Изменения
м
→Сведение задачи о генерации оптимального префиксного кода с длиной кодового слова не более L бит к задаче о рюкзаке
При этом <tex>h_{i}</tex> — это длина кодового слова для <tex>i</tex>-го символа. Зная длины кодовых слов, легко восстановить и сам код.
Из последнего утверждения и шага 2 два легко заметить, что длина кодового слова, сгенерированного приведенным алгоритмом, действительно не превысит <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 \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</tex>. Попробуем посчитать суммарную стоимость имеющихся монет:
