Изменения

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

Чтобы доказать корректность алгоритма Хаффмана, покажем, что в [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза | задаче о построении оптимального префиксного кода]] проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.