82
правки
Изменения
Нет описания правки
== Пример работы алгоритма генерации кода Хоффмана с длиной кодового слова не более L бит ==
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>P=\{p_{1},p_{2},...,p_{n}\}</tex> — соответствующий ему набор положительных целых весовчастот. Пусть <tex>L = 2</tex> - ограничение на длину кодового слова.
Сначала создадим необходимый набор монет;
Теперь нам нужно набрать монеты суммарным номиналом <tex> n - 1 = 2 </tex> с минимальным суммарным весом, т.е. просто возьмем первые две монеты из итогового списка. Посчитаем массив <tex> H </tex>. Обратите внимание, что при подсчете количества монет определенного веса мы учитываем монеты, которые были даны изначально, а не те, которые получились путем слияния исходных.
<tex>H=\{12,2,21\}</tex>
Итак, мы получили длины кодовых слов для символов. Осталось восстановить ответ.
== Пример восстановления ответа. ==
Итак, у нас есть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>P=\{1, 2, 3\}</tex> — соответствующий ему набор частот, а также <tex>H=\{2,2,1\}</tex> - соответсвующие длины кодовых слов
