Невеликий уривок з Вікіпедії.
Алгоритм Хаффмана - адаптивний жадібний алгоритм оптимального префіксного кодування алфавіту з мінімальною надмірністю. Був розроблений в 1952 році аспірантом Массачусетського технологічного інституту Девідом Хаффманом при написанні їм курсової роботи. В даний час використовується в багатьох програмах стиснення даних.
Цей метод кодування складається з двох основних етапів:
Побудова оптимального кодового дерева.
Побудова відображення код-символ на основі побудованого дерева.
Ідея алгоритму полягає в наступному: знаючи ймовірності символів в повідомленні, можна описати процедуру побудови кодів змінної довжини, що складаються з цілого кількості бітів. Символам з більшою ймовірністю ставляться у відповідність коротші коди. Коди Хаффмана мають властивість префіксних (т. Е. Жодне кодове слово не є префіксом іншого), що дозволяє однозначно їх декодувати.
Класичний алгоритм Хаффмана на вході отримує таблицю частот зустрічальності символів в повідомленні. Далі на підставі цієї таблиці будується дерево кодування Гоффмана (Н-дерево).
- Символи вхідного алфавіту утворюють список вільних вузлів. Кожен лист має вагу, який може дорівнювати або ймовірності, або кількістю входжень символу в стискає повідомлення.
- Вибираються два вільних вузла дерева з найменшими вагами.
- Створюється їх батько з вагою, рівним їх сумарному вазі.
- Батько додається в список вільних вузлів, а два його нащадка видаляються з цього списку.
- Однією дузі, що виходить з батьків, ставиться у відповідність біт 1, інший - біт 0.
- Кроки, починаючи з другого, повторюються до тих пір, поки в списку вільних вузлів не залишиться тільки один вільний вузол. Він і буде вважатися коренем дерева.
Цей процес можна представити як побудова дерева, коріння якого - символ з сумою ймовірностей об'єднаних символів, що вийшов при об'єднанні символів з останнього кроку, його n0 нащадків - символи з попереднього кроку і т. Д.
Щоб визначити код для кожного з символів, що входять в повідомлення, ми повинні пройти шлях від кореня до листа дерева, що відповідає поточному символу, накопичуючи біти при переміщенні по гілках дерева (перша гілка в дорозі відповідає молодшому біту). Отримана таким чином послідовність бітів є кодом даного символу, записаним в зворотному порядку.