1632
правки
Изменения
м
rollbackEdits.php mass rollback
Пусть <tex>A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов, <tex>W=\{w_{1},w_{2}, \ldots ,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2}, \ldots ,c_{n}\}</tex>, где <tex>c_{i}</tex> является кодом для символа <tex>a_{i}</tex>, такой, что:
:* <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>,
:* cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>),
называется '''кодом Хаффмана'''.
}}
== Алгоритм построения бинарного кода Хаффмана ==
|}
На последнем шаге объединим два узла {{---}} <tex>brcd</tex> и <tex>a</tex>:
{| class="wikitable"
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
