Изменения
нет описания правки
'''Алгоритм Хаффмана''' — [[Адаптивный алгоритм|адаптивный]] [[простой алгоритм]] оптимального [[префиксный код|префиксного]] [[энтропийное кодирование|кодирования]] алфавита с минимальной [[избыточность]]ю. Был разработан в [[1952 год]]у аспирантом [[Массачусетский технологический институт|Массачусетского технологического института]] [[Хаффман, Дэвид|Дэвидом Хаффманом]] при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.
'''Алгоритм Хаффмана''' — [[Адаптивный алгоритм|адаптивный]] [[жадный алгоритм]] оптимального [[префиксный код|префиксного]] [[энтропийное кодирование|кодирования]] алфавита с минимальной [[избыточность]]ю. Был разработан в [[1952 год]]у аспирантом [[Массачусетский технологический институт|Массачусетского технологического института]] [[Хаффман, Дэвид|Дэвидом Хаффманом]] при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.
В отличие от [[Алгоритм Шеннона — Фано|алгоритма Шеннона — Фано]], алгоритм Хаффмана остаётся всегда оптимальным и для [[вторичный алфавит|вторичных алфавитов]] m<sub>2</sub> с более чем двумя символами.
В отличие от [[Алгоритм Шеннона — Фано|алгоритма Шеннона — Фано]], алгоритм Хаффмана остаётся всегда оптимальным и для [[вторичный алфавит|вторичных алфавитов]] m<sub>2</sub> с более чем двумя символами.
Этот процесс можно представить как построение [[Дерево (теория графов)|дерева]], корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n<sub>0</sub> потомков — символы из предыдущего шага и т. д.
Этот процесс можно представить как построение [[Дерево (теория графов)|дерева]], корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n<sub>0</sub> потомков — символы из предыдущего шага и т. д.
Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от корня до листа дерева, соответствующего текущему символу, накапливая биты при перемещении по ветвям дерева (первая ветвь в пути соответствует младшему биту). Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке.
Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего текущему символу, до его корня, накапливая биты при перемещении по ветвям дерева (первая ветвь в пути соответствует младшему биту). Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке.
Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.
Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/huffman-tree-2003 Визуализатор кодирования букв русского алфавита]
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/huffman-tree-2003 Визуализатор кодирования букв русского алфавита]
* [http://algolist.manual.ru/compress/standard/huffman.php Сжатие по алгоритму Хаффмана] на algolist.manual.ru
* [http://algolist.manual.ru/compress/standard/huffman.php Сжатие по алгоритму Хаффмана] на algolist.manual.ru
{{методы сжатия}}
{{методы сжатия}}
[[Категория:Алгоритмы сжатия без потерь]]
[[Категория:Алгоритмы сжатия без потерь]]
[[Категория:Задачи, решаемые жадным алгоритмом]]
[[Категория:Задачи, решаемые жадным алгоритмом]]
[[de:Shannon-Fano-Kodierung#Huffman-Code]]