Кодирование методом Хаффмана

Смысл метода Хаффмана заключается в замене данных более эффективными кода­ми. Более короткие коды используются для замены более часто появляющихся вели­чин. Например в выражении abbbcccddeeeeeeeeef есть шесть уникальных величин, с частотами появления: а:1, b:3, c:3, d:2, e:9, f:l. Для образования минимального кода используется двоичное дерево. Алгоритм объединяет в пары элементы, появляющиеся наименее часто, затем пара объединяется в один элемент, а их частоты объединяются. Это действие повторяется до тех пор, пока элементы не объединятся в пары. В данном примере надо объединить а и f – это первая пара, а присваивается нулевая ветвь, a f – 1-я. Это означает, что 0 и 1 будут младшими битами кодов для а и f соответственно. Более старшие биты будут получены из дерева по мере его построения.

Суммирование частот дает в итоге 2. Теперь самая низкая частота – 2, поэтому пара а и f объединяется с d (которая тоже имеет частоту 2). Исходной паре присваивается нулевая ветвь, a d – ветвь 1. Таким образом, код для а заканчивается на 00; для f на 01, d заканчивается на 1 и будет на один бит короче по сравнению с кодами для а и f.

Дерево продолжает строиться подобным образом так, что наименее распространенные величины описываются более длинными кодами. Данное кодирование нуждается в точной статистике, выражающейся в том, как часто каждая величина появляется в файле. Следовательно, для работы по схеме Хаффмана необходимо два этапа: на первом этапе создается статистическая модель, на втором кодируются данные. Следует отметить, что компрессия и декомпрессия, по Хаффману, – достаточно медленный процесс.