Код Гаффмана
З Вікіпедії, безкоштовно encyclopedia
Алгоритм Гаффмана (або коди Гафмена[1]) — адаптивний жадібний алгоритм оптимального префіксного кодування алфавіту з мінімальною надмірністю. Був розроблений аспірантом Массачусетського технологічного інституту Девідом Гаффманом при написанні ним курсової роботи та надрукований в статті 1952 року «A Method for the Construction of Minimum-Redundancy Codes»[2]. Нині[коли?] використовується в багатьох програмах стиснення даних без втрат.
На відміну від алгоритму Шеннона — Фано, алгоритм Гаффмана залишається завжди оптимальним і для вторинних алфавітів m2 з більш ніж двома символами.
Цей метод кодування складається з двох основних етапів:
- Побудова оптимального кодового дерева
- Побудова відображення код-символ на основі побудованого дерева