Изменения
Нет описания правки
При этом <tex>h_{i}</tex> — это длина кодового слова для <tex>i</tex>-го символа. Зная длины кодовых слов, легко восстановить и сам код.
Из последнего утверждения и шага 2 легко заметить, что длина кодового слова, сгенерированного приведенным алгоритмом, действительно не превысит <tex>L</tex>. Это так, потому что мы создаем ровно L предметов веса <tex>p_{i}</tex> (частота символа). А значит, если в худшем случае мы возьмем все предметы данного веса, то их количество не превысит <tex>L</tex>. Обратите внимание, что одинаковые частоты у разных символов считаются разными,т.е. если <tex> p_{i} = p_{j}, i <> \ne j</tex>, то при подсчете количества предметов заданного веса мы считаем предеметы с частотой <tex>p_{i}</tex> и предметы с частотой <tex>p_{j}</tex> отдельно.
Оптимальность же кода следует из оптимальности решения задачи о рюкзаке. Действительно, частота символа - это вес предеметов, соответствующих ему. Значит, чем чаще символ встречается в тексте, тем реже он будет попадать в наш рюкзак (будет выгоднее брать предметы аналогичной ценности, но меньшего веса, соответствующие более редким символам), а значит, его код будет короче.
