Изменения

'''Алгоритм Хаффмана''' — [[Адаптивный алгоритм|адаптивный]] [[нежадный алгоритм]] оптимального [[префиксный код|префиксного]] [[энтропийное кодирование|кодирования]] алфавита с минимальной [[избыточность]]ю. Был разработан в [[1952 год]]у аспирантом [[Массачусетский технологический институт|Массачусетского технологического института]] [[Хаффман, Дэвид|Дэвидом Хаффманом]] при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

'''Алгоритм Хаффмана''' — [[Адаптивный алгоритм|адаптивный]] [[жадный алгоритм]] оптимального [[префиксный код|префиксного]] [[энтропийное кодирование|кодирования]] алфавита с минимальной [[избыточность]]ю. Был разработан в [[1952 год]]у аспирантом [[Массачусетский технологический институт|Массачусетского технологического института]] [[Хаффман, Дэвид|Дэвидом Хаффманом]] при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

В отличие от [[Алгоритм Шеннона — Фано|алгоритма Шеннона — Фано]], алгоритм Хаффмана остаётся всегда оптимальным и для [[вторичный алфавит|вторичных алфавитов]] m₂ с более чем двумя символами.

В отличие от [[Алгоритм Шеннона — Фано|алгоритма Шеннона — Фано]], алгоритм Хаффмана остаётся всегда оптимальным и для [[вторичный алфавит|вторичных алфавитов]] m₂ с более чем двумя символами.

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

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

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

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

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). <ref>Д. Мастрюков. [http://masters.donntu.edu.ua/2005/fvti/kozlenko/library/mastrukov_1993_huffman.pdf Монитор 7-8.93]</ref>

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). <ref>Д. Мастрюков. [http://masters.donntu.edu.ua/2005/fvti/kozlenko/library/mastrukov_1993_huffman.pdf Монитор 7-8.93]</ref>