Основы современных компьютерных технологий
Кодирование методом Хаффмана
Смысл метода Хаффмана заключается в замене данных более эффективными кодами. Более короткие коды используются для замены более часто появляющихся величин. Например в выражении abbbcccddeeeeeeeeef есть шесть уникальных величин, с частотами появления: а:1, b:3, c:3, d:2, e:9, f:l. Для образования минимального кода используется двоичное дерево. Алгоритм объединяет в пары элементы, появляющиеся наименее часто, затем пара объединяется в один элемент, а их частоты объединяются. Это действие повторяется до тех пор, пока элементы не объединятся в пары. В данном примере надо объединить а и f - это первая пара, а присваивается нулевая ветвь, a f - 1-я. Это означает, что Out будут младшими битами кодов для а и f соответственно. Более старшие биты будут получены из дерева по мере его построения.
364
Суммирование частот дает в итоге 2. Теперь самая низкая частота -2, поэтому пара а и f объединяется с d (которая тоже имеет частоту 2). Исходной паре присваиваемся нулевая ветвь, ad - ветвь 1. Таким образом, код для а заканчивается на 00; для f на 01, d заканчивается на 1 и будет на один бит короче по сравнению с кодами для а и f.
Дерево продолжает строиться подобным образом так, что наименее распространенные величины описываются более длинными кодами. Данное кодирование нуждается в точной статистике, выражающейся в том, как часто каждая величина появляется в файле. Следовательно, для работы по схеме Хаффмана необходимо два этапа: на первом этапе создается статистическая модель, на втором кодируются данные. Следует отметить, что компрессия и декомпрессия, по Хаффману, - достаточно медленный процесс.
365
364 :: 365 :: Содержание
