Изменения

== Кодирование Хаффмана ==

== Кодирование Хаффмана ==

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности появления символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством [[Префиксный код|префиксности]] (то есть ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать.

Идея алгоритма состоит в следующем: зная вероятности появления символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством [[Префиксный код|префиксности]] (то есть ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать.

Классический алгоритм Хаффмана на входе получает таблицу [[частотность|частотностей]] символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).<ref>Д. Мастрюков. [http://www.compression.ru/download/articles/huff/mastrukov_1993_huffman.pdf Монитор 7-8.93]</ref>

Классический алгоритм Хаффмана на входе получает таблицу [[частотность|частотностей]] символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).<ref>Д. Мастрюков. [http://www.compression.ru/download/articles/huff/mastrukov_1993_huffman.pdf Монитор 7-8.93]</ref>