Изменения
Нет описания правки
При этом <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> отдельно.
Оптимальность же кода следует из оптимальности решения задачи о рюкзаке. Действительно, частота символа - это вес предеметов, соответствующих ему. Значит, чем чаще символ встречается в тексте, тем реже он будет попадать в наш рюкзак (будет выгоднее брать предметы аналогичной ценности, но меньшего веса, соответствующие более редким символам), а значит, его код будет короче.
# Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.
Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (т.к. ведь мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Т.е. Значит, код, сгенерированный таким образом является префиксным.
== Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит ==
<tex> C = 0 </tex>
Сопоставим следующему символу следующее двоичное число. Т.к. Так как длина кода увеличилась на один, то припишем справа ноль:
<tex> B = 10 </tex>
