14
правок
Изменения
м
Нет описания правки
'''''Алгоритм Хаффмана''''' — алгоритм оптимального префиксного кодирования алфавита. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется Используется во многих программах сжатия данных, например, для сжатия изображений он использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротивPKZIP 2, встречающимся редко — цепочку большей длиныLZH и др.
== Определение ==
|id=th1
|statement=
Алгоритм Хаффмана дает [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза | оптимальный префиксный код]].
|proof=
Справедливость теоремы непосредственно следует из лемм (1) и (2)
*[http://ru.wikipedia.org/wiki/%C4%E2%EE%E8%F7%ED%EE%E5_%E4%E5%F0%E5%E2%EE Википедия — Бинарное дерево]
*[http://ru.wikipedia.org/wiki/Префиксный_код Википедия — Префиксный код]
*[http://neerc.ifmo.ru/wiki/index.php?title=[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза | Задача об оптимальном префиксном коде]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
